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

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

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

Внимание!

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

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

Материалы

Мультимедиа

Слайды

Слайды по ссылкам практически точно совпадают с теми, которые показываются на лекциях

  1. От символов к байтам

  2. Числа: точность, неотрицательные системы счисления, дополнительный код

  3. Числа с плавающей запятой: представление, распределение; комплексные числа

  4. Булева и многозначные логики; cимметричные системы счисления; троичная информатика

  5. Линейные контейнеры

  6. Бинарные деревья

  7. Сильно ветвящиеся деревья

  8. Хэш-функции и хэш-таблицы

  9. Куча

  10. Строки

  11. Эволюционные алгоритмы

  12. Стек. Динамическая и статическая цепочки

  13. Классификаторы

Задания и примеры

Опубликованы здесь

Темы практических занятий

  1. Кодировки: современные, несовременные, экзотические. Кодировки в программах на Python и C

  2. Collation в Unicode для разных языков

  3. Проверка типов и magic-методы в Python

  4. Плавающая запятая IEEE-754 и Posits

  5. Нечёткие логики; модульные тесты

  6. Производительность массивов в Python. Неблокирующие операции ввода-вывода и GUI

  7. Высота случайных деревьев; визуализация графов

  8. О распределённых хэш-таблицах

  9. Скорость работы кучи

  10. Скорость и возможности реализаций статических цепочек для разных языков

  11. Совсем немного нейронных сетей и чуть больше нейронных сетей. И ещё чуть-чуть, и ещё чуть-чуть.

Вопросы к зачёту и экзамену, весна 2020

Часть I

  1. Буква, символ, алфавит; кодирование и кодировки до Unicode.

  2. Unicode: пространство символов; модификаторы; нормализация; сравнение; кодировки.

  3. Абсолютная и относительная погрешности; позиционные системы счисления.

  4. Дополнительный код.

  5. Симметричные системы счисления.

  6. Троичные арифметика и логика.

  7. Числа с плавающей запятой; нормализация.

  8. Распределение чисел с плавающей запятой.

  9. Комплексные числа, распределение разных представлений.

  10. Назначение линейных контейнеров; преимущества и недостатки массивов.

  11. Массивы; представление многомерных массивов при помощи векторов Айлифа.

  12. Преимущества и недостатки списков; способы реализации списков; оптимизация работы списков: блочные списки.

  13. Оптимизация работы списков: шитые и иерархические списки; Zipper, стек, очередь и дек на основе списков.

  14. Назначение, преимущества и недостатки деревьев.

  15. AVL - деревья.

  16. Красно-черные деревья.

Часть II

  1. Декартовы деревья.

  2. Интервальные деревья.

  3. B - деревья.

  4. R - деревья.

  5. Представления графов.

  6. Хеш-функции: требуемые свойства «хороших» функций, примеры использования.

  7. «Плохие» хэш-функции, их использование.

  8. Хеш-таблицы: назначение, преимущества и недостатки перед деревьями, подходы к перестройке расширению.

  9. Распределенные хеш-таблицы.

  10. Строки; представление строк при помощи массивов, списков и деревьев (ациклических графов).

  11. Назначение кучи; куча для элементов одинакового размера.

  12. Тривиальная организация кучи; фрагментация и дефрагментация.

  13. Оптимизация дефрагментации методом граничных маркеров.

  14. Метод двоичных близнецов.

  15. Генетические алгоритмы.

  16. Вдумчивые и конструктивные замечания по программе курса.

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

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

  1. ~20 мин. Python typing & Abstract Base Classes. Объяснить, зачем они нужны, и что они дают программисту на Python.

  2. ~20 мин. Реализация целочисленной арифметики с использованием обратного кода.

  3. ~40–50 мин. Unums & Posits. Объяснить, как (и для чего) хранятся числа в форматах Unum и Posit, попробовать хотя бы одну реализацию, продемонстрировать отличия в работе от IEEE-754.

  4. ~20 мин. Реализация Deque на основе неизменяемых структур данных. Можно пользоваться Википедией, но желательно копнуть глубже.

  5. ~20 мин. Высота несбалансированного дерева поиска. Доходчиво и внятно изложить материал по ссылке.

  6. ~20 мин. Расширяющиеся деревья. D.D. Sleator, R.E. Tarjan. Self-Adjusting Binary Search Trees // Journal of the ACM. 32 (3) 1985, P. 652–686.

Рекомендованные онлайн-курсы

  • На первый семестр Data Structures University of California San Diego; National Research University Higher School of Economics

  • На все семестры Data Structures and Algorithms University of California San Diego; National Research University Higher School of Economics

Список литературы и не литературы

  • Конспект.

  • Дж. Д. Ульман А. В. Ахо, Дж. Э. Хопкрофт. Структуры данных и алгоритмы. Издательский дом «Вильямс», 2000.

  • Дональд Э. Кнут. Искусство Программирования. Издательский дом «Вильямс», 2000.

  • Томас Кормен, Чарльз Лейзерсон, Рональд Ривест. Алгоритмы: построение и анализ. М.: МЦНМО, 1999.

  • Кубенский А. А. Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++. СПб.: БХВ-Петербург, 2004.

  • Тоби Сегаран. Программируем коллективный разум: [пер. с англ.] // М. — Символ-Плюс, 2008, 368 с.

  • Кузнецов С. Д. Методы сортировки и поиска. ИСП РАН, Центр Информационных Технологий.

  • Материалы лектора: приложение к данной странице; кому-то может показаться, что это лучше, чем ничего.