Пояснительная записка
Программа учебного предмета «Теория алгоритмов» разработана для учащихся 11
класса технологического профиля.
Программа раскрывает взаимосвязь математики и информатики, дает возможность
учащимся как отработать базовые алгоритмические конструкции, так и получить опыт
решения сложных типов алгоритмических задач.
Данная программа ориентирована на школьников, имеющих базовую подготовку по
информатике, желающих расширить свои знания о теории алгоритмов. Программа
способствует реализации индивидуальных образовательных интересов, потребностей и
склонностей учащихся, определения выбора будущей профессии.
Цель преподавания курса «Теория алгоритмов» для учеников 11 класса состоит в
том, чтобы помочь учащимся развить понимание основных понятий и принципов
алгоритмов, их реализацию и применение в решении задач различной сложности.
Задачи курса включают:
•
Изучение основных понятий и определений в области алгоритмов.
•
Ознакомление с классическими алгоритмами и структурами данных.
•
Разработка навыков анализа эффективности алгоритмов и оценки их
сложности.
•
Практическое применение изученных знаний при решении задач на
программирование.
•
Знакомство с современными технологиями и применение алгоритмов в
различных областях жизни.
Для достижения поставленных целей и задач в курсе будут использоваться
разнообразные
методы
обучения,
такие
как
лекции,
практические
задания,
самостоятельное изучение материала, а также работу с учебной литературой и
онлайнресурсами. Особое внимание будет уделено развитию у учеников логического
мышления, а также навыков работы с алгоритмами и структурами данных.
Программа рассчитана на 1 год обучения. Объем программы 34 часа по 1 часу в
неделю.
2
Содержание программы 11 класс
Знакомство с алгоритмами.
Введение в алгоритмы. Эффективность алгоритмов. Алгоритм бинарного поиска. Время
выполнения алгоритма. Асимптотическая сложность алгоритма. «О-большое». Анализ
сложности алгоритмов.
Рекурсия и методы сортировки.
Основные структуры данных: массивы и связанные списки. Как работает память. Операции
с массивами и связанными списками. Сортировка выбором. Уменьшение количества
проверяемых элементов.
Рекурсия: базовый и рекурсивный случай. Стек как структура данных LIFO («последним
пришел, первым вышел»). Стек вызовов. Стек вызовов с рекурсией. Стратегия «Разделяй
и властвуй». Алгоритмы сортировки слиянием и быстрой сортировки.
Хэш-таблицы, шаблонный поиск
Хэш-функции. Использование хэш-таблиц для поиска. Исключение дубликатов.
Использование хэш-таблицы как кэша. Область применения хэш-таблиц.
Графы, алгоритм Дейкстры
Граф как структура данных. Алгоритм поиска в ширину (путь с минимальным количеством
сегментов в невзвешенном графе). Очередь как структура данных FIFO («первым вошел,
первым вышел»). Реализация графа на языке Python. Взвешенные графы. Алгоритм
Дейкстры (алгоритм поиска кратчайшего пути во взвешенном графе).
Ребра с отрицательным весом. Алгоритм Беллмана-Форда.
Жадные алгоритмы, динамическое программирование
Понятие «жадного алгоритма» (локально-оптимальное решение) и его применение в
решении задач. Задачи, не имеющие быстрого алгоритмического решения (NP-полные
задачи). Алгоритмы нахождения приближенного решения. Признаки задачи, не имеющей
быстрого алгоритмического решения.
Динамическое программирование как метод решения задач оптимизации.
3
Алгоритм k-ближайших соседей
Системы классификации на базе алгоритма k-ближайших соседей. Извлечение признаков.
Регрессия. Знакомство с машинным обучением. OCR (оптическое распознавание текста).
Построение спам-фильтра.
ПЛАНИРУЕМЫЕ РЕЗУЛЬТАТЫ ОСВОЕНИЯ ПРОГРАММЫ ЛИЧНОСТНЫЕ
РЕЗУЛЬТАТЫ
Личностные
результаты
руководствоваться
ценностных
отражают
сформированной
ориентаций,
позитивных
готовность
внутренней
внутренних
и
способность
позицией
обучающихся
личности,
убеждений,
системой
соответствующих
традиционным ценностям российского общества, расширение жизненного опыта и опыта
деятельности в процессе реализации средствами
учебного предмета основных
направлений воспитательной деятельности. В результате изучения информатики на уровне
среднего общего образования у обучающегося будут сформированы следующие
личностные результаты:
1) гражданского воспитания: осознание своих конституционных прав и обязанностей,
уважение закона и правопорядка, соблюдение основополагающих норм информационного
права
и
информационной
безопасности;
готовность
противостоять
идеологии
экстремизма, национализма, ксенофобии, дискриминации по социальным, религиозным,
расовым, национальным признакам в виртуальном пространстве; 2) патриотического
воспитания: ценностное отношение к историческому наследию, достижениям России в
науке, искусстве, технологиях, понимание значения информатики как науки в жизни
современного общества;
3)
духовно-нравственного воспитания: сформированность нравственного сознания,
этического поведения; способность оценивать ситуацию и принимать осознанные
решения, ориентируясь на морально-нравственные нормы и ценности, в том числе в сети
Интернет;
4)
эстетического воспитания: эстетическое отношение к миру, включая эстетику
научного и технического творчества; способность воспринимать различные виды
искусства, в том числе основанного на использовании информационных технологий; 5)
физического воспитания: сформированность здорового и безопасного образа жизни,
ответственного отношения к своему здоровью, в том числе за счёт соблюдения требований
безопасной эксплуатации средств информационных и коммуникационных технологий;
4
6)
трудового воспитания: готовность к активной деятельности технологической и
социальной направленности, способность инициировать, планировать и самостоятельно
выполнять такую деятельность; интерес к сферам профессиональной деятельности,
связанным с информатикой, программированием и информационными технологиями,
основанными на достижениях науки информатики и научно-технического прогресса,
умение совершать осознанный выбор будущей профессии и реализовывать собственные
жизненные планы; готовность и способность к образованию и самообразованию на
протяжении всей жизни;
7)
экологического воспитания: осознание глобального характера экологических
проблем
и
путей
их
решения,
в
том
числе
с
учётом
возможностей
информационнокоммуникационных технологий;
8)
ценности
научного
познания:
сформированность
мировоззрения,
соответствующего современному уровню развития науки, достижениям научнотехнического
прогресса
и
общественной
практики,
за
счёт
понимания
роли
информационных ресурсов, информационных процессов и информационных технологий в
условиях цифровой трансформации многих сфер жизни современного общества;
осознание ценности научной деятельности, готовность осуществлять проектную и
исследовательскую деятельность индивидуально и в группе.
В процессе достижения личностных результатов освоения программы по информатике у
обучающихся
совершенствуется
эмоциональный
интеллект,
предполагающий
сформированность: саморегулирования, включающего самоконтроль, умение принимать
ответственность за своё поведение, способность адаптироваться к эмоциональным
изменениям и проявлять гибкость, быть открытым новому; внутренней мотивации,
включающей стремление к достижению цели и успеху, оптимизм, инициативность, умение
действовать, исходя из своих возможностей; эмпатии, включающей способность понимать
эмоциональное состояние других, учитывать его при осуществлении коммуникации,
способность к сочувствию и сопереживанию; социальных навыков, включающих
способность выстраивать отношения с другими людьми, заботиться, проявлять интерес и
разрешать конфликты.
МЕТАПРЕДМЕТНЫЕ РЕЗУЛЬТАТЫ
В результате изучения курса на уровне среднего общего образования у обучающегося
будут сформированы метапредметные результаты, отраженные в универсальных учебных
действиях,
а
именно
–
познавательные
универсальные
учебные
действия,
5
коммуникативные универсальные учебные действия, регулятивные универсальные
учебные действия, совместная деятельность.
Познавательные универсальные учебные действия
1)
базовые логические действия: самостоятельно формулировать и актуализировать
проблему, рассматривать её всесторонне; устанавливать существенный признак или
основания для сравнения, классификации и обобщения; определять цели деятельности,
задавать параметры и критерии их достижения; выявлять закономерности и противоречия
в рассматриваемых явлениях; разрабатывать план решения проблемы с учётом анализа
имеющихся материальных и нематериальных ресурсов; вносить коррективы в
деятельность, оценивать соответствие результатов целям, оценивать риски последствий
деятельности; координировать и выполнять работу в условиях реального, виртуального и
комбинированного взаимодействия; развивать креативное мышление при решении
жизненных проблем.
2)
базовые исследовательские действия: владеть навыками учебно-исследовательской
и проектной деятельности, навыками разрешения проблем, способностью и готовностью к
самостоятельному поиску методов решения практических задач, применению различных
методов познания; осуществлять различные виды деятельности по получению нового
знания, его интерпретации, преобразованию и применению в различных учебных
ситуациях, в том числе при создании учебных и социальных проектов; формировать
научный тип мышления, владеть научной терминологией, ключевыми понятиями и
методами; ставить и формулировать собственные задачи в образовательной деятельности
и жизненных ситуациях; выявлять причинно-следственные связи и актуализировать
задачу, выдвигать гипотезу её решения, находить аргументы для доказательства своих
утверждений, задавать параметры и критерии решения; анализировать полученные в ходе
решения задачи результаты, критически оценивать их достоверность, прогнозировать
изменение в новых условиях; давать оценку новым ситуациям, оценивать приобретённый
опыт; осуществлять целенаправленный поиск переноса средств и способов действия в
профессиональную среду; уметь переносить знания в познавательную и практическую
области жизнедеятельности; уметь интегрировать знания из разных предметных областей;
выдвигать новые идеи, предлагать оригинальные подходы и решения, ставить проблемы и
задачи, допускающие альтернативные решения.
3)
работа с информацией: владеть навыками получения информации из источников
разных типов, самостоятельно осуществлять поиск, анализ, систематизацию и
интерпретацию информации различных видов и форм представления; создавать тексты в
6
различных форматах с учётом назначения информации и целевой аудитории, выбирая
оптимальную
форму
представления
и
визуализации;
оценивать
достоверность,
легитимность информации, её соответствие правовым и морально-этическим нормам;
использовать средства информационных и коммуникационных технологий в решении
когнитивных, коммуникативных и организационных задач с соблюдением требований
эргономики, техники безопасности, гигиены, ресурсосбережения, правовых и этических
норм, норм информационной безопасности; владеть навыками распознавания и защиты
информации, информационной безопасности личности.
Коммуникативные универсальные учебные действия
1)
общение: осуществлять коммуникации во всех сферах жизни; распознавать
невербальные средства общения, понимать значение социальных знаков, распознавать
предпосылки конфликтных ситуаций и смягчать конфликты; владеть различными
способами общения и взаимодействия, аргументированно вести диалог, уметь смягчать
конфликтные ситуации; развёрнуто и логично излагать свою точку зрения с
использованием языковых средств.
2)
совместная деятельность: понимать и использовать преимущества командной и
индивидуальной работы; выбирать тематику и методы совместных действий с учётом
общих интересов и возможностей каждого члена коллектива; принимать цели совместной
деятельности, организовывать и координировать действия по их достижению: составлять
план действий, распределять роли с учётом мнений участников, обсуждать результаты
совместной работы; оценивать качество своего вклада и каждого участника команды в
общий результат по разработанным критериям; предлагать новые проекты, оценивать идеи
с позиции новизны, оригинальности, практической значимости; осуществлять позитивное
стратегическое поведение в различных ситуациях, проявлять творчество и воображение,
быть инициативным.
Регулятивные универсальные учебные действия
1)
самоорганизация: самостоятельно осуществлять познавательную деятельность,
выявлять проблемы, ставить и формулировать собственные задачи в образовательной
деятельности и жизненных ситуациях; самостоятельно составлять план решения проблемы
с учётом имеющихся ресурсов, собственных возможностей и предпочтений; давать оценку
новым ситуациям; расширять рамки учебного предмета на основе личных предпочтений;
делать осознанный выбор, аргументировать его, брать ответственность за решение;
оценивать приобретённый опыт; способствовать формированию и проявлению широкой
7
эрудиции в разных областях знаний, постоянно повышать свой образовательный и
культурный уровень.
2)
самоконтроль:
деятельность,
давать
оценивать
оценку
новым
соответствие
ситуациям,
результатов
вносить
целям;
коррективы
владеть
в
навыками
познавательной рефлексии как осознания совершаемых действий и мыслительных
процессов, их результатов и оснований, использовать приёмы рефлексии для оценки
ситуации, выбора верного решения; оценивать риски и своевременно принимать решения
по их снижению; принимать мотивы и аргументы других при анализе результатов
деятельности.
3)
принятия себя и других: принимать себя, понимая свои недостатки и достоинства;
принимать мотивы и аргументы других при анализе результатов деятельности; признавать
своё право и право других на ошибку; развивать способность понимать мир с позиции
другого человека.
ПРЕДМЕТНЫЕ РЕЗУЛЬТАТЫ
Предметные результаты включают в себя: освоенные обучающимися в ходе
изучения учебного предмета умения специфические для данной предметной области, виды
деятельности по получению нового знания в рамках учебного предмета, его
преобразованию и применению в учебных, учебно-проектных и социально-проектных
ситуациях, формирование научного типа мышления, научных представлений о ключевых
теориях, типах и видах отношений, владение научной терминологией, ключевыми
понятиями, методами и приемами. Основные предметные результаты отражают:
− формирование информационной и алгоритмической культуры;
− формирование представления об основных изучаемых понятиях: информация, алгоритм,
модель – и их свойствах;
−
развитие
алгоритмического
мышления,
необходимого
для
профессиональной
деятельности в современном обществе; развитие умений составить и записать алгоритм для
конкретного исполнителя; формирование знаний об алгоритмических конструкциях, −
формирование умений формализации и структурирования информации, умения выбирать
способ представления данных в соответствии с поставленной задачей, с использованием
соответствующих программных средств обработки данных;
- освоение методов теории алгоритмов, алгоритмизации и оптимизации алгоритмов.
8
Тематическое планирование
Номер
темы
Кол-во
часов
Название темы
теория практика
11 класс
1.
Знакомство с алгоритмами
3
1
2
2.
Рекурсия и методы сортировки
8
2
6
3.
Хэш-таблицы, шаблонный поиск
3
1
2
4.
Графы, алгоритм Дейкстры
8
2
6
5.
Жадные
алгоритмы,
программирование
8
2
6
6.
Алгоритм k-ближайших соседей
4
34
2
10
2
24
динамическое
Итого
9
Поурочное планирование
11класс (34 часа)
№
Тема разделов, занятий
Количество часов
Количество
часов
Теория
Практика
Знакомство с алгоритмами
3
1
2
1.
Введение в алгоритмы. Эффективность алгоритмов. Алгоритм бинарного поиска
1
1
2.
Время выполнения алгоритма. Асимптотическая сложность алгоритма
1
1
Практикум по решению задач
1
1
Рекурсия и методы сортировки
8
2
4.
Основные структуры данных: массивы и связанные списки. Как работает память
1
1
5.
Операции с массивами и связанными списками
1
1
6.
Сортировка выбором. Уменьшение количества проверяемых элементов
1
1
7.
Рекурсия: базовый и рекурсивный случай. Стек как структура данных LIFO
1
«О-большое». Анализ сложности алгоритмов
3.
6
1
(«последним пришел, первым вышел»)
8.
Стек вызовов. Стек вызовов с рекурсией
1
1
9.
Стратегия «Разделяй и властвуй». Алгоритмы сортировки слиянием и быстрой
сортировки
1
1
10.
Практикум по решению задач
1
1
11.
Практикум по решению задач
1
1
Хэш-таблицы, шаблонный поиск
3
1
2
10
12.
Хэш-функции. Использование хэш-таблиц для поиска
1
13.
Исключение дубликатов. Использование хэш-таблицы как кэша. Область
применения хэш-таблиц
1
1
14.
Практикум по решению задач
1
1
Графы, алгоритм Дейкстры
8
2
15.
Граф как структура данных
1
1
16.
Алгоритм поиска в ширину (путь с минимальным количеством сегментов в
невзвешенном графе)
1
1
17.
Очередь как структура данных FIFO («первым вошел, первым вышел»).
1
1
1
6
Реализация графа на языке Python
18.
Взвешенные графы. Алгоритм Дейкстры (алгоритм поиска кратчайшего пути во
взвешенном графе)
1
19.
Практикум по решению задач
1
1
20.
Практикум по решению задач
1
1
21.
Ребра с отрицательным весом. Алгоритм Беллмана-Форда
1
1
22.
Практикум по решению задач
1
1
Жадные алгоритмы, динамическое программирование
8
2
23.
Понятие «жадного алгоритма» (локально-оптимальное решение) и его применение
в решении задач
1
1
24.
Задачи, не имеющие быстрого алгоритмического решения (NP-полные задачи)
1
1
25.
Алгоритмы нахождения приближенного решения. Признаки задачи, не имеющей
быстрого алгоритмического решения
1
1
1
6
11
26.
Практикум по решению задач
1
27.
Динамическое программирование как метод решения задач оптимизации
1
28.
Практикум по решению задач
1
1
29.
Практикум по решению задач
1
1
30.
Практикум по решению задач
1
1
Алгоритм k-ближайших соседей
4
2
31.
Системы классификации на базе алгоритма k-ближайших соседей. Извлечение
признаков. Регрессия.
1
1
32.
Практикум по решению задач
1
33.
Знакомство с машинным обучением. OCR (оптическое распознавание текста).
1
1
1
2
1
1
Построение спам-фильтра.
34.
Практикум по решению задач
1
1
12
Литература
1.
Информтаика (базовый и углубленный уровни) (в 2 частях) 11класс /К.Ю. Поляков
и др. – М.: Бином. Лаборатория знаний, 2019)
2.
Информтаика (базовый и углубленный уровни) (в 2 частях) 10класс /К.Ю. Поляков
и др. – М.: Бином. Лаборатория знаний, 2019)
3.
Грокаем
алгоритмы.
Иллюстрированное
пособие
для
программистов
любопытствующих. – СПБ.: Питер, 2024 (Серия «Библиотека программиста»)
Список ЭОР
1. Официальный
сайт
Федерального
института
педагогических
измерений http://www.fipi.ru/
2. Преподавание, наука и жизнь: сайт К. Полякова http://kpolyakov.spb.ru/
3. Библиотека ЦОК https://m.edsoo.ru/
4. Российская электронная школа https: //resh.edu.ru/subject/19/10/
5. Яндекс.Учебник
https://education.yandex.ru
и
