Кафедра Математического обеспечения ЭВМО кафедреПреподаватели и сотрудникиГергель Виктор Павлович
Новости
О кафедре
Преподаватели и сотрудники
Структура
Немного истории
Контакты
Фотохроника
Обучение
Исследования
Семинары и конференции
Сотрудничество
О сайте
Имя:
Пароль:
запомнить:
Забыли пароль? Регистрация

Гергель Виктор Павлович

CS103. Алгоритмы и структуры данных

Курс направлен на освоение моделей и методов программного отображения на аппаратуру ЭВМ сложных математических моделей (отображающих объекты некоторой проблемной области и операции над ними). Излагаемый набор знаний и умений составляет теоретическую основу для методов разработки сложных программ и включают такие темы, как концепция структур данных, базовые структуры данных (включая стеки, очереди, связные списки, хэш-таблицы, деревья и графы), объектно-ориентированная разработка структур хранения данных, основы анализа алгоритмов, использование рекурсии при построении алгоритмов. Изучение курса поддерживается расширенным лабораторным практикумом.

Требования к слушателям: 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 осн. часов 
  • ЯП1   Обзор языков программирования   1 осн. час 
  • ИН4   Проверка соответствия ПО   1 осн. час

 

Учебные материалы


<< вернуться  |   Документ от: 11.07.2005 18:00

Новости

28.04.2014
21.04.2014
21.03.2014
12.01.2014
04.10.2013