Preview

Информатика в школе

Расширенный поиск

Эмпирическое исследование времени выполнения рекурсивных функций и развитие STEM-компетенций

https://doi.org/10.32517/2221-1993-2024-23-3-5-14

Аннотация

В статье представлен подход к изучению рекурсивных функций на углубленном уровне освоения курса информатики в X—XI классах на примере функций вычисления факториала и обобщенных функций Фибоначчи различного порядка. Являясь объектом исследования в рассматриваемой в статье исследовательской работе, эти функции предоставляют усредненные экспериментальные данные времени выполнения, которые в дальнейшем визуализируются, анализируются и аппроксимируются. В процессе такого анализа соотносятся теоретические оценки вычислительной сложности и полученные экспериментальные данные времени выполнения рекурсивных функций в зависимости от переменных аргументов. Показаны примеры двумерной визуализации времени выполнения функции вычисления факториала средствами языка программирования Python итрехмерной визуализации времени выполнения обобщенных функций Фибоначчи различного порядка в редакторе электронных таблиц. Выделены развиваемые STEM-компетенции, изучаемые теории, методы, принципы и концепции в науке, технологиях, инженерии и математике. Объектами научной новизны в данной работе являются: демонстрация нелинейной вычислительной сложности рекурсивного алгоритма вычисления факториала в Python при больших аргументах и выявление причин такого поведения данного алгоритма, основанное на контрпримере; написание рекурсивной обобщенной функции вычисления чисел рядов Фибоначчи с различным порядком как пример реализации принципа DRY; предложенные подходы к углубленному изучению рекурсии и знакомству обучающихся с теорией вычислительной сложности.

Об авторе

В. С. Попов
Московский государственный технический университет имени Н. Э. Баумана (национальный исследовательский университет); Тверской государственный университет
Россия

Попов Владислав Сергеевич, старший преподаватель кафедры «Информационные системы и телекоммуникации», факультет «Информатика и системы управления»; аспирант Института педагогического образования и социальных технологий;

победитель Всероссийского конкурса «Эксперименты, исследования, проекты по информатике»
в номинации «Эксперименты, исследования, проекты по информатике: теория и  практика»,

105005, г. Москва, 2-я Бауманская ул., д. 5, стр. 1;

170100, г. Тверь, ул. Желябова, д. 33.



Список литературы

1. Атлас профессий будущего / Н. Ю. Анисимов, Л. М. Гохберг, Г. О. Греф, Н. В. Дудина, С. В. Черногорцева, Н. А. Шматко и др.; НИУ ВШЭ; ПАО «Сбербанк». Вып. 2. М.: НИУ ВШЭ, 2021. 240 с. https://sberuniversity.ru/upload/edutech/reports/Atlas_future_professions.pdf

2. Барабаш Г. И., Старикова М. Е. Рекурсивные задачи в ЕГЭ по информатике // Информатика: проблемы, методы, технологии. Материалы XX Международной научно-методической конференции (Воронеж, 13–14 февраля 2020 года) / под ред. А. А. Зацаринного, Д. Н. Борисова. Воронеж: Научно-исследовательские публикации (ООО «Вэлборн»), 2020. С. 1887–1890. EDN: VETFVK.

3. Богданова В., Кириак Л. Изучение рекурсивных алгоритмов с позиции STEAM в среднем образовании // Materialele Conferinței Științifice Internaționale «Abordări inter/ transdisciplinare în predarea științelor reale (concept STEAM)», ediția a 2-a (Chişinău: UST, 28–29 Octombrie 2022). С. 366–371. http://dir.upsc.md:8080/xmlui/bitstream/handle/123456789/4962/Conf-Abordari-predare-stiinte-reale-STEAM-2022-p366-371.pdf?sequence=1&isAllowed=y

4. Богданова В. А., Тодорова Ю. Г., Чумак Л. В. Из опыта проведения междисциплинарного внеаудиторного мероприятия «Удивительный мир рекурсии» // Инновационные подходы в образовании. Научно-методический семинар (30 марта 2023 года) / под общ. ред. А. Л. Цынцарь, Е. В. Гатанюк. Тирасполь: Изд-во Приднестр. ун-та, 2023. C. 13–15.

5. Вилков А. Н. Курс лекций «Методология проведения научного эксперимента». М.: МГТУ им. Н. Э. Баумана, 2012. 33 с.

6. Городов А. А., Городова Л. В., Кузнецов А. А. Моделирование сложных процессов при помощи авторегрессии // Вестник Сибирского государственного аэрокосмического университета им. академика М. Ф. Решетнева. 2014. № 5 (57). С. 57–61. EDN: TYWGSF.

7. Девятков В. В., Лычков И. И., Наунг М. Т. Прототипирование верификации поведения интеллектуальных агентов в языке логического программирования ПРОЛОГ: учебное пособие. М.: Изд-во МГТУ им. Н. Э. Баумана, 2021. 56 с. EDN: EHIBSP.

