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

02.03.01, Математика и компьютерные науки

Внимание!

Осторожно! У вас ведёт занятие преподаватель кафедры системного программирования СПбГУ, но ваша группа вероятно ещё не заполняла опрос «Давайте познакомимся»? Это очень опасная ситуация.

Не ждите, пока (и если) преподаватель скажет. Заполняйте!

Материалы

Вопросы по курсу

2019 год

Часть 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.
  • Тоби Сегаран. Программируем коллективный разум: [пер. с англ.] // М. — Символ-Плюс, 2008, 368 с.
  • Кузнецов С. Д. Методы сортировки и поиска. ИСП РАН, Центр Информационных Технологий.
  • Материалы лектора: приложение к данной странице; кому-то может показаться, что это лучше, чем ничего.

Темы для докладов

Учебный план подразумевает по две лекции в неделю в течение 4 семестров. Всё это время сидеть и слушать не полезно для психического здоровья. Поэтому предлагается сделать ряд докладов.

  1. Длинный доклад. Unums & Posits. Объяснить, как (и для чего) хранятся числа в форматах Unum и Posit, попробовать хотя бы одну реализацию, продемонстрировать отличия в работе от IEEE-754.
  2. Короткий доклад. Высота несбалансированного дерева поиска. Доходчиво и внятно изложить материал по ссылке.
  3. Короткий доклад. Расширяющиеся деревья. D.D. Sleator, R.E. Tarjan. Self-Adjusting Binary Search Trees // Journal of the ACM. 32 (3) 1985, P. 652–686.