Кодификатор олимпиадной информатики

с. 1 с. 2 с. 3
Кодификатор олимпиадной информатики

2013г.


Код раздела

Код элемента

Содержание

Класс

1.

Математические основы информатики




1.1

Функции, отношения и множества








1.1.1
1.1.2

1.1.3

1.1.4
1.1.5

Функции, обратная функция, композиция

7-8


Отношения (рефлексивность,

симметричность, транзитивность, эквивалентность, лексикографический порядок)


5-6



Множества (диаграммы Венна, дополнения, декартовы произведения)

7-8



Вполне упорядоченные множества *

9-11


Мощность и счетность *


9-11




1.2

Основные геометрические понятия








1.2.1
1.2.2

1.2.3

1.2.4


1.2.5

1.2.6


Точка, прямая, отрезок, вектор, угол

5-6


Декартовы координаты в евклидовом пространстве

5-6



Евклидово расстояние

7-8



Векторное и скалярное произведение на плоскости

7-8

Треугольник, прямоугольник, многоугольник




5-6

Выпуклые многоугольники


5-6




1.3

Основы логики








1.3.1


1.3.2
1.3.3
1.3.4

1.3.5
1.3.6
1.3.7


Логические переменные, операции.


5-6


Логические выражения

7-8

Таблицы истинности

5-6


Булевы функции

5-6


Формы задания и синтез логических функций

7-8



Преобразование логических выражений

7-8


Минимизация булевых функций *

9-11

Основные законы логики суждений*

Логика предикатов *

9-11
9-11




1.4

Основы вычислений







1.4.1

1.4.2
1.4.3

Основы вычислений:

  • Правила суммы и произведения

  • Арифметические и геометрические прогрессии

  • Числа Фибоначчи

  • Принцип включения-выключения *

5-6
5-6

7-8


7-8
9-11


Рекуррентные соотношения

5-6


Матрицы и действия над ними *

9-11





1.5

Методы доказательства









1.5.1

1.5.2
1.5.3


1.5.4
1.5.5
1.5.6


Прямые доказательства



5-6


Доказательство через контрпример

5-6


Доказательство через противопоставление


5-6



Доказательство через противоречие

7-8


Математическая индукция

7-8


Структура формальных доказательств *


9-11




1.6


Основы теории чисел







1.6.1


1.6.2
1.6.3

1.6.4
1.6.5

Простые числа. Основная теорема арифметики

7-8



Деление с остатком


5-6

Наибольший общий делитель


5-6

Взаимно простые числа

7-8


Делимость. Кольцо вычетов по модулю *

9-11





1.7

Основы алгебры








1.7.1

1.7.2

1.7.3
1.7.4
1.7.5
1.7.6


1.8

Многочлены и операции над ними. Решение квадратных уравнений. Теорема Виета

Общий случай теоремы Виета.

7-8


Симметрические многочлены *

9-11


Понятие группы *

9-11


Свойства групп *

9-11


Теоремы о гомоморфизме и изоморфизме *


9-11



Основы комбинаторики






1.8.1

1.8.2


1.8.3

1.8.4


1.8.5

Перестановки, размещения и сочетания:

      • Основные определения

      • Тождество Паскаля

      • Биномиальная теорема

5-6
5-6
7-8

7-8


Коды Грея: подмножества, сочетания, перестановки *


9-11


Таблицы инверсий перестановок *


9-11

Разбиения на подмножества. Числа Стирлинга *


9-11



Скобочные последовательности *

9-11




1.9

1.9.1

1.9.2
1.9.3
1.9.4
1.9.5
1.9.6

1.9.7
1.9.8
1.9.9


1.9.10


1.9.11

1.9.12

1.9.13

Теория графов

Типы графов

Маршруты и связность


5-6
5-6


Операции над графами

7-8


Деревья


5-6

Остовные деревья


5-6

Раскраска графов


7-8

Эйлеровы и гамильтоновы графы


7-8

Покрытия и независимость *


9-11

Укладка графов. Плоские (планарные) графы *


Двусвязность графа. Мосты, блоки, точки сочленения *


9-11



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


9-11


Двудольные графы *

9-11



Потоки и сети *


9-11





1.10


Основы теории вероятностей





1.10.1
1.10.2

Понятие вероятности,

Понятие математического ожидания.

Аксиомы теории вероятностей *

5-6
7-8
9-11


Формула полной вероятности и формула Байеса. Условное математическое ожидание *


9-11




1.11


Основы теории игр







1.11.1
1.11.2

1.11.3

Понятие игры и результата игры

5-6


Простейшие игры и стратегии

5-6


Игры на матрицах *

9-11

2

Разработка и анализ алгоритмов




2.1

Алгоритмы и их свойства







2.1.1

2.1.2
2.1.3

Понятие алгоритма

5-6


Концепции и свойства алгоритмов

5-6


Запись алгоритма на неформальном языке


5-6




2.2


Структуры данных







2.2.1

2.2.2

2.2.3
2.2.4
2.2.5
2.2.6
2.2.7

2.2.8
2.2.9
2.2.10

Простые базовые структуры

5-6


Множества

5-6



Последовательности

5-6


Списки

5-6


Неориентированные графы

5-6


Ориентированные графы

7-8


Деревья

7-8


Пирамида и дерево отрезков *

9-11


Сбалансированные деревья *

9-11


Хэш-таблицы и ассоциативные массивы *

Бор *


9-11




2.3


Основы анализа алгоритмов







2.3.1

2.3.2
2.3.3


2.3.4


2.3.5


2.3.6

Нотация О большое

7-8


Стандартные классы сложности

7-8


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


7-8



Компромисс между временем и объемом памяти в алгоритмах *

9-11



Использование рекуррентных отношений для анализа рекурсивных алгоритмов *



9-11

NP-полнота *

9-11




2.4


Алгоритмические стратегии







2.4.1
2.4.2

2.4.3
2.4.4
2.4.5

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

5-6


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

7-8


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

9-11


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

9-11


Эвристики *

9-11





2.5

Рекурсия







2.5.1
2.5.2
2.5.3
2.5.4

2.5.5
2.5.6

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

5-6


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

7-8


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

7-8


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

7-8


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

9-11


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


9-11




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

2.6.9

2.6.10

2.6.11


2.7

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

5-6


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

5-6


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

5-6


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

5-6


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


5-6



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

7-8

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

7-8


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

9-11

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

9-11



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


9-11


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

9-11


Числовые алгоритмы






2.7.1
2.7.2

2.7.3
2.7.4


2.7.5


2.7.6


2.7.7


2.7.8


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

5-6


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

5-6


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

5-6


с. 1 с. 2 с. 3