8. Дегтяренко В. А. Теория алгоритмов в школьном курсе информатики // Актуальные проблемы преподавания информатики и информатизации образовательного процесса в учреждениях основного и дополнительного образования. Сборник научных трудов. Комсомольск-на-Амуре: Амурский гуманитарно-педагогический государственный университет, 2021. С. 33–39. EDN: RUPUKH.

9. Деза Е. И. Научная составляющая и методические возможности понятия «факториал» // Проблемы теории и практики инновационного развития и интеграции современной науки и образования. Материалы IV международной междисциплинарной конференции (Москва, 15 февраля 2023 года). М.: Государственный университет просвещения, 2024. С. 23–26. EDN: RNVIGF.

10. Долинский М. С. Ускорение рекурсивных решений при помощи мемоизации // Информатика в школе. 2022. № 6. С. 55–67. EDN: PSWCPK. DOI: 10.32517/2221-1993-2022-216-55-67.

11. Дроздюк А. В. Фибоначчи, его числа и кролики. Торонто: Choven, 2010. 145 с.

12. Дудина И. П., Коновалова А. Д. Подготовка учащихся к единому государственному экзамену по информатике (по разделу «Алгоритмизация и программирование») // Инновации. Наука. Образование. 2019. № 10 (11). С. 1–6. EDN: BMGFRK.

13. Зуева И. Ю. Рекурсивные алгоритмы — инструмент развития стиля мышления. (ЕГЭ по информатике) // Информатика: проблемы, методология, технологии. Сборник материалов XVII международной научно-методической конференции (Воронеж, 9–10 февраля 2017 года). Т. 5. Воронеж: ООО «Вэлборн», 2017. С. 3–6. EDN: YJOQNX.

14. Иванов О. А. Алгебраические и комбинаторные методы исследования обобщений чисел Фибоначчи // Актуальные вопросы современных математических и естественных наук. Сборник научных трудов по итогам международной научнопрактической конференции (Екатеринбург, 10 марта 2016 года). Вып. III. Екатеринбург: Инновационный центр развития образования и науки, 2016. С. 13–15. EDN: VPZFVR.

15. Киттель Ч. Элементарная статистическая физика / пер. с англ. Л. А. Шубиной, под ред. С. В. Вонсовского. М: Изд-во иностранной литературы, 1960. 288 с.

16. Куликов В. Л., Олехова Е. Ф., Оселедец В. И. Замечания об абсолютной непрерывности меры Эрдеша для золотого сечения, числа трибоначчи и марковской цепи // Современная математика и концепции инновационного математического образования. 2022. Т. 9. № 1. С. 66–76. EDN: FITMNB. DOI: 10.54965/24129895_2022_9_1_66.

17. Куликов В. Л., Олехова Е. Ф., Оселедец В. И. Об абсолютной непрерывности меры Эрдёша для золотого сечения, числа трибоначчи и марковских цепей второго порядка // Теория вероятностей и ее применения. 2024. Т. 69. Вып. 2. С. 335–353. EDN: YWCGER. DOI: 10.4213/tvp5628.

18. Куликов В. Л., Олехова Е. Ф., Оселедец В. И. Сингулярность меры Эрдеша для 2-марковских цепей и числа 4-наччи // Современная математика и концепции инновационного математического образования. 2023. Т. 10. № 1. С. 77–87. EDN: LOWLOV. DOI: 10.54965/24129895_2023_10_1_77.

19. Ладиков А. В. Улучшенный алгоритм вычисления факториала // Математические заметки. 2008. Т. 83. Вып. 6. С. 857–863. DOI: 10.4213/mzm4837. https://www.mathnet.ru/links/2ebe8133b2d42988b39aac04eee34917/mzm4837.pdf.

20. Лапаев А. О. Реализация алгоритма Карацубы и оценки сложности // Вестник Тамбовского университета. Серия: Естественные и технические науки. 2008. Т. 13. № 1. С. 142–143. EDN: IIWFVP.

21. Лебедев С. А. Методология научного познания: учебное пособие для вузов. М.: Юрайт, 2024. 153 с. https://urait.ru/bcode/537439

22. Локтев Д. А., Видьманов Д. А. Учебное пособие для поступающих в вузы. Информатика: учебное пособие. 2-е изд., испр. М.: Изд-во МГТУ им. Н. Э. Баумана, 2023. 196 с.

23. Лорсанова З. М. Использование рекурсивных методов в решении алгоритмических задач // Актуальные научные исследования в современном мире. 2019. № 12-4(56). С. 129–131. EDN: MJKRKB.

24. Лычков И. И. Применение логического программирования для решения олимпиадных задач по информатике // Преподавание информационных технологий в Российской Федерации. Сборник научных трудов Двадцать второй открытой Всероссийской конференции (Тверь, 16–17 мая 2024 года). [В печати.]

25. Мартынюк Ю. М., Ванькова В. С., Даниленко С. В. К вопросу об изучении рекурсивных алгоритмов // Университет XXI века: научное измерение. Материалы научной конференции научно-педагогических работников, аспирантов, магистрантов ТГПУ им. Л. Н. Толстого (Тула, 14–30 ноября 2022 года). Тула: Тульский государственный педагогический университет им. Л. Н. Толстого, 2022. С. 210–212. EDN: KYOWEN.

