Алгоритмы и структуры данных, сем. 2
Для программ:
- Программная инженерия
- Искусственный интеллект и наука о данных
- Математика и компьютерные науки
Материалы
Слайды
Слайды по ссылкам практически точно совпадают с теми, которые, показываются на лекциях. Но всё может поменяться 🧔🏻.
- От символов к байтам и обратно
- Числа: точность, неотрицательные системы счисления, дополнительный код
- Числа с плавающей запятой: представление, распределение; комплексные числа
- Булева и многозначные логики; cимметричные системы счисления; троичная информатика
- Линейные контейнеры
- Бинарные деревья
- Сильно ветвящиеся деревья
- Хэш-функции и хэш-таблицы
- Куча
- Строки
- Эволюционные алгоритмы + блокноты с примерами
- Стек. Динамическая и статическая цепочки
- Немного об алгоритмах и рекуррентных соотношениях
- Классификаторы
Примеры
Практические задания, семинары и коммуникация
Коммуникация
Чатики для ИИНД и МиКН (2025) в VK Teams СПбГУ:
Практические задания для ИИНД и МиКН (2025)
Задания проверяются при помощи курсов на HwProj:
Темы для возможных докладов МиКН
Учебный план МиКН подразумевает по две лекции в неделю в течение 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.
Зачёт и экзамен
Вопросы к зачёту и экзамену, весна 2025
Часть I
- Буква, символ, алфавит; кодирование и кодировки до Unicode.
- Unicode: пространство символов; модификаторы; нормализация; сравнение; кодировки.
- Абсолютная и относительная погрешности; позиционные системы счисления.
- Дополнительный код.
- Симметричные системы счисления.
- Троичные арифметика и логика.
- Числа с плавающей запятой; нормализация.
- Распределение чисел с плавающей запятой.
- Комплексные числа, распределение разных представлений.
- Назначение линейных контейнеров; преимущества и недостатки массивов.
- Массивы; представление многомерных массивов при помощи векторов Айлифа.
- Сортировка массивов: зачем она нужна. Алгоритмы сортировки на месте, без использования дополнительной памяти для данных.
- Алгоритмы сортировки с использованием дополнительной памяти для данных. Вопросы локальности обращения к ОЗУ при сортировке.
- Преимущества и недостатки списков; способы реализации списков; оптимизация работы списков: блочные списки.
- Оптимизация работы списков: шитые и иерархические списки; Zipper, стек, очередь и дек на основе списков.
- Назначение, преимущества и недостатки деревьев.
- Эффективность распараллеливания, закон Амдала, распараллеливание известных алгоритмов; жадные и динамические алгоритмы.
- [МиКН, ИИНД] Назначение кучи; куча для элементов одинакового размера. Тривиальная организация кучи; фрагментация и дефрагментация.
- [МиКН] Ускорение программ на Python при помощи Numba, MyPy, Cython.
Часть II
- AVL - деревья.
- Красно-черные деревья.
- Декартовы деревья.
- Интервальные деревья.
- B - деревья.
- R - деревья.
- Деревья поиска строк — префиксное дерево, Trie. Представления графов.
- Хеш-функции: требуемые свойства «хороших» функций, примеры использования.
- «Плохие» хэш-функции, их использование.
- Хеш-таблицы: назначение, преимущества и недостатки перед деревьями, подходы к перестройке расширению.
- Распределенные хеш-таблицы.
- Строки; представление строк при помощи массивов, списков и деревьев (ациклических графов).
- Представление контекста вложенных процедур при помощи цепочек фреймов и мониторов.
- Передача процедур «вниз» по цепочке вызовов; поддержание статической цепочки.
- Произвольная передача замыканий (процедур с контекстом) с копированием или динамическим выделением контекста.
- Теорема о рекуррентных соотношениях и примеры алгоритмов, подходящих под её частные случаи.
- Вдумчивые и конструктивные замечания по программе курса (любой обдуманный ответ считается безупречным).
- [МиКН, ИИНД] Оптимизация дефрагментации методом граничных маркеров. Метод двоичных близнецов.
- [МиКН] Генетические алгоритмы.
Успехи
Куда загружать сертификаты за онлайн-курс?
Также на HwProj:
Критерии оценивания (2024)
Пересчёт $R \in [0, 1] = [0\%, 100\%]$ в оценку по приказу 7293/1 от 20.07.2018.
Теоретический зачёт из двух вопросов — $T = (T_1+T_2+\mathrm{Доп})/3$.
Онлайн-курс (ниже) — $C \in [0, 1] = [0\%, 100\%]$
Практические задание — $P \in [0, 1] = $ <полученный балл на HwProj> / <хороший возможный балл на HwProj>
ПИ
$$R = \min(1, T + 1/2 C)$$
МиКН и ИИНД
$$R = \min(1, T + 1/2 C + 1/2 P)$$
В 2025:
- для МиКН $P =$ <балл в HwProj> / 50
- для ИИНД $P =$ <балл в HwProj> / 70
Список информационных источников
Литература
- Дж. Д. Ульман А. В. Ахо, Дж. Э. Хопкрофт. Структуры данных и алгоритмы. Издательский дом «Вильямс», 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.
https://edu.dluciv.name/search_index.ru.json $MATCHES more matchesNote