Preview

Informatics in school

Advanced search

Recursive function for solving a dynamic programming task: from knowledgeless form of competence towards knowledge and understanding

https://doi.org/10.32517/2221-1993-2024-23-5-85-94

Abstract

The recursive function for solving task 23 on dynamic programming of the Informatics Unified State Exam is used by examinees without a deep understanding of the principles of its operation: with the formed skill of its use, the necessary knowledge is missing, which is an knowledgeless form of competence. Understanding the principles of the program code and the transition from the knowledgeless form to full-fledged competencies (information, digital, mathematical, programming) will allow students to gain deeper knowledge of the theory of recursive functions, to form skills and attitudes in the field of solving dynamic programming problems at a higher level, which can lead to improved educational results, understanding of dynamic programming methods used, including Unified State Exam tasks and informatics Olympiads. To form the knowledge component of the competence, it is proposed to build, study and use call trees of the recursive function, created in the Observable programming environment, as well as study memorization as a key difference between the dynamic programming method and recursion.

About the Authors

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

Moscow

Tver



E. A. Alefirenko
Moscow City University
Russian Federation

Moscow



L. Yu. Chernitsyna
Moscow City University
Russian Federation

Moscow



References

1. Белякова Е. Г. Понимание как категория смыслоориентированной педагогики // Образование и наука. Известия УрО РАО. 2006. № 6 (42). С. 21–28. EDN: IUZJQV.

2. Брызгалина Е. В. Компетентностный подход в системе образования // ПостНаука. https://www.youtube.com/watch?v=lc6EMbZTN_4

3. Брызгалина Е. В. Компетентностный подход и будущее социогуманитарного образования // Вестник Волгоградского государственного университета. 2013. № 1 (23). С. 162–168. EDN: QJBGOD.

4. Брызгалина Е. В. Проблемы интеграции естественнонаучного и философского знания в современном образовании: социальные аспекты // Философия и общество. 2017. № 2 (83). С. 94–96. EDN: ZCPEKN.

5. Гаенко Н. Е. Динамическое программирование в школьном курсе информатики // Информационные и инновационные технологии в науке и образовании. Материалы V Всероссийской научно-практической конференции смеждународным участием. К 65-летию Таганрогского института имени А. П. Чехова (Таганрог, 28–29 октября 2020 года). Ростов н/Д: Издательско-полиграфический комплекс РГЭУ (РИНХ), 2021. С. 584–586. EDN: PHRQBZ.

6. Демонстрационный вариант контрольных измерительных материалов единого государственного экзамена 2012 года по информатике и ИКТ. М.: Федеральный институт педагогических измерений, Федеральная служба по надзору в сфере образования и науки Российской Федерации, 2011. 36 с.

7. Демонстрационный вариант контрольных измерительных материалов единого государственного экзамена 2016 года по информатике и ИКТ. М.: Федеральный институт педагогических измерений, 2015. 54 с.

8. Демонстрационный вариант контрольных измерительных материалов единого государственного экзамена 2023 года по информатике. М.: Федеральный институт педагогических измерений, Федеральная служба по надзору в сфере образования и науки, 2022. 21 с.

9. Демонстрационный вариант контрольных измерительных материалов единого государственного экзамена 2024 года по информатике. М.: Федеральный институт педагогических измерений, Федеральная служба по надзору в сфере образования и науки, 2023. 24 с.

10. Долгушин Н. А., Оленькова М. Н. Решение задач ЕГЭ по информатике в среде программирования PascalABC.NET // Международный студенческий научный вестник. 2015. № 3-2. С. 240–241. EDN: TWPKTT.

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

12. Ерофеев А. Н. Решение задач динамического программирования при подготовке к ЕГЭ по информатике // Актуальные проблемы модернизации математического и естественнонаучного образования. Сборник научных трудов по материалам Всероссийской научно-методической конференции (Балашов, 15 мая 2020 года). Балашов: Саратовский источник, 2020. С. 107–110. EDN: RUYALN.

13. Заводчикова Н. И., Быкова И. А. Укрупнение дидактических единиц при изучении метода динамического программирования в средней школе // Актуальные проблемы теории и практики обучения физико-математическим и техническим дисциплинам в современном образовательном пространстве. IV Всероссийская (с международным участием) научно-практическая конференция, посвященная 75-летию факультета физики, математики, информатики Курского государственного университета (Курск, 16–17 декабря 2020 года). Курск: Курский государственный университет, 2020. С. 289–294. EDN: GSRACM.