26. Морозов А. А., Вайш А., Полупанов А. Ф., Анциперов В. Е., Лычков И. И., Алфимцев А. Н., Девятков В. В. Разработка исследовательской программной платформы для параллельного объектно-ориентированного логического программирования интеллектуального видеонаблюдения // Интеллектуализация обработки информации. 2014. Т. 10. № 1. С. 130–131. EDN: YLJMDV.

27. Никифоров П. В., Вяткин А. А. Инновационный подход к преподаванию функционального программирования (на примере F#) // Инновации в науке и практике. Сборник статей по материалам XIII международной научно-практической конференции (Барнаул, 26 декабря 2018 года). Ч. 5 (5). Уфа: ООО «Дендра», 2018. С. 126–131. EDN: ZAPBGP.

28. Огурцов А. П. Постмодернизм в контексте новых вызовов науки и образования // Вестник Самарской гуманитарной академии. Выпуск «Философия. Филология». 2006. № 1(4). С. 3–27.

29. Подласый И. П. Педагогика: Новый курс: учебник для студентов высших учебных заведений. В 2 кн. М.: Гуманит. изд. центр ВЛАДОС, 2003. Кн. 1: Общие основы. Процесс обучения. 576 с.

30. Пономарев А. Б., Пикулева Э. А. Методология научных исследований: учебное пособие. Пермь: Изд-во Пермского национального исследовательского политехнического университета, 2014. 186 с.

31. Приоритетные направления современной психологии и педагогики: коллективная монография / Л. А. Абросимова-Романова, А. В. Антоновский, Е. В. Астапенко и др. Тверь: Тверской государственный университет, 2023. 223 с. EDN: JECRVO.

32. Симанева Т. А., Топченко Р. К. Проектирование и реализация цифрового образовательного ресурса для изучения темы «Рекурсия» в школьном курсе информатики // Естественные и гуманитарные науки в современном мире. Материалы Международной научно-практической конференции (Орел, 13–15 мая 2021 года). Орел: Орловский государственный университет имени И. С. Тургенева, 2021. С. 465–471. EDN: JFOIMR.

33. Смирнова А. В. Особенности изучения темы «Рекурсия» в школьном курсе информатики // Современные проблемы и перспективные направления инновационного развития науки. Сборник статей Международной научно-практической конференции (Томск, 25 апреля 2016 года). В 4 ч. Ч. 2. Томск: ООО «Аэтерна», 2016. С. 188–193. EDN: VWTMNR.

34. Федеральная рабочая программа среднего общего образования. Информатика (базовый уровень) (для 10–11 классов образовательных организаций). М.: Институт стратегии развития образования, 2023. 38 с. https://edsoo.ru/wp-content/uploads/2023/08/21_ФРП-Информатика_10-11-классы_база.pdf

35. Федеральная рабочая программа среднего общего образования. Информатика (углубленный уровень) (для 10–11 классов образовательных организаций). М.: Институт стратегии развития образования, 2023. 52 с. https://edsoo.ru/wp-content/uploads/2023/08/22_ФРП_Информатика-10-11-классы_угл.pdf

36. Чернов В. М. Фибоначчи, трибоначчи, ..., гексаначчи и параллельная безошибочная машинная арифметика // Компьютерная оптика. 2019. Т. 43. № 6. С. 1072–1078. EDN: AMUIMF. DOI: 10.18287/2412-6179-2019-43-6-1072-1078.

37. Шваб А. Г. Формирование компьютерного (вычислительного) мышления // Наука сегодня: глобальные вызовы и механизмы развития. Материалы международной научнопрактической конференции (Вологда, 28 апреля 2021 года). Вологда: ООО «Маркер», 2021. С. 57–58. EDN: DHXEWR.

38. Breiner J. M., Sheats Harkness S., Johnson C. C., Koehler C. M. What is STEM? A discussion about conceptions of STEM in education and partnerships // School Science and Mathematics. 2012. Vol. 112 (1). P. 3–11. DOI:10.1111/j.1949-8594.2011.00109.x.

39. Brown R., Brown J., Reardon K., Merrill C. Understanding STEM: current perceptions // Technology and Engineering Teacher. March 2011. P. 5–9.

40. Gardner M. The second scientific American book of mathematical puzzles and diversions. Chicago: The University of Chicago Press, 1987. 254 p.

41. Thomas D., Hunt A. The Pragmatic Programmer: Your journey to mastery. 20th Anniversary Edition. Addison-Wesley Professional, 2019. 352 p.


Рецензия

Для цитирования:


Попов В.С. Эмпирическое исследование времени выполнения рекурсивных функций и развитие STEM-компетенций. Информатика в школе. 2024;(3):5-14. https://doi.org/10.32517/2221-1993-2024-23-3-5-14

For citation:


Popov V.S. Empirical research of recursive functions' execution time and development of STEM competencies. Informatics in school. 2024;(3):5-14. (In Russ.) https://doi.org/10.32517/2221-1993-2024-23-3-5-14

Просмотров: 61


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2221-1993 (Print)