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