Алгоритмы и структуры данных, c2
09.03.04, Программная инженерия
02.03.01, Математика и компьютерные науки
Внимание!
Осторожно! У вас ведёт занятие преподаватель Кафедры системного программирования СПбГУ, но ваша группа возможно ещё не заполняла опрос «Давайте познакомимся»? Это очень опасная ситуация.
Не ждите, пока (и если) преподаватель скажет. Заполняйте!
Материалы
Слайды
Слайды по ссылкам практически точно совпадают с теми, которые показываются на лекциях
Числа: точность, неотрицательные системы счисления, дополнительный код
Числа с плавающей запятой: представление, распределение; комплексные числа
Булева и многозначные логики; cимметричные системы счисления; троичная информатика
Задания и примеры
Опубликованы здесь
Темы практических занятий
0. Python: быстрый, не очень и медленный
Проверка типов, iterrools и генераторы, декораторы и magic-методы в Python
Кодировки: современные, несовременные, экзотические. Кодировки в программах на Python и C
Collation в Unicode для разных языков
Числовые типы — Python и другие языки; обратный код; модульные тесты
Плавающая запятая IEEE-754 и Posits
Нечёткие логики
Производительность массивов в Python
Высота случайных деревьев; визуализация графов
О распределённых хэш-таблицах
Скорость работы кучи
Скорость и возможности реализаций статических цепочек для разных языков
Вопросы к зачёту и экзамену, весна 2023
Часть I
Буква, символ, алфавит; кодирование и кодировки до Unicode.
Unicode: пространство символов; модификаторы; нормализация; сравнение; кодировки.
Абсолютная и относительная погрешности; позиционные системы счисления.
Дополнительный код.
Симметричные системы счисления.
Троичные арифметика и логика.
Числа с плавающей запятой; нормализация.
Распределение чисел с плавающей запятой.
Комплексные числа, распределение разных представлений.
Назначение линейных контейнеров; преимущества и недостатки массивов.
Массивы; представление многомерных массивов при помощи векторов Айлифа.
Преимущества и недостатки списков; способы реализации списков; оптимизация работы списков: блочные списки.
Оптимизация работы списков: шитые и иерархические списки; Zipper, стек, очередь и дек на основе списков.
Назначение, преимущества и недостатки деревьев.
AVL - деревья.
[МиКН] Ускорение программ на Python при помощи Numba, MyPy, Cython.
[МиКН] Генетические алгоритмы.
Часть II
Красно-черные деревья.
Декартовы деревья.
Интервальные деревья.
B - деревья.
R - деревья.
Деревья поиска строк — префиксное дерево, Trie. Представления графов.
Хеш-функции: требуемые свойства «хороших» функций, примеры использования.
«Плохие» хэш-функции, их использование.
Хеш-таблицы: назначение, преимущества и недостатки перед деревьями, подходы к перестройке расширению.
Распределенные хеш-таблицы.
Строки; представление строк при помощи массивов, списков и деревьев (ациклических графов).
Представление контекста вложенных процедур при помощи цепочек фреймов и мониторов.
Передача процедур «вниз» по цепочке вызовов; поддержание статической цепочки.
Произвольная передача замыканий (процедур с контекстом) с копированием или динамическим выделением контекста.
Вдумчивые и конструктивные замечания по программе курса (любой обдуманный ответ считается безупречным).
[МиКН] Назначение кучи; куча для элементов одинакового размера. Тривиальная организация кучи; фрагментация и дефрагментация.
[МиКН] Оптимизация дефрагментации методом граничных маркеров. Метод двоичных близнецов.
Темы для докладов
Учебный план подразумевает по две лекции в неделю в течение 4 семестров. Всё это время сидеть и слушать не полезно для психического здоровья. Поэтому предлагается сделать ряд докладов.
~20 мин. Python typing & Abstract Base Classes. Объяснить, зачем они нужны, и что они дают программисту на Python.
~20 мин. Реализация целочисленной арифметики с использованием обратного кода.
~40–50 мин. Unums & Posits. Объяснить, как (и для чего) хранятся числа в форматах Unum и Posit, попробовать хотя бы одну реализацию, продемонстрировать отличия в работе от IEEE-754.
~20 мин. Реализация Deque на основе неизменяемых структур данных. Можно пользоваться Википедией, но желательно копнуть глубже.
~20 мин. Высота несбалансированного дерева поиска. Доходчиво и внятно изложить материал по ссылке.
~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 с.
Кузнецов С. Д. Методы сортировки и поиска. ИСП РАН, Центр Информационных Технологий.
Онлайн-курсы, рекомендованные в качестве дополнительных материалов
На второй семестр — Algorithmic Toolbox & Data Structures University of California San Diego; National Research University Higher School of Economics.
На второй семестр —. CS Center Алгоритмы: теория и практика. Структуры данных.
На все семестры Data Structures and Algorithms University of California San Diego; National Research University Higher School of Economics