Preview

Informatics in school

Advanced search

Empirical research of recursive functions' execution time and development of STEM competencies

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

Abstract

The article presents an approach to studying recursive functions at an in-depth level of studying informatics course in grades 10–11 using the example of functions for calculating factorial and generalized Fibonacci functions of various orders. Being the object of study in the research work considered in the article, these functions provide average experimental runtime data, which are further visualized, analyzed and approximated. In the process of such analysis, theoretical estimates of computational complexity are compared with the obtained experimental data on the execution time of recursive functions depending on the variable arguments. Examples of 2D visualization of the execution time of the factorial calculation function using the Python programming language and 3D visualization of the execution time of generalized Fibonacci functions of various orders in a spreadsheet editor are shown. Developed STEM competencies, studied theories, methods, principles and concepts in science, technology, engineering and mathematics are highlighted. The objects of scientific novelty in this work are: demonstration of the nonlinear computational complexity of the recursive algorithm for calculating the factorial in Python with large arguments and identifying the reasons for this behavior of this algorithm, based on a counterexample; writing a recursive generalized function for calculating the numbers of Fibonacci series with different orders as an example of the implementation of the DRY principle; proposed approaches to in-depth study of recursion and acquaintance of students with the theory of computational complexity.

About the Author

V. S. Popov
Bauman Moscow State Technical University; Tver State University
Russian Federation

Moscow;

Tver.



References

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.


Review

For citations:


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

Views: 78


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.


ISSN 2221-1993 (Print)