Курс направлен на освоение моделей и методов
программного отображения на аппаратуру ЭВМ сложных математических моделей
(отображающих объекты некоторой проблемной области и операции над ними).
Излагаемый набор знаний и умений составляет теоретическую основу для
методов разработки сложных программ и включают такие темы, как концепция
структур данных, базовые структуры данных (включая стеки, очереди, связные
списки, хэш-таблицы, деревья и графы), объектно-ориентированная разработка
структур хранения данных, основы анализа алгоритмов, использование
рекурсии при построении алгоритмов. Изучение курса поддерживается
расширенным лабораторным практикумом.
Требования к слушателям: CS101 "Введение в методы
программирования", CS102 "Методы объектно-ориентированного
программирования", CS105 "Дискретная
математика".
Описание курса:
Концепция структур данных (объекты и операции)
Базовые структуры данных: стеки, очереди, связные списки,
хэш-таблицы, деревья, графы
Структуры хранения данных и их объектно-ориентированная разработка
Основные вычислительные алгоритмы: алгоритмы сортировки со
сложностью O(N logN), хэш-таблицы и алгоритмы исключения коллизий,
двоичные деревья поиска, представления графов, обходы в глубину и в
ширину
Рекурсия: понятие рекурсии, рекурсивные математические функции,
простые рекурсивные процедуры, стратегия "разделяй-и-властвуй",
рекурсивный перебор с возвратами, реализация рекурсии
Базовый анализ алгоритмов: асимптотический анализ наибольшей и
средней сложности; установление различии между лучшим, средним и худшим
случаями; О-большое и о-маленькое нотации; стандартные классы сложности;
эмпирические измерения характеристик исполнения; затраты по объему
памяти и времени; использование рекуррентных соотношений для анализа
рекурсивных алгоритмов
Обзор языков программирования: парадигмы программирования
Программная инженерия: разработка спецификаций, проектирование
структуры создаваемого программного обеспечения, поэтапная разработка,
проверка соответствия; основы тестирования, составление плана
тестирования и генерация тестовых пакетов; тестирование
объектно-ориентированных программ, подготовка документации
Затрагиваемые разделы (в соответствии с
рекомендациями CC 2001):
DS5 Графы и деревья 2 осн. часа ( из
4)
PF3 Основные структуры данных 12 осн. часов
(из 14)
PF4 Рекурсия 5 осн. часов (из 5)
AL1 Базовый анализ алгоритмов 2 осн. часа
(из 4)
AL2 Алгоритмические стратегии 3 осн. часа
(из 6)
AL3 Основные вычислительные алгоритмы 5 осн.
часов (из 12)
PL1 Обзор языков программирования 1 осн. час
(из 2)
PL6 Объектно-ориентированное
программирование 8 осн. часов (из 10)
SE6 Проверка соответствия ПО 1 осн. час (из
3)
Описание курса в соответствии со стандартом
направления 5119 "Информационные технологии":
ДМ1 Графы и деревья 2 осн. часа
ОП6 Объектно-ориентированное
программирование 8 осн. часов
ОП4 Основные структуры данных 12 осн.
часов
ОП5 Рекурсия 5 осн. часов
АЛ1 Базовый анализ алгоритмов 2 осн.
часа
АЛ2 Алгоритмические стратегии 3 осн.
часа
АЛ3 Основные вычислительные алгоритмы 5 осн.
часов