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

Оглавление

1 Общая информация
2 Вопросы по курсу (2011 год)
3 Источники информации

Общая информация

Программная инженерия

Объем курса	1/2 года (1 сем, 1 лекция в неделю)
Отчётность	теоретический экзамен
Направление	231000, программная инженерия
Семестр	II (1 курс, весна)
Код дисциплины	CS103
Трудоёмкость	3 зачётных единицы

Информационные технологии

Объем курса	1/2 года (1 сем, 1 лекция в неделю)
Отчётность	теоретический экзамен
Направление	010400, информационные технологии
Семестр	IV (2 курс, весна)
Код дисциплины	CS103
Трудоёмкость	3 зачётных единицы

Вопросы по курсу (2011 год)

Часть I

Буква, символ, алфавит; кодирование и кодировки до Unicode.
Unicode: пространство символов; модификаторы; нормализация; сравнение; кодировки.
Абсолютная и относительная погрешности; позиционные системы счисления; дополнительный код.
Симметричные системы; троичные арифметика и логика.
Числа с плавающей запятой; нормализация; распределение.
Комплексные числа, распределение разных представлений.
Назначение линейных контейнеров; преимущества и недостатки массивов.
Преимущества и недостатки списков; способы реализации списков; оптимизация работы списков: шитые и иерархические списки.
Назначение, преимущества и недостатки деревьев.
AVL - деревья.
B - деревья.
R - деревья.
Красно-черные деревья.
Декартовы деревья.
Представления графов.

Часть II

Хеш-таблицы: назначение, подходы к расширению, преимущества и недостатки перед деревьями.
Хеш-функции: требуемые свойства, примеры.
Распределенные хеш-таблицы.
Строки; представление строк при помощи массивов, списков и деревьев (ациклических графов).
Назначение кучи; куча для элементов одинакового размера.
Тривиальная организация кучи; дефрагментация.
Таблица виртуальных методов при одиночном наследовании.
Таблица виртуальных методов и смещений для невиртуального множественного наследования.
Таблица виртуальных методов и смещений для виртуального множественного наследования.
Виртуальные таблицы для одиночного наследования и множественной реализации интерфейсов.
Виртуальные таблицы для динамических языков.
Распараллеливание алгоритмов на примере сортировок с и без использования дополнительной памяти; ускорение и эффективность, распараллеливание и оптимизация умножения квадратных матриц.
Жадные и динамические алгоритмы.
Генетические алгоритмы.
Вдумчивые и конструктивные замечания по программе курса.

Не выносится на экзамен

Массивы; представление многомерных массивов при помощи векторов Айлифа.
Представление контекста вложенных процедур при помощи цепочек фреймов и мониторов.
Передача процедур "вниз" по цепочке вызовов; поддержание статической цепочки.
Произвольная передача замыканий (процедур с контекстом) с копированием или динамическим выделением контекста.
Оптимизация дефрагментации методом граничных маркеров.
Метод двоичных близнецов.

Источники информации

Конспект.
Дж. Д. Ульман А. В. Ахо, Дж. Э. Хопкрофт. Структуры данных и алгоритмы. Издательский дом «Вильямс», 2000.
Дональд Э. Кнут. Искусство Программирования. Издательский дом «Вильямс», 2000.
Томас Кормен, Чарльз Лейзерсон, Рональд Ривест. Алгоритмы: построение и анализ. М.: МЦНМО, 1999.
Кубенский А. А. Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++. СПб.: БХВ-Петербург, 2004.
Кузнецов С. Д. Методы сортировки и поиска. ИСП РАН, Центр Информационных Технологий.
Материалы лектора: