Установите в клетку ответа для каждого уровня балл по предложенной шкале.

В графе «Оценка» поставьте цифру в соответствии с выбранным вариантом ответа:

  1. Не знаю
  2. Имею представление
  3. Знаю теоретически
  4. Знаю и умею решать
  5. Имею опыт использования на практике

Раздел информатики

Темы

Оценка

ТЕМА 2.4. Алгоритмические стратегии

2.4.1. Алгоритмы полного перебора

 

 

2.4.2. "Жадные" алгоритмы

 

2.4.3. Алгоритмы "разделяй и властвуй" *

 

2.4.4. Перебор с возвратом *

 

2.4.5. Эвристики *

 

2.4.6. Метод ветвей и границ **

 

 

 2.4.7. Метод отжига **

 

 

2.4.8. Алгоритм четырех русских **

 

ТЕМА 2.5. Рекурсия

2.5.1. Понятие рекурсии

2.5.2. Рекурсивные математические функции

2.5.3. Простые рекурсивные процедуры

2.5.4. Реализация рекурсии

 

2.5.5. Стратегия "разделяй и властвуй" *

 

 

2.5.6. Рекурсивный перебор с возвратами *

 

ТЕМА 2.6. Фундаментальные вычислительные алгоритмы

2.6.1. Простые численные алгоритмы

2.6.2. Классические комбинаторные алгоритмы 

 

2.6.3. Алгоритмы с подмножествами: генерация, восстановление по номеру и построение номера, генерация следующего и предыдущего (прибавление и вычитание единицы) 

 

2.6.4. Алгоритмы с сочетаниями и перестановками: генерация, восстановление по номеру и построение номера, генерация следующего и предыдущего. 

 

2.6.5. Алгоритмы последовательного и бинарного поиска 

 

2.6.6. Квадратичные методы сортировки (сортировка методом выбора, сортировка вставками) 

 

2.6.7. Сортировка подсчетом за линейное время. 

 

2.6.8. Алгоритмы сортировки за время O(N log N) (быстрая сортировка, пирамидальная сортировка, сортировка слиянием) * 

 

 

2.6.9. Цифровая сортировка * 

 

 

2.6.10. Алгоритм вычисления номера слова в лексикографически упорядоченном множестве перестановок его символов * 

 

 

2.6.11. Арифметика многоразрядных целых чисел *

 

ТЕМА 2.7. Числовые алгоритмы

2.7.1. Разложение числа на простые множители

2.7.2. Решето Эратосфена

2.7.3. Алгоритм Евклида 

 

2.7.4. Расширенный алгоритм Евклида. Способы реализации алгоритма без деления *

2.7.5. Решение линейных сравнений с помощью алгоритма Евклида *

2.7.6. Эффективная реализация решета Эратосфена (O(n)) * 

 

2.7.7. Метод Гаусса и обращение матриц ** 

 

 

2.7.8. Быстрое возведение в степень по модулю. RSA-шифрование **

2.7.9. Дискретное логарифмирование **

2.7.10. Извлечение корней по модулю **

2.7.11. Эффективная проверка числа на простоту **

2.7.12. Быстрые алгоритмы разложения чисел на простые множители. Ро-эвристика **

2.7.13. Алгоритм Берлекэмпа **

 

ТЕМА 2.8. Алгоритмы на строках

2.8.1. Поиск подстроки в строке. Наивный метод 

 

2.8.2. Алгоритмы поиска подстроки в строке за O(N+M) (алгоритм Кнут-Моррис-Пратт, Z-алгоритм) * 

 

2.8.3. Периодические и циклические строки * 

 

2.8.4. Редакционное расстояние и оптимальное выравнивание * 

 

2.8.5. Алгоритм Бойера-Мура **

2.8.6. Алгоритм Ахо-Корасик для поиска нескольких подстрок за линейное время ** 

 

 

2.8.7. Алгоритм построения суффиксного дерева **

2.8.8. Цифровая сортировка суффиксов **

2.8.9. Разложение на простые строки **

2.8.10. Построение суффиксного автомата ** 

 

ТЕМА 2.9. Алгоритмы на графах

2.9.1. Вычисление длин кратчайших путей в дереве

2.9.2. Обход графа в ширину и в глубину 2.9.3. Способы реализации поиска в ширину (“наивный” и с очередью)

2.9.4. Проверка графа на связность

2.9.5. Алгоритмы поиска кратчайшего пути во взвешенных графах

 

2.9.6. Топологическая сортировка графа, нахождение компонент сильной связности и построение диаграммы порядка *

2.9.7. Циклы отрицательной длины – критерий наличия, поиск *

2.9.8. Задача о синхронизации времени и задача о системе неравенств *

2.9.9. Алгоритм поиска эйлерова цикла (в том числе лексикографически минимального) *

2.9.10. Нахождение транзитивного замыкания графа *

2.9.11. Алгоритмы нахождения взвешенных остовных деревьев * 

 

2.9.12. Алгоритмы отыскания компонент двусвязности, точек сочленения, мостов с помощью поиска в глубину *

2.9.13. Алгоритм нахождения максимального паросочетания и минимального вершинного покрытия в двудольном графе *

 

2.9.14. Поиск максимального потока в сети ** 2.9.15. Поиск потока минимальной стоимости ** 2.9.16. Венгерский метод решения задачи о назначениях. Связь между Венгерским методом, потоком минимальной стоимости и алгоритмом Дейкстры ** 2.9.17. Быстрые алгоритмы отыскания потока за O(N^3) **

 

ТЕМА 2.10. Динамическое программирование

2.10.1. Основная идея динамического программирования. Рекурсивная реализация и развертывание в цикл. 

 

2.10.2. Задачи с монотонным направлением движения в таблице

2.10.3. Задача о рюкзаке – решение методом динамического программирования

2.10.4. Оптимизация решения задачи динамического программирования на примере задачи о рюкзаке (исключение лишних параметров) * 

 

2.10.5. Восстановление решения в задачах динамического программирования *

2.10.6. Общая схема решения задач динамического программирования *

2.10.7. Динамическое программирование по профилю и по подмножествам *

2.10.8. Динамическое программирование по изломанному профилю *

 

ТЕМА 2.11. Алгоритмы теории игр

2.11.0.Простейшие алгоритмы программирования игр. 

 

2.11.1. Динамическое программирование и полный перебор как методы решения игровых задач. Игры на ациклическом графе *

 

2.11.2. Ретроанализ как метод решения игр на графах с циклами. Эффективная реализация **

2.11.3. Алгоритм сокращенного вычисления булевских выражений и его применение к анализу игр **

2.11.4. Оценка позиций. Альфа-бета отсечение **

 

ТЕМА 2.12. Геометрические алгоритмы

2.12.1. Алгоритмы определения совпадения точек, лучей, прямых и отрезков

2.12.2. Представление точек, прямых и отрезков на плоскости

 

2.12.3. Нахождение расстояний между объектами на плоскости * 2.12.4. Алгоритмы определения пересечения отрезков на плоскости *

2.12.5. Алгоритмы вычисления площади многоугольника с заданными координатами вершин. Случай целочисленной решетки (формула Пика) *

 

2.12.6. Алгоритмы построения выпуклой оболочки (алгоритмы Грэхема и Джарвиса) * 

 

 

2.12.7. Окружности на плоскости, пересечение их с другими геометрическими объектами * 

 

 

2.12.8. Проверка нахождения точки внутри многоугольника * 

 

 

2.12.9. Метод движущейся прямой *

 

 

2 2.12.10. Метод полуплоскостей ** 

 

 

2.12.11. Метод «заворачивания подарка» ** 

 

 

2.12.12. Эффективный алгоритм нахождения пары ближайших точек на плоскости **

2.12.13. Эффективный алгоритм построения диаграммы Вороного **