2018-01-08
959
Задача сортировки массива. Простейшие алгоритмы сортировки: сортировка простым выбором, пузырьковая сортировка, сортировка вставками, сортировка подсчетом. Анализ простейших алгоритмов сортировки и сравнение их эффективности.
Рекурсия
Понятие рекурсии. Рекурсивные определения. Рекурсивные программы. Задача о ханойских башнях. Стратегии решения задач. Общий метод «разделяй и властвуй».
Более сложные алгоритмы сортировки
Рекурсивные алгоритмы сортировки массива: сортировка слиянием, быстрая сортировка. Анализ рекурсивных алгоритмов сортировки.
Простые структуры данных
Стек, определение и примеры. Представление стека линейным массивом. Очередь и ее кольцевое представление линейным массивом. Реализация операций над стеком и очередью на языке программирования. Применение стека и очереди при решении задач.
Линейные связные списки
Статическое и динамическое выделение памяти. Указатели (ссылки) и динамические переменные. Линейные связные списки (списки со связями). Операции над связными списками. Представление стека и очереди связным списком. Рекурсивные алгоритмы обработки списков. Кольцевые списки. Двунаправленные списки.
Двоичные деревья
Двоичные деревья поиска. Построение двоичного дерева. Оценка сложности алгоритмов поиска. Обход двоичного дерева. Рекурсивные алгоритмы обхода двоичных деревьев. Алгоритмы обхода, использующие стек и очередь. Полные деревья. Применение двоичных деревьев в задачах поиска и сортировки. Представление списков двоичными деревьями. Представление двоичного дерева с использованием массива.
Разработка алгоритмов и программ по технологии сверху-вниз
Формализованная запись алгоритма решения задачи. Пошаговая разработка и детализация алгоритмов и программ. Требования структурного программирования. Преимущества разработки и отладки программ по технологии сверху-вниз.
Ожидаемые результаты
После успешного прохождения учебного материала учащиеся получат представление:
- о разнообразии методов поиска и сортировки, о рекурсии;
- о методах анализа алгоритмов и критериях оценки их сложности;
- о приемах работы с базовыми структурами данных;
- об использовании динамических переменных;
- о разработке алгоритмов и программ по технологии сверху-вниз.
Изучение данного курса предполагает:
- развитие познавательных способностей школьников;
- формирование у них алгоритмического мышления;
- получение реального опыта творческой и исследовательской деятельности;
- повышение интереса учащихся к программированию.
Рекомендуемая литература
1. Абрамов С. А. Математические построения и программирование / С. А. Абрамов. — М.: Наука, 1978. — 191 с.
2. Ахо А. В. Структуры данных и алгоритмы / А. В. Ахо, Д. Хопкрофт, Д. Д. Ульман. — М.: Издательский дом «Вильямс», 2000. — 384 с.
3. Бакнелл Дж. Фундаментальные алгоритмы и структуры данных в Delphi / Дж. Бакнелл. — СПб: ООО «ДиаСофтЮП», 2003. — 560 с.
4. Бентли Д. Жемчужины программирования / Д. Бентли. — СПб: Питер, 2002. — 272 с.
5. Вирт Н. Алгоритмы + структуры данных = программы / Н. Вирт. — М.: Мир, 1985. — 406 с.
6. Касьянов В. Н. Курс программирования на Паскале в заданиях и упражнениях / В. Н. Касьянов. — Новосибирск: Из-во НГУ, 2001. — 448 с.
7. Катков В. Л. Программирование / В. Л. Катков, Э. З. Любимский. — Мн.: Вышэйшая школа, 1992. — 295 с.
8. Кормен Т. Х. Алгоритмы: построение и анализ / Т. Х. Кормен, Ч. И. Лейзерсон, Р. Л. Ривест. — М.: МЦНМО, 2000. — 960 с.
9. Котов В. М. Информатика. Методы алгоритмизации / В. М. Котов, О. И. Мельников. — Мн.: Народная асвета, 2000. — 221 с.
10. Котов В. М. Структуры данных и алгоритмы: теория и практика / В. М. Котов, Е. П. Соболевская. — Мн.: БГУ, 2004. — 255 с.
11. Макконелл Дж. Основы современных алгоритмов / Дж. Макконелл. — М.: Техносфера, 2004. — 368 с.
12. Окулов С. М. Основы программирования / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2005. — 440 с.
13. Окулов С. М. Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. — 341 с.
14. Стивенс Р. Delphi. Готовые алгоритмы / Р. Стивенс. — М.: ДМК Пресс, 2004. — 384 с.
