Научно-методическое учреждение
«Национальный институт образования»
Министерства образования Республики Беларусь
Учебная программа
факультативных занятий
«МЕТОДЫ АЛГОРИТМИЗАЦИИ»
по учебному предмету «Информатика»
Минск
Автор-составитель:
, профессор, доктор физико-математических наук, заведующий кафедрой дискретной математики и алгоритмики БГУ.
Предлагаемый курс факультативных занятий направлен на обучение учащихся методам построения и анализа алгоритмов и использования различных структур данных. Программа расширяет и углубляет знания учащихся в области программирования и основ алгоритмизации. При работе по данной программе учащиеся должны знать основы языка программирования.
Факультативные занятия рассчитаны на работу в течение одного года по 2 часа в неделю. Порядок изучения тем учитель может изменить в соответствии с подготовленностью учащихся.
Пояснительная записка
Данная программа расширяет и углубляет знания и умения учащихся в области теории построения и записи алгоритмов решения практических задач, знакомит с методологией и технологией программирования, имеет алгоритмическую направленность. При работе по данной программе учащиеся должны знать основы языка программирования.
Учебная программа факультативных занятий соответствует содержательной линии «Основы алгоритмизации и программирования» учебного предмета «Информатика».
Программа имеет системно-информационный характер. Целью программы является формирование у учащихся системно-информационного взгляда на мир, включающего абстрагирование, моделирование, и алгоритмическое мышление, а также умений, обеспечивающих возможность построения алгоритмов различной степени сложности и использования структур данных.
Успешное освоение материалов предлагаемых факультативных занятий будет способствовать успешному решению задач повышенной сложности по информатике, в частности олимпиадных задач.
ЦЕЛИ И ЗАДАЧИ ФАКУЛЬТАТИВНЫХ ЗАНЯТИЙ
Предлагаемый курс факультативных занятий преследует следующую цель:
формирование основ научного мировоззрения путем расширения объема необходимых знаний в области построения алгоритмов и структур данных;
Задачи данных факультативных занятий:
· систематизировать и углубить знания и умения учащихся в области теоретических понятий информатики;
· изучить основные способы построения алгоритмов;
· формировать основы рационального подхода к решению задач путем анализа известных алгоритмов и разработки новых;
· формировать умения учащихся в использовании различных структур данных для решения задач;
· обучить учащихся анализу сложности и правильности алгоритмов;
· обучить учащихся тестированию программ;
· развивать логического и алгоритмического мышления учащихся;
· развивать интерес к изучению информатики и программирования.
Отбор содержания программы соответствует тематике наиболее распространенных способов построения и анализа алгоритмов.
Рекомендуемые формы и методы проведения занятий
Результат решения задач предлагаемого курса во многом зависит от организации учебного процесса. Обучение предполагает, прежде всего, наполнение учебного материала заданиями различного уровня сложности. Одни из них служат для закрепления пройденного материала, в других модифицируются рассматриваемые алгоритмы и реализуются изученные структуры данных.
В учебном процессе должно быть уделено особое внимание самостоятельной работе учащихся – самостоятельному решению заданий, проработке дополнительного учебного материала, разработке алгоритмов решения задач и их реализации в конкретной среде программирования. .
Выбор языка программирования и среды программирования остается за учителем. Однако, наиболее оптимальными вариантами следует считать язык Pascal в среде FreePascal или язык С++ в среде DevC++.
Ожидаемые результаты
После успешного прохождения учебного материала учащиеся получат представление:
- о разнообразии задач, решаемых с использованием языка программирования;
- о методах решения задач;
- о разработке алгоритмов решения задач;
- об оценке сложности алгоритмов;
- о тестировании задач.
Изучение данного курса предполагает:
- развитие познавательных способностей школьников;
- формирование у них алгоритмического мышления;
- получение реального опыта творческой и исследовательской деятельности;
- повышение интереса учащихся к программированию и «спортивному программированию».
Содержание
(70 часов)
РАЗДЕЛ 1. ТИПЫ И СТРУКТУРЫ ДАННЫХ
Представление информации в компьютере. Представление целых чисел: стандартное, в виде полиномов, в виде: разложения на множители Способы реализации арифметических операций при различных представлениях. Приближения вещественных чисел в виде рациональных дробей. Решение задач
Структуры данных. Основные структуры данных, способы их организации, реализация базовых операций. Представлений и использование приоритетных очередей. Представление и использование множеств.
Представление геометрических объектов. Представление прямой, отрезка о определение их взаимного расположения. Определение расстояний между геометрическими объектами. Многоугольники, их характеристики. Решение задач
РАЗДЕЛ 2. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВ
Графовые модели. Основные понятия, основные способы представления. Основные алгоритмы поиска в графах (поиск в ширину и глубину) Алгоритмы поиска кратчайших путей. Использование алгоритмов поиска для определения компонент связности графа. Алгоритмы построения остовных деревьев. Топологическая сортировка. Потоки в графах. Алгоритмы построения максимального потока. Решение задач.
Рекуррентные соотношения. Понятие рекуррентного уравнения, понятие задачи и подзадачи. Основные этапы при построении эффективных алгоритмов: сведение задачи к подзадачам. Особенности методов «Разделяй и властвуй» и динамического программирования и алгоритмов их реализации. Параметризация исходной задачи. Определение существенных параметров, запись рекуррентного уравнения и определение начальных данных. Порядок вычисления значения функций. Рекурсивный и не рекурсивные алгоритмы. Методы восстановления решений. Решение задач.
Элементы комбинаторики и организация перебора. Алгоритмы построения перестановок, сочетаний. Алгоритм поиска с возвратом как основа для организации перебора. Методы сокращения перебора. Методы сокращения перебора. Решение задач.
планирование
Предлагаемое планирование является примерным. Количество часов на изучение темы может быть изменено. Планирование рассчитано на 2 часа в неделю.
1. Цели и задачи курса (2 часа).
РАЗДЕЛ 1. ТИПЫ И СТРУКТУРЫ ДАННЫХ
Представление информации в компьютере (10 часов)
2. Представление целых чисел: стандартное, в виде полиномов.
3. Представление целых чисел в виде: разложения на множители.
4. способы реализации арифметических операций при различных представлениях.
5. Приближения вещественных чисел в виде рациональных дробей
6. Решение задач.
Структуры данных (8 часов)
7. Основные структуры данных, способы их организации.
8. Реализация базовых операций.
9. Представлений и использование приоритетных очередей.
10. Представление и использование множеств.
Представление геометрических объектов (8 часов)
11. Представление прямой, отрезка о определение их взаимного расположения.
12. Определение расстояний между геометрическими объектами
13. Многоугольники, их характеристики.
14. Решение задач.
РАЗДЕЛ 2. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВ
Графовые модели (16 часа)
15. Основные понятия, основные способы представления.
16. Основные алгоритмы поиска в графах (поиск в ширину и глубину)
17. Алгоритмы поиска кратчайших путей
18. Использование алгоритмов поиска для определения компонент связности графа.
19. Алгоритмы построения остовных деревьев.
20. Топологическая сортировка.
21. Потоки в графах. Алгоритмы построения максимального потока.
22. Решение задач.
Рекуррентные соотношения (14 часов)
23. Понятие рекуррентного уравнения, понятие задачи и подзадачи
24. Основные этапы при построении эффективных алгоритмов: сведение задачи к подзадачам.
25. Особенности методов «Разделяй и властвуй» и динамического программирования и алгоритмов их реализации.
26. Параметризация исходной задачи. Определение существенных параметров, запись рекуррентного уравнения и определение начальных данных.
27. Порядок вычисления значения функций. Рекурсивный и не рекурсивные алгоритмы.
28. Методы восстановления решений.
29. Решение задач.
Элементы комбинаторики и организация перебора(10 часов)
30. Алгоритмы построения перестановок, сочетаний.
31. Алгоритм поиска с возвратом как основа для организации перебора.
32. Методы сокращения перебора.
33. Решение задач.
34. Резерв.
Основная литература
для учащихся
1. Котов . Методы алгоритмизации. / , , . – Мн. ИГП Нар. асвета,2000г. – 300с.
2. Котов алгоритмизации. / , , . – Мн.-Нар. асвета, 1997г. – 126с.
3. Котов алгоритмизации. / , , . – Мн. ИГП Нар. асвета,1997г. – 160с.
4. Котов алгоритмизации. / , . – Мн. ИГП Нар. асвета,2000г. – 220с.
для учителей
5. Андреева олимпиады по информатике. Под редакцией , , . – М, Издательство МЦНМО 2006. – 255с
6. Гуровиц учебно-тренировочные сборы по информатике. Весна -2006 / Под ред. – М: МЦНМО, 2007. – 194 с.
7. Долинский сложных и олимпиадных задач по программированию./ . – Питер 2006. – 365с.
8. . Алгоритмизация и программирование на Turbo Pascal от простых до олимпиадных задач. / . – Питер 2005. – 236с.
9. Олимпиадные задачи по программированию. / Ф. Меньшиков. – Питер 2006. – 314с.
10. Окулов С. М. Основы программирования / С. М. Окулов. – М.: БИНОМ. Лаборатория знаний, 2005. – 440 с.
11. Окулов в алгоритмах. / . – М.: "БИНОМ. Лаборатория знаний", 2004. – 341 с..
12. Порублев и программы. Решение олимпиадных задач / , – М. . Д. Вильямс», 2007. – 480с.
13. Радион по информатике. Задачи. Решения. Тесты. / . Мн. Аверсев. 2007.– 366с.
Дополнительная литература
14. Бакнел. Д. Фундаментальные алгоритмы и структуры данных в Delphi. Библиотека программиста / Джулиан Бакнел. – М.: ; СПб.: Питер, 2006. – 557 с.
15. Кормэн : построение и анализ / , , Р. Л. Ривест. — М.: МЦНМО, 2000. — 960 с.
16. Олимпиадные задачи по программированию. / Скиена, Ревила, М. Кудиц-Образ, 2005. – 416с.
17. Delphi. Готовые алгоритмы. / Р. Стивенс. – Питер, ДМК, 2004. – 378с.
ИНТЕРНЕТ ИСТОЧНИКИ
18. Олимпиады по информатике, Санкт-Петербург: http://neerc. ifmo. ru/school
19. Олимпиадная информатика: http://olympiads. ru/
20. Школьные олимпиады по программированию в Минске
http://oi-minsk. narod. ru/
21. Белорусский сайт дистанционного обучения: http://dl.
22. Дистанционная подготовка по информатике: http://informatics. mccme. ru/
23. Сайт Югорского НИИ ИТ с большим архивом задач, распределенных по темам: http://www. acmu. ru
24. Украинские олимпиады по информатике: http://www. uoi.
