Задача сортировки массива. Простейшие алгоритмы сортировки: сортировка простым выбором, пузырьковая сортировка, сортировка вставками, сортировка подсчетом. Анализ простейших алгоритмов сортировки и сравнение их эффективности.
Рекурсия
Понятие рекурсии. Рекурсивные определения. Рекурсивные программы. Задача о ханойских башнях. Стратегии решения задач. Общий метод «разделяй и властвуй».
Более сложные алгоритмы сортировки
Рекурсивные алгоритмы сортировки массива: сортировка слиянием, быстрая сортировка. Анализ рекурсивных алгоритмов сортировки.
Простые структуры данных
Стек, определение и примеры. Представление стека линейным массивом. Очередь и ее кольцевое представление линейным массивом. Реализация операций над стеком и очередью на языке программирования. Применение стека и очереди при решении задач.
Линейные связные списки
Статическое и динамическое выделение памяти. Указатели (ссылки) и динамические переменные. Линейные связные списки (списки со связями). Операции над связными списками. Представление стека и очереди связным списком. Рекурсивные алгоритмы обработки списков. Кольцевые списки. Двунаправленные списки.
|
|
Двоичные деревья
Двоичные деревья поиска. Построение двоичного дерева. Оценка сложности алгоритмов поиска. Обход двоичного дерева. Рекурсивные алгоритмы обхода двоичных деревьев. Алгоритмы обхода, использующие стек и очередь. Полные деревья. Применение двоичных деревьев в задачах поиска и сортировки. Представление списков двоичными деревьями. Представление двоичного дерева с использованием массива.
Разработка алгоритмов и программ по технологии сверху-вниз
Формализованная запись алгоритма решения задачи. Пошаговая разработка и детализация алгоритмов и программ. Требования структурного программирования. Преимущества разработки и отладки программ по технологии сверху-вниз.
Ожидаемые результаты
После успешного прохождения учебного материала учащиеся получат представление:
- о разнообразии методов поиска и сортировки, о рекурсии;
- о методах анализа алгоритмов и критериях оценки их сложности;
- о приемах работы с базовыми структурами данных;
- об использовании динамических переменных;
- о разработке алгоритмов и программ по технологии сверху-вниз.
Изучение данного курса предполагает:
- развитие познавательных способностей школьников;
- формирование у них алгоритмического мышления;
- получение реального опыта творческой и исследовательской деятельности;
- повышение интереса учащихся к программированию.
Рекомендуемая литература
|
|
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 с.