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

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

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

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

Часть I

  1. Буква, символ, алфавит; кодирование и кодировки до Unicode.
  2. Unicode: пространство символов; модификаторы; нормализация; сравнение; кодировки.
  3. Абсолютная и относительная погрешности; позиционные системы счисления.
  4. Дополнительный код.
  5. Симметричные системы счисления.
  6. Троичные арифметика и логика.
  7. Числа с плавающей запятой; нормализация.
  8. Распределение чисел с плавающей запятой.
  9. Комплексные числа, распределение разных представлений.
  10. Назначение линейных контейнеров; преимущества и недостатки массивов.
  11. Массивы; представление многомерных массивов при помощи векторов Айлифа.
  12. Преимущества и недостатки списков; способы реализации списков; оптимизация работы списков: блочные списки.
  13. Оптимизация работы списков: шитые и иерархические списки; Zipper, стек, очередь и дек на основе списков.
  14. Назначение, преимущества и недостатки деревьев.
  15. AVL - деревья.
  16. B - деревья.

Часть II

  1. R - деревья.
  2. Красно-черные деревья.
  3. Декартовы деревья.
  4. Представления графов.
  5. Хеш-таблицы: назначение, подходы к расширению, преимущества и недостатки перед деревьями.
  6. Хеш-функции: требуемые свойства, примеры.
  7. Распределенные хеш-таблицы.
  8. Строки; представление строк при помощи массивов, списков и деревьев (ациклических графов).
  9. Назначение кучи; куча для элементов одинакового размера.
  10. Тривиальная организация кучи; дефрагментация.
  11. Оптимизация дефрагментации методом граничных маркеров.
  12. Генетические алгоритмы.
  13. Вдумчивые и конструктивные замечания по программе курса.
  14. Представление контекста вложенных процедур при помощи цепочек фреймов и мониторов.
  15. Передача процедур "вниз" по цепочке вызовов; поддержание статической цепочки.
  16. Произвольная передача замыканий (процедур с контекстом) с копированием или динамическим выделением контекста.

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

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