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

Для программ:

Материалы

Слайды

Слайды по ссылкам практически точно совпадают с теми, которые, показываются на лекциях. Но всё может поменяться 🧔🏻.

  1. От символов к байтам и обратно
  2. Числа: точность, неотрицательные системы счисления, дополнительный код
  3. Числа с плавающей запятой: представление, распределение; комплексные числа
  4. Булева и многозначные логики; cимметричные системы счисления; троичная информатика
  5. Линейные контейнеры
  6. Бинарные деревья
  7. Сильно ветвящиеся деревья
  8. Хэш-функции и хэш-таблицы
  9. Куча
  10. Строки
  11. Эволюционные алгоритмы + блокноты с примерами
  12. Стек. Динамическая и статическая цепочки
  13. Немного об алгоритмах и рекуррентных соотношениях
  14. Классификаторы

Примеры

Здесь и здесь.

Практические задания, семинары и коммуникация

Коммуникация

Чатики для ИИНД и МиКН (2025) в VK Teams СПбГУ:

Практические задания для ИИНД и МиКН (2025)

Задания проверяются при помощи курсов на HwProj:

Темы для возможных докладов МиКН

Учебный план МиКН подразумевает по две лекции в неделю в течение 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.

Зачёт и экзамен

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

Часть I

  1. Буква, символ, алфавит; кодирование и кодировки до Unicode.
  2. Unicode: пространство символов; модификаторы; нормализация; сравнение; кодировки.
  3. Абсолютная и относительная погрешности; позиционные системы счисления.
  4. Дополнительный код.
  5. Симметричные системы счисления.
  6. Троичные арифметика и логика.
  7. Числа с плавающей запятой; нормализация.
  8. Распределение чисел с плавающей запятой.
  9. Комплексные числа, распределение разных представлений.
  10. Назначение линейных контейнеров; преимущества и недостатки массивов.
  11. Массивы; представление многомерных массивов при помощи векторов Айлифа.
  12. Сортировка массивов: зачем она нужна. Алгоритмы сортировки на месте, без использования дополнительной памяти для данных.
  13. Алгоритмы сортировки с использованием дополнительной памяти для данных. Вопросы локальности обращения к ОЗУ при сортировке.
  14. Преимущества и недостатки списков; способы реализации списков; оптимизация работы списков: блочные списки.
  15. Оптимизация работы списков: шитые и иерархические списки; Zipper, стек, очередь и дек на основе списков.
  16. Назначение, преимущества и недостатки деревьев.
  17. Эффективность распараллеливания, закон Амдала, распараллеливание известных алгоритмов; жадные и динамические алгоритмы.
  18. [МиКН, ИИНД] Назначение кучи; куча для элементов одинакового размера. Тривиальная организация кучи; фрагментация и дефрагментация.
  19. [МиКН] Ускорение программ на Python при помощи Numba, MyPy, Cython.

Часть II

  1. AVL - деревья.
  2. Красно-черные деревья.
  3. Декартовы деревья.
  4. Интервальные деревья.
  5. B - деревья.
  6. R - деревья.
  7. Деревья поиска строк — префиксное дерево, Trie. Представления графов.
  8. Хеш-функции: требуемые свойства «хороших» функций, примеры использования.
  9. «Плохие» хэш-функции, их использование.
  10. Хеш-таблицы: назначение, преимущества и недостатки перед деревьями, подходы к перестройке расширению.
  11. Распределенные хеш-таблицы.
  12. Строки; представление строк при помощи массивов, списков и деревьев (ациклических графов).
  13. Представление контекста вложенных процедур при помощи цепочек фреймов и мониторов.
  14. Передача процедур «вниз» по цепочке вызовов; поддержание статической цепочки.
  15. Произвольная передача замыканий (процедур с контекстом) с копированием или динамическим выделением контекста.
  16. Теорема о рекуррентных соотношениях и примеры алгоритмов, подходящих под её частные случаи.
  17. Вдумчивые и конструктивные замечания по программе курса (любой обдуманный ответ считается безупречным).
  18. [МиКН, ИИНД] Оптимизация дефрагментации методом граничных маркеров. Метод двоичных близнецов.
  19. [МиКН] Генетические алгоритмы.

Успехи

Табличка на Яндекс.Диске

Куда загружать сертификаты за онлайн-курс?

Также на HwProj:

Критерии оценивания (2025)

Пересчёт $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:

Список информационных источников

Литература

  1. Дж. Д. Ульман А. В. Ахо, Дж. Э. Хопкрофт. Структуры данных и алгоритмы. Издательский дом «Вильямс», 2000.
  2. Дональд Э. Кнут. Искусство Программирования. Издательский дом «Вильямс», 2000.
  3. Томас Кормен, Чарльз Лейзерсон, Рональд Ривест. Алгоритмы: построение и анализ. М.: МЦНМО, 1999.
  4. Кубенский А. А. Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++. СПб.: БХВ-Петербург, 2004.
  5. Тоби Сегаран. Программируем коллективный разум: [пер. с англ.] // М. — Символ-Плюс, 2008, 368 с.
  6. Кузнецов С. Д. Методы сортировки и поиска. ИСП РАН, Центр Информационных Технологий.

Онлайн-курсы

... рекомендованные в качестве дополнительных материалов

  1. На второй семестр — Algorithmic Toolbox & Data Structures University of California San Diego; National Research University Higher School of Economics.
  2. На второй семестр — CS Center, Алгоритмы: теория и практика. Структуры данных.
  3. На все семестры Data Structures and Algorithms University of California San Diego; National Research University Higher School of Economics.

Note

Cтраница доступна на старом сайте