13.11.2017. № 11. Красно-черные деревья, очередь с приоритетом

Развернуть

  1. 2-3-4 деревья.
  2. Красно-черные деревья (red-black trees).
  3. Слоеные списки.
  4. Префиксные деревья.
  5. Очередь с приоритетом и двоичная куча («пирамида»).

30.10.2017. № 9. Splay-деревья, АВЛ-деревья, 2-3-4-деревья

Развернуть

  1. Выворачивание (splay trees).
  2. АВЛ-деревья.
  3. 2-3-4 деревья.

23.10.2017. № 8. Модули, деревья, бинарные деревья поиска

Развернуть

  1. Программирование как борьба со сложностью.
  2. Программа как один большой черный ящик.
  3. Декомпозиция на модули.
  4. Пример модульной структуры: скачивалка изображений.
  5. На что указывает граф связей между модулями?
  6. Модуль = Интерфейс + Реализация.
  7. Устройство модулей в C: заголовочный файл, исходный файл, использование модуля.
  8. Стандартная библиотека C как набор модулей.
  9. Почему интерфейс важнее реализации?
  10. Операционная система как интерфейс.
  11. Признаки хорошего интерфейса.
  12. Структура данных дерево.
  13. Представление деревьев в C.
  14. Двоичные деревья.
  15. Обходы двоичных деревьев, связь обходов с древовидным представлением арифметических выражений.
  16. Преобразование произвольного дерева в двоичное.
  17. Интерфейс и применение деревьев поиска.
  18. Высота дерева поиска.
  19. Удаление элемента.
  20. Оптимальные деревья поиска.

09.10.2017. № 6. Составные типы данных, стек, очередь, списки

Развернуть

  1. Записи
  2. Массивы.
  3. Адресация в многомерных массивах: C-style, FORTRAN-style, Java-style.
  4. Данные как «белый ящик» и как «черный ящик».
  5. Стеки, очереди и их применение в различных задачах.
  6. Реализация стека с помощью динамического массива.
  7. Связные списки: структура и свойства.
  8. Операции над списками.
  9. Двусвязные списки, кольцевые списки, двусвязные кольцевые списки.
  10. Отличия абстрактных типов данных от структур данных.

02.10.2017. № 5. Алгоритмы поиска подстроки в строке

Развернуть

  1. Поиск подстроки в строке — метод грубой силы и идеи его ускорения.
  2. Алгоритм Боуэра-Мура.
  3. Алгоритм Рабина-Карпа.

25.09.2017. № 4. Сортировки: квази-линейные, линейные

Развернуть

  1. Быстрая сортировка. Процедура разделения массива.
  2. Алгоритм выбора k-го элемента.
  3. Стабильность сортировок.
  4. Сортировка слиянием.
  5. Пирамидальная сортировка.
  6. Нижняя оценка скорости сортировок, основанных на сравнениях.
  7. Линейные сортировки: подсчетом, поразрядная, карманная.

18.09.2017. № 3. Сложность алгоритмов, алгоритмы сортировки, рекурсивные алгоритмы

Развернуть

  1. Сложность алгоритмов. Нотация O, Ω, Θ.
  2. Задача сортировки.
  3. Интерфейс функции сортировки в C.
  4. Bogosort и bozosort.
  5. Сортировка выбором.
  6. «Пузырьковая» сортировка.
  7. Сортировка вставками.
  8. Принцип «Разделяй и властвуй». Примеры: задача о ханойских башнях, получение перестановок, алгоритм Карацубы (умножение длинных чисел).
  9. Основная теорема о рекуррентных соотношениях.
  10. Поиск в массиве, двоичный поиск.
  11. Рекурсия. Удачные и неудачные примеры использования рекурсии.
  12. Хвостовая рекурсия.

Сайт с визуализацией сортировок

11.09.2017. № 2, дополнение 1. Базовые типы данных

Развернуть

Лекция от 2 марта 2017, прочитанная в рамках курса «Основы программирования»

Базовая информация о представлении целых и вещественных чисел, одномерных массивах, указателях.

11.09.2017. № 2. Сборка программы, представление примитивных типов данных

Развернуть

  1. Структура C-программы.
  2. Сборка программы: компиляция и линковка.
  3. Двоичная система счисления, перевод чисел, битовое представление.
  4. Шестнадцатеричная система счисления.
  5. Хранение знака: знак в старшем бите (наивный способ).
  6. Арифметика по модулю и двоичный дополнительный код.
  7. Переполнение.
  8. Двоично-десятичный код, Packed BCD.
  9. Строки, базовые способы их представления.
  10. Действительные числа как рациональные дроби.
  11. Представление с фиксированной точкой.
  12. Фиксированная точка и двоично-десятичный код.
  13. Числа с плавающей точкой. Binary32, binary64, битовое устройство числа, варианты хранимых чисел.
  14. Возможные проблемы плавающей арифметики.
  15. Пример проблем: сравнение двух "равных" чисел.
  16. Пример проблем: вычисление числа π по двум формулам.
  17. Иерархия структур и типов данных.

Ссылки:

11.09.2017. № 2, дополнение 2. Динамическая память, указатели на функции, символы и строки

Развернуть

Лекция от 16 марта 2017, прочитанная в рамках курса «Основы программирования»

Лекция о работе с динамической памятью, использовании указателей на функции, символах и их кодировках, о представлении строк в C.

Действия