Материалы

Слайды

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

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

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

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

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

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

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

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

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

9. Куча

10. Строки

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

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

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

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

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

Часть I

1. Буква, символ, алфавит; кодирование и кодировки до Unicode.

2. Unicode: пространство символов; модификаторы; нормализация; сравнение; кодировки.

3. Абсолютная и относительная погрешности; позиционные системы счисления.

4. Дополнительный код.

5. Симметричные системы счисления.

6. Троичные арифметика и логика.

7. Числа с плавающей запятой; нормализация.

8. Распределение чисел с плавающей запятой.

9. Комплексные числа, распределение разных представлений.

10. Назначение линейных контейнеров; преимущества и недостатки массивов.

11. Массивы; представление многомерных массивов при помощи векторов Айлифа.

12. Преимущества и недостатки списков; способы реализации списков; оптимизация работы списков: блочные списки.

13. Оптимизация работы списков: шитые и иерархические списки; Zipper, стек, очередь и дек на основе списков.

14. Назначение, преимущества и недостатки деревьев.

15. AVL - деревья.

16. [МиКН, ИИНД] Назначение кучи; куча для элементов одинакового размера. Тривиальная организация кучи; фрагментация и дефрагментация.

17. [МиКН, ИИНД] Эффективность распараллеливания, закон Амдала, распараллеливание известных алгоритмов; жадные и динамические алгоритмы.

18. [МиКН] Ускорение программ на Python при помощи Numba, MyPy, Cython.

Часть II

1. Красно-черные деревья.

2. Декартовы деревья.

3. Интервальные деревья.

4. B - деревья.

5. R - деревья.

6. Деревья поиска строк — префиксное дерево, Trie. Представления графов.

7. Хеш-функции: требуемые свойства «хороших» функций, примеры использования.

8. «Плохие» хэш-функции, их использование.

9. Хеш-таблицы: назначение, преимущества и недостатки перед деревьями, подходы к перестройке расширению.

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

11. Строки; представление строк при помощи массивов, списков и деревьев (ациклических графов).

12. Представление контекста вложенных процедур при помощи цепочек фреймов и мониторов.

13. Передача процедур «вниз» по цепочке вызовов; поддержание статической цепочки.

14. Произвольная передача замыканий (процедур с контекстом) с копированием или динамическим выделением контекста.

15. Вдумчивые и конструктивные замечания по программе курса (любой обдуманный ответ считается безупречным).

16. [МиКН, ИИНД] Оптимизация дефрагментации методом граничных маркеров. Метод двоичных близнецов.

17. [МиКН, ИИНД] Теорема о рекуррентных соотношениях и примеры алгоритмов, подходящих под её частные случаи.

18. [МиКН] Генетические алгоритмы.

Критерии оценивания

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

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

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

ПИ

R = min(1, T + ⅔C)

МиКН

R = min(1, T + ⅔C)

ИИНД

Практические задания P∈[0, 35];

R = min(1, T + ⅗C + 9/350×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.