23.09.2020. № 2-4. Подпрограммы

Развернуть

  1. Макросы.
  2. Адрес возврата.
  3. Соглашение о вызовах. Передача аргументов, результатов. Сохраняемые регистры.
  4. Стек. Рекурсивные функции.

Исходный код

16.09.2020. № 2-3. Вещественные числа

Развернуть

  1. Вещественные числа как рациональные дроби.
  2. Представление с фиксированной точкой.
  3. Фиксированная точка и двоично-десятичный код.
  4. Числа с плавающей точкой. Binary32, binary64, битовое устройство числа, варианты хранимых чисел.
  5. Возможные проблемы плавающей арифметики.
  6. Пример проблем: сравнение двух "равных" чисел.
  7. Пример проблем: вычисление числа π по двум формулам.

09.09.2020. № 2-2. Числа, символы, массивы

Развернуть

  • Битовые операции.
  • BCD кодирование.
  • Кодировка ASCII, Юникод.
  • Массивы и их представление.
  • Многомерные массивы и варианты их представления.

Та самая интересная лекция про Юникод на TechTalks@NSU.

02.09.2020. № 2-1. Взгляд снизу, представление чисел

Развернуть

  • План курса.
  • ЭВМ в целом.
  • Процессор в целом.
  • Архитектура RISC-V.
  • Симулятор RARS (страница загрузки jar-файла).
  • Нетипизированность памяти.
  • Двоичная и шестнадцатеричная система счисления.
  • Представление беззнаковых чисел и знаковых (двоичный дополнительный код).
  • Проблема переполнения.

18.05.2020. № 11. Отладка

Развернуть

  1. Основные принципы отладки программ.

27.04.2020. № 10. Упаковка данных

Развернуть

  1. Зачем сжимать информацию?
  2. Сжатие с потерями и без потерь.
  3. Алгоритм RLE.
  4. Алгоритм Хаффмана: построение кодового дерева, упаковка и распаковка.
  5. Алгоритм LZ77 (скользящее окно).
  6. Алгоритм LZW.
  7. Исключительный случай при распаковке LZW.
  8. Сжатие с потерями и функциональный анализ.

Слайды:

Видеозапись:

20.04.2020. № 9. Проекты

Развернуть

  1. Что такое хорошая программа (хороший проект)?
  2. Хорошие и плохие интерфейсы (модулей и программ).
  3. Тестирование и документирование.

06.04.2020. № 8. Хеш-таблицы

Развернуть

  1. Общий принцип работы хеш-таблицы.
  2. Требования к хеш-функции.
  3. Интерфейс хеш-таблицы.
  4. Размещение в массиве: метод деления, метод умножения.
  5. Тривиальные хеш-функции.
  6. Хеш-функция Дженкинса.
  7. Хеш-функция для набора элементов.
  8. Конфликты и способы их разрешения.
  9. Списки коллизий.
  10. Открытая адресация: линейное, квадратичное исследование, двойное хеширование.
  11. Кукушиное хеширование (cuckoo hash).
  12. Хеш vs. дерево.
  13. Криптографические хеш-функции.
  14. Контрольные суммы.
  15. Принцип адресации по содержимому.
  16. Фильтр Блума.
  17. Генерация хеш-функций для фильтра Блума.

23.03.2020. № 7. АВЛ-деревья, красно-черные деревья, префиксные деревья

Развернуть

  1. АВЛ-деревья.
  2. 2-3-4 деревья.
  3. Красно-черные деревья (red-black trees).
  4. Префиксные деревья (trie).
  5. Слоеные списки (skip list).

Слайды:

Видеозапись:

16.03.2020. № 6. Деревья, бинарные деревья поиска, splay-деревья

Развернуть

  1. Структура данных дерево.
  2. Представление деревьев в Python.
  3. Двоичные деревья.
  4. Обходы двоичных деревьев, связь обходов с древовидным представлением арифметических выражений.
  5. Преобразование произвольного дерева в двоичное.
  6. Интерфейс и применение деревьев поиска.
  7. Высота дерева поиска.
  8. Удаление элемента.
  9. Оптимальные деревья поиска.
  10. Выворачивание (splay trees).

Действия