воскресенье, 16 ноября 2014 г.

Готовимся к олимпиаде по программированию

Советую познакомиться со следующими лекциями. До просмотра приготовьте тетрадь и ручку. Смотрите и конспектируйте лекции

Лекция 1. Оценка сложности алгоритмов. Необходимость оценки сложности программ. Полиномиальные и экспоненциальные оценки. Структуры данных: стек, очередь. Списки и операции со списками.



Лекция 2. Поиск в упорядоченном и неупорядоченном массиве. Целочисленный двоичный поиск. Вещественный двоичный поиск. Приоритетная очередь. Куча. Деревья. Двоичные деревья.



Лекция 3. Числа Фибоначчи. Задача о кузнечике, прыгающем по столбикам. Задача о кузнечике и лягушках. Задача о кузнечике и монетах. Задача о черепашке. Задача о черепашке и монетках. Задача о клетках с животными. Задача о рюкзаке. Оптимальность использования динамического программирования.



Лекция 4. Графы. Вершины и ребра графа. Путь в графе. Длина пути. Простой путь. Циклический путь. Неориентированный граф. Ориентированный граф. Лемма о рукопожатиях. Связность в неориентированном графе. Компоненты связности в неориентированном графе. Полный граф. Ациклические графы. Представление графов в программе.



Лекция 5. Поиск в глубину. Топологическая сортировка. Алгоритм поиска циклов в графе. Кратчайшие пути в графах. Обход графа в ширину. Обход графа в глубину. Пути во взвешенных графах. Алгоритм Дейкстры.


Лекция 6. Остовные деревья. Алгоритм Краскала. Алгоритм Прима. Остовный лес.



Лекция 7Базовые геометрические примитивы и работа с ними. Тригонометрические функции. Обратные тригонометрические функции. Операции над векторами. Скалярное произведение векторов. Векторное произведение векторов.



Лекция 8. Точность вычислений. Геометрические объекты. Окружность. Многоугольники. Выпуклые и невыпуклые многоугольники. Площадь многоугольника. Определение выпуклости многоугольника. Самопересекающиеся многоугольники.



Лекция 9. Представление чисел. Реализация процедуры считывания длинного числа. Реализация процедуры вывода длинного числа. Сложение длинных чисел. Умножение длинного числа на короткое. Вычитание длинных чисел. Деление длинного числа на короткое. Сравнение длинных чисел.


Лекция 10. Лексикографический порядок. Сложение двоичных чисел. Перевод чисел из десятичной системы счисления в двоичную. Перевод чисел из двоичной системы счисления в десятичную. Перестановки. Сочетания.





Комментариев нет:

Отправить комментарий