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

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

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

Внимание!

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

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

Материалы

Мультимедиа

Слайды

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

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

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

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

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

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

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

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

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

  9. Куча

  10. Строки

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

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

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

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

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

Видеозаписи занятий

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

0. Python: быстрый, не очень и медленный

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

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

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

  4. Числовые типы — Python и другие языки

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

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

  7. Производительность массивов в Python

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

  9. Неблокирующие операции ввода-вывода и GUI

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

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

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

  13. Совсем немного нейронных сетей

Вопросы к зачёту и экзамену, весна 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. Деревья поиска строк — префиксное дерево, Trie. Представления графов.

  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.

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

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

  • Конспект.

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

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

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

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

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

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

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