Материалы

Слайды

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

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. [МиКН] Генетические алгоритмы.

Критерии оценивания (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.