14. Каширская И. И. ЕГЭ: задачи 6-2 и 15 как способ подготовки к решению задачи 22 и решение задачи 22 обратным способом // Информатика: проблемы, методология, технологии. Сборник материалов XIX международной научно-методической конференции (Воронеж, 14–15 февраля 2019 года). Воронеж: Изд-во «Научно-исследовательские публикации» (ООО «Вэлборн»), 2019. С. 1840–1845. EDN: ZFDRBB.

15. Киселева М. М. Синергетический подход в преподавании информатики как элемент развития ключевых компетенций учащихся // Информатика в школе. 2019. № 4. С. 23–31. EDN: KMDKUV. DOI: 10.32517/2221-1993-2019-18-4-23-31.

16. Козлов С. В., Быков А. А. Решение задач динамического программирования ЕГЭ по информатике средствами электронных таблиц // Системы компьютерной математики и их приложения. 2022. № 23. С. 356–361. EDN: ADRMTU.

17. Коршунова Н. Л. Компетентностный и деятельностный подходы к модернизации высшей школы // Лингвокультурное образование в системе вузовской подготовки специалиста. 2017. Т. 1. № 2 (10). С. 184–192. EDN: YSCVIL.

18. Лещинер В. Р., Ройтберг М. А. Методические рекомендации для учителей, подготовленные на основе анализа типичных ошибок участников ЕГЭ 2015 года по информатике и ИКТ. М.: Федеральный институт педагогических измерений, 2015. 31 с.

19. Лысикова А. А., Редько Е. А. Принцип динамического программирования в решении задания 23 ЕГЭ по информатике // Материалы I региональной студенческой конференции к 65-летию ТОГУ. Материалы конференции (Хабаровск, 27–28 апреля 2023 года). Хабаровск: Тихоокеанский государственный университет, 2023. С. 236–242. EDN: OQYZZV.

20. Муртузалиева А. С., Халимбеков М. М. Использование динамического программирования для решения некоторых заданий ЕГЭ по информатике и ИКТ // Наука и образование: состояние, проблемы, перспективы развития. Материалы научной сессии профессорско-преподавательского состава Дагестанского государственного педагогического университета, посвященной 100-летию создания первого в Дагестане педагогического института (Махачкала, 8–9 ноября 2017 года). Махачкала: Дагестанский государственный педагогический университет, 2018. С. 236–239. EDN: RSNJRZ.

21. Муцурова З. М. Динамическое программирование в задачах ЕГЭ // Известия Чеченского государственного педагогического университета. Серия 2: Естественные и технические науки. 2019. Т. 17. № 1 (20). С. 44–47. EDN: VJYMNW.

22. Педагогический энциклопедический словарь / гл. ред. Б. М. Бим-Бад, редкол.: М. М. Безруких, В. А. Болотов, Л. С. Глебова и др. М.: Большая рос. энцикл., 2002. 527 с.

23. Поляков К. Ю. 23: перебор вариантов, динамическое программирование // Сайт Константина Полякова. ЕГЭ по информатике: подготовка кЕГЭ-2024 по информатике, разбор задач ЕГЭ-2024 по информатике, материалы для подготовки к ЕГЭ. https://kpolyakov.spb.ru/download/ege23.doc

24. Поляков К. Ю. Динамическое программирование в задачах обработки последовательностей ЕГЭ по информатике // Информатика в школе. 2020. № 5. С. 55–63. EDN: SXZKLG. DOI: 10.32517/2221-1993-2020-19-5-55-63.

25. Попов В. С. Анализ изменения среднего процента выполнения заданий ЕГЭ по информатике в связи с введением компьютерного формата экзамена // Новые информационные технологии в образовании. Сборник научных трудов 13-й международной научно-практической конференции (Москва, 31 января — 1 февраля 2023 года). Ч. 2. М.: 1С-Паблишинг, 2023. С. 153–156. EDN: DBTYBS.

26. Попов В. С., Абросимова-Романова Л. А. Анализ рисков выпускников и выделение необходимых компетенций в связи с изменением среднего процента выполнения заданий ЕГЭ по информатике за 2019–2023 годы и введением компьютерного формата экзамена // Новые информационные технологии в образовании. Сборник научных трудов XXIV Международной научно-практической конференции (Москва, 30–31 января 2024 года). М.: 1С-Паблишинг, 2024. С. 326–330. EDN: RJIRBK.

27. Попов В. С., Видьманов Д. А. Популярность ЕГЭ по информатике // Преподавание информационных технологий в Российской Федерации. Сборник научных трудов Двадцать первой открытой Всероссийской конференции (Нижний Новгород, 18–19 мая 2023 года). Н. Новгород: Изд-во Нижегородского государственного университета им. Н. И. Лобачевского, 2023. С. 489–491. EDN: TKPFHZ.

28. Рябинина Е. Е. Решение задач ЕГЭ с использованием алгоритмов динамического программирования // Информационно-коммуникационные технологии в педагогическом образовании. 2019. № 6 (63). С. 71–78. EDN: GKGDSA.

29. Садыкова А. Р., Белоусова А. С. Методические основы формирования предпрофессиональных ИТ-компетенций старшеклассников в детских технопарках «Кванториум» // Информатика и образование. 2023. Т. 38. № 5. С. 57–64. EDN: LHZVGW. DOI: 10.32517/0234-0453-2023-38-5-57-64.

30. Самылкина Н. Н. Структура и содержание цифровых компетенций, формируемых в предпрофессиональном обучении // Информатика в школе. 2020. № 4. С. 11–19. EDN: ZXUPNW. DOI: 10.32517/2221-1993-2020-19-4-11-19.

31. Томме Д. Е., Поспелов М. В. О взаимодействии учебных предметов математики и информатики на примере изучения числовых последовательностей // Математика: фундаментальные и прикладные исследования и вопросы образования. Материалы международной научно-практической конференции (Рязань, 26–28 апреля 2016 года). Рязань: Рязанский государственный университет имени С. А. Есенина, 2016. С. 484–486. EDN: XFEPMF.

32. Трекина А. С., Богданова М. В. Методические аспекты подготовки учащихся кЕГЭ по информатике с использованием языка программирования Python // Актуальные проблемы методики обучения информатике и математике в современной школе. Материалы международной научно-практической интернет-конференции (Москва, 18–24 апреля 2022 года). М.: МПГУ, 2022. С. 345–352. EDN: WEOGQT.

33. Тришкина А. В. Использование различных средств обучения динамическому программированию в ИТ-классах // #ScienceJuice2021. Сборник статей и тезисов (Москва, 22– 26 ноября 2021 года). Т. II. М.: ПАРАДИГМА, 2021. С. 167–175. EDN: NGSTYH.

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. Хеннер Е. К. Профессиональные знания и профессиональные компетенции в высшем образовании // Образование и наука. 2018. Т. 20. № 2. С. 9–31. EDN: NSHCCH. DOI: 10.17853/1994-5639-2018-2-9-31.

37. Чапурных А. А. Различные способы решения задания №23 КЕГЭ на перебор вариантов и динамическое программирование // Наука, общество, образование в условиях цифровизации и глобальных изменений. Сборник статей III Международной научно-практической конференции. Пенза: МЦНС «Наука и Просвещение». 2022. С. 44–48.

38. Шамаева Т. В. «Динамическое программирование» с помощью MS Excel на примере 23 номера из КЕГЭ по информатике // Архимед: Научно-методический сборник / отв. за выпуск А. Рубин, Т. Струков, П. Чулков, А. Шевкин. Вып. 18. М.: ООО «МАКС Пресс», 2022. С. 124–136. EDN: RTVFKK. https://www.elemschool.mathedu.ru/text/arhimed_2022_v18/p116/

39. Шафоростова Е. П. Динамическое программирование в олимпиадных задачах и ЕГЭ по информатике // Преподавание информационных технологий в Российской Федерации. Сборник научных трудов материалов Двадцатой открытой Всероссийской конференции (Москва, 19–20 мая 2022 года). М.: 1С-Паблишинг, 2022. С. 367–370. EDN: FJKEXE.

40. Popov V. S. Dynamic programming in tasks of the Russian Unified State Exam in Computer Science // 2024 6th International Youth Conference on Radio Electronics, Electrical and Power Engineering (REEPE), Moscow, Russian Federation, 2024. P. 1–6. DOI: 10.1109/REEPE60449.2024.10479768.

41. Tree mark | Observable Plot // OBSERVABLEHQ.COM. https://observablehq.com/plot/marks/tree


Review

For citations:


Popov V.S., Alefirenko E.A., Chernitsyna L.Yu. Recursive function for solving a dynamic programming task: from knowledgeless form of competence towards knowledge and understanding. Informatics in school. 2024;23(5):85-94. (In Russ.) https://doi.org/10.32517/2221-1993-2024-23-5-85-94

Views: 121


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


ISSN 2221-1993 (Print)