Материалы

Слайды

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

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

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

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

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

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

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

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

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

9. Куча

10. Строки

11. Эволюционные алгоритмы + блокноты с примерами

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

13. Немного об алгоритмах и рекуррентных соотношениях

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

Некоторые примеры

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

Вопросы к зачёту и экзамену, весна 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. [МиКН] Генетические алгоритмы.

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

Пересчёт R∈[0, 1]=[0%, 100%] в оценку по приказу 7293/1 от 20.07.2018.

Теоретический зачёт из двух вопросов — T = (T₁+T₂+Доп)/3.

Онлайн-курс (ниже) — C∈[0, 1] = [0%, 100%]

Практические задание — P∈[0, 1] = <полученный балл на HwProj> / <максимально возможный балл на HwProj>

ПИ

R = min(1, T + 0,49 C)

МиКН и ИИНД

R = min(1, 0,49 T + 0,49 C + 0,49 P)

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

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