Первый семестр с акцентом на алгоритмы

Часть 1. Основные понятия

• Лекции
  • Современные задачи информатики
  • Интуитивное понятие алгоритма?
    • Примеры алгоритмов из жизни. Понятие иcполнителя.
    • Блок схемы. Блок схемы классических алгоритмов
      • Алгоритм Евклида?
      • Ханойские башни
      • Простота числа
  • Системы счисления. Способы представления данных в компьютере. Блок схема вычисления двоичной записи числа.
  • Вычислительные машины. Множество вычислимых функций
    • Конечные автоматы. Примеры задач, которые удобно решать с помощью конечных автоматов.
    • Машина Тьюринга
    • Алгорифмы Маркова
    • Различные определения вычислимых функций и их эквивалентность
  • Язык программирования.
    • Структура программы
    • Типы данных
    • Операторы, функции
    • Массивы

• Cеминары
  • Алгоритмы в математике. Алгоритм Евклида и НОД.(a, b) Оценка времени работы алгоритма. Алгоритм проверки числа на простоту и разложения на множители. Ханойские башни.
  • Знакомство с языком на простых задачах
    • Оператор цикла. Условный оператор.
    • Стандартный поток ввода и вывода.
    • Скалярные типы данных.
    • Математические операции.
    • Работа со строчками.
    • Работа с массивами.
    • Программирование своих функций.
    • Однопроходные алгоритмы
      • максимум введеных чисел
      • среднее введенных чисел
      • правильность скобочной структуры
  • Двоичное представление числа.
  • Примеры рекурсивных алгоритмов
    • a^n
    • n!
    • F(n)=F(n-1) + F(n-2).
      • Вычисление числа Фибоначчи F_n. Сравнение рекурсивного и нерекурсивного алгоритма
      • Эффективный алгоритм
        • 1) основанный на возведении матрицы A={ {1,1}, {1,0}} в n-ую степень
        • 2) основанный на рекурентной формуле F(2n) = F(n)F(n+1)+ F(n)F(n-1)
  • Сортировка
    • Сведение к n-кратному поиску максимума
    • Метод пузырька
    • Оценка времени работы сортировки пузырьком
  • Метод деления пополам (binary search)
    • Корень функции
    • Задача про провода

Простые задачи для знакомства с языком программирования

Часть 2. Алгоритмы: Построение и анализ

• Лекции
  • Рекурсивные алгоритмы. Идея "Разделяй и властвуй". Оценка времени работы рекурсивных алгоритмов на основе рекуррентных соотношений.
  • Алгоритмы сортировки. Нижняя граница для сложности задачи упорядочивания. Алгоритм QuickSort. Расчет среднего времени работы алгоритмы QSort.
  • Динамическое программирование
    • Использование памяти для хранения найденых решений
    • Рекурсия с запоминанием или "динамическое программирование сверху"
  • Жадные алгоритмы
    • Задача об оптимальном расписании
      • а) удовлетворить максимальное число заявок имея одну аудиторию
      • б) минимизировать число аудиторий удовлетворив все заявки
    • Архивирование методом Хафмана
  • Задача хранения и поиска данных. Структуры данных
    • Балланс между временем добавления(изменения) и временем извлечения информации
    • BinaryHeap
      • HeapSort — метод сортировки, работающий в худшем случае n log n
      • Очередь с приоритетами
    • BinarySearchTree
      • Хранение отображений (maps)
    • HashTable? и SearchTrees?
    • B-Trees.

• Семинары
  • Рассмотрение QuickSort. Экспериментальный анализ
    • Число операций SWAP в среднем и в худшем случае
    • Число операций SWAP для массива {5,4,3,2,1}
  • Очередь и стек.
    • задача про сложные скобки
    • задача про лабиринт.
  • Бинарная куча BinaryHeap.
    • HeapSort
    • очередь с приоритетами
    • K максимальных чисел из N введенных за время N log K
  • Двоичное дерево поиска
  • Задача про топологическую сортировку — одежда профессора: "Что за чем одевать?"
    • Представление графов в памяти
    • Обход графа в глубину - Depth First Search (DFS)
    • Хэширование
  • Максимальное число паросочетаний Простые задачи на алгоритмы