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

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

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

9-11

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

9-11

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

9-11

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

9-11

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

9-11

2.8

Алгоритмы на строках

2.8.1

2.8.2

2.8.3

2.8.4

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

5-6

Алгоритмы поиска подстроки в строке за O(N+M) *

9-11

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

9-11

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

9-11

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

Алгоритмы на графах

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

5-6

Обход графа в ширину и в глубину

5-6

Способы реализации поиска в ширину (“наивный” и с очередью)

5-6

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

7-8

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

7-8

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

9-11

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

9-11

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

9-11

Алгоритм поиска эйлерова цикла (в том

числе лексикографически минимального) *

9-11

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

9-11

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

9-11

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

9-11

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

9-11

Поиск максимального потока в сети *

9-11

2.10

Динамическое программирование

2.10.1

2.10.2

2.10.3

2.10.4

2.10.5

2.10.6

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

7-8

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

7-8

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

7-8

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

9-11

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

9-11

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

9-11

2.11

Алгоритмы теории игр *

2.11.1

2.11.2

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

9-11

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

9-11

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

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

5-6

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

7-8

Нахождение расстояний между объектами

на плоскости *

9-11

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

9-11

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

9-11

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

9-11

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

9-11

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

9-11

3

Основы программирования

3.1

3.1.1

3.1.2

3.1.3

3.1.4

3.1.5

Языки программирования

Классификация языков программирования

5-6

Процедурные языки программирования

5-6

Основы синтаксиса и семантики языков высокого уровня

7-8

Формальные методы описания синтаксиса:
форма Бэкуса-Наура *

9-11

Объектно-ориентированные языки *

9-11

3.2

3.2.1

3.2.2

3.2.3

3.2.4

3.2.5

Основные конструкции программирования

Переменные, типы, выражения и присваивания

5-6

Основы ввода/вывода

5-6

Операторы проверки условия и цикла

5-6

Функции и передача параметров

7-8

Структурная декомпозиция *

9-11

3.3

3.3.1

3.3.2

3.3.3

Переменные и типы данных

Концепция типа данных как множества значений и операций над ними

5-6

Свойства объявлений (связывание, область видимости, блоки и время жизни)

7-8

Обзор проверки типов

7-8

3.4

3.4.1

3.4.2

3.4.3

3.4.4

3.4.5

3.4.6

3.4.7

3.4.8

3.4.9

3.4.10

Типы структур данных

Примитивные типы

5-6

Массивы

5-6

Записи

7-8

Стратегии выбора подходящей структуры данных

7-8

Представление данных в памяти *

9-11

Статическое, автоматическое и

динамическое выделение памяти *

9-11

Указатели и ссылки *

9-11

Связанные структуры *

9-11

Методы реализации стеков, очередей и хэш-таблиц *

9-11

Методы реализации графов и деревьев *

9-11

3.5

3.5.1

3.5.2

3.5.3

Механизмы абстракции

Процедуры, функции и итераторы как механизмы абстракции

7-8

Механизмы параметризации (ссылки и значения)

7-8

Модули в языках программирования

7-8

3.6

3.6.1

3.6.2

3.6.3

3.6.4

3.6.5

Особенности программирования фундаментальных алгоритмов.

Стратегии решения задач

5-6

Роль алгоритмов в процессе решения задач

5-6

Стратегии реализации алгоритмов

7-8

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

7-8

Стратегии отладки *

9-11

4

Средства ИКТ

4.1

4.1.1

4.1.2

4.1.3

Цифровая логика

Логические схемы

7-8

Системы счисления

5-6

Компьютерная арифметика

5-6

4.2

4.2.1

4.2.2

4.2.3

4.2.4

4.2.5

4.2.6

Представление данных в памяти компьютера

Биты, байты и слова

5-6

Представление числовых данных *

9-11

Системы с фиксированной и плавающей точкой *

9-11

Представление со знаковым битом и в дополнительном коде *

9-11

Представление нечисловых данных (коды символов, графические данные) *

9-11

Представление массивов и записей *

9-11

4.3

4.3.1

4.3.2

4.3.3

4.3.4

4.3.5

4.3.6

4.3.7

Организация работы компьютера

Принципы фон Неймана

5-6

Управляющее устройство: выборка инструкций, декодирование и выполнение

7-8

Набор инструкций и виды инструкций (манипуляция данными, управление, ввод-вывод)

Форматы инструкций *

7-8

7-8

Режимы адресации *

9-11

Механизм вызовов и возвратов из процедур *

9-11

Ввод-вывод и прерывания *

9-11

4.4

4.4.1

4.4.2

4.4.3

4.4.4

Устройство памяти компьютера

Организация основной памяти и операции с ней

5-6

Иерархия памяти

7-8

Кодирование данных, сжатие данных и целостность *

9-11

Кэш-память *

9-11

4.5

4.5.1

4.5.2

4.5.3

4.5.4

Взаимодействие и коммуникации

Интерфейс пользователя. Основы ввода-вывода информации. Принципы скоростного клавиатурного ввода.

5-6

Внешняя память, физическая организация и устройства

7-8

Введение в сетевые технологии

Прямой доступ к памяти *

5-6

9-11

5

Операционные системы

5.1

5.1.1

5.1.2

5.1.3

5.1.4

Основы операционных систем

Роль и задачи операционных систем

5-6

Функционирование типичной операционной системы

5-6

Директории: содержимое и структура

5-6

Именование, поиск, доступ, резервное копирование

7-8

5.2

5.2.1

5.2.2

Основные функции операционных систем

Абстракции, процессы и ресурсы

7-8

Организация устройств

Защита, доступ и аутентификация

7-8

7-8

5.3

5.3.1

5.3.2

5.3.3

Управление памятью

Обзор физической памяти и аппаратного обеспечения, предназначенного для управления памятью

7-8

Страничная и сегментная организации памяти *

9-11

Кэширование *

9-11

6

Основы технологии программирования

6.1

6.1.1

6.1.2

Программные средства и окружения

Среды программирования

5-6

Инструментальные средства тестирования *

9-11

6.2

6.2.1

6.2.2

Проверка соответствия программного обеспечения.

Основы тестирования, включая создание тестового плана и генерацию тестов *

Тестирование методом "черного ящика" и "белого ящика" *

9-11

9-11

Тестирование элементов, интеграционное, системное тестирование и проверка соответствия *

9-11

7

Методы вычислений и моделирование

7.1

7.1.1

7.1.2

7.1.3

7.1.4

Основы вычислительной математики*.

Основные методы вычислительной математики

    вычисление значения и корней функции * вычисление периметра, площади и объема плоских фигур*

5-6

9-11

9-11

Вычисление функций с шагом. Метод сеток *

9-11

Арифметика с плавающей точкой *

9-11

Ошибка, устойчивость, сходимость*

9-11

7.2

7.2.1

7.2.2

7.2.3

7.2.4

7.2.5

Введение в моделирование.

Понятия модели и моделирования

Основные типы моделей

5-6

5-6

Компоненты компьютерной модели и способы их описания: входные и выходные переменные, переменные состояния, функции перехода и выхода, функция продвижения времени

7-8

Основные этапы и особенности построения компьютерных моделей

7-8

Основные этапы использования компьютерных моделей при решении практических задач

7-8

8

Компьютерные сетевые технологии

8.1

8.1.1

8.1.2

8.1.3

8.1.4

8.1.5

Сети и телекоммуникации.

Сетевые карты и сетевые устройства

5-6

Среды передачи данных

5-6

Сетевые архитектуры

7-8

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

5-6

Вопросы качества обслуживания: производительность, восстановление после сбоев *

9-11

8.2

8.2.1

8.2.2

8.2.3

Беспроводные сети.

Специфические проблемы беспроводных и мобильных компьютеров

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

5-6

7-8

Беспроводные локальные сети и линии связи

7-8

Список рекомендуемой литературы олимпиадной подготовки по информатике издательства «БИНОМ. Лаборатория знаний» (см каталог  на сайте  www. LBZ. RU ).

НЕ нашли? Не то? Что вы ищете?

НАЧАЛЬНЫЙ УРОВЕНЬ

1

Учимся программировать в компьютере: самоучитель для детей и родителей

2

Логические задачи

3

, Механизм творчества решения нестандартных задач. Руководство для тех, кто хочет научиться решать нестандартные задачи: учебное пособие

4

Формирование у младших школьников представлений о геометрических фигкрах: пособие для учителя начальной школы

5

, Виртуальные лаборатории по информатике в начальной школе: методическое пособие

6

, Культура клавиатурного письма: методическое пособие

7

Методика решения учебных задач средствами программирования: методическое пособие

8

Организация внеклассной работы в школьном клубе программистов: методическое пособие

9

Занимательные задачи по информатике

ОСНОВНОЙ УРОВЕНЬ

1

Основы программирования

2

Программирование в алгоритмах

3

Задачи по программированию

4

, Ханойские башни. Занятия по информатике с одаренными школьниками

5

Объектно-ориентированное программирование для начинающих

6

Тестирование и отладка программ для профессионалов будущих и настоящих

7

Информатика: представление данных и алгоритмы

8

рограммирование для начинающих

9

Программирование – это просто: пошаговый подход. (перевод с английского)

10

Введение в программирование. Учебное пособие

11

Программирование на языке Pascal. Учебное пособие

12

Основы программирования на С# 2.0

13

амоучитель по С++ от Wiley (перевод с английского языка)

14

Бишоп Дж. С# в кратком изложении (перевод с английского языка)

15

Сборник заданий по основаниям программирования. Учебное пособие

16

Основы программирования С#. Учебное пособие

17

Язык Си и особенности работы с ним. Учебное пособие

18

Основы программирования в интегрированной среде DELPHI. Практикум

19

Программирование: типовые задачи, алгоритмы, методы

20

Сборник заданий по основам программирования

21

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

ПРОФИЛЬНЫЙ УРОВЕНЬ

1

, Методика решения задач по информатике. Международные олимпиады

2

и др. Дискретная математика. Теория и практика решения задач по информатике

3

изика для разработчиков компьютерных игр (перевод с английского языка)

4

Графы и алгоритмы. Структура данных. Модели вычисления. Учебник

5

, ,   Математические основы информатики. Элективный курс.  Учебное пособие

6

Разработка Паскаль-компилятора

7

оследовательные и параллельные алгоритмы: общий подход (перевод с английского языка)

8

Структуры данных и проектирование программ (перевод с английского языка)

9

Графы и их применение. Комбинаторные алгоритмы для программистов.

10

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

11

Дискретная математика: задачи и решения. Учебное пособие

12

Лекции по дискретной математике. Учебное пособие

13

Динамическое программирование в экономических задачах

14

Наглядная математическая статистика. Учебное пособие

15

и др. Элементарный курс теории вероятностей. Стохастические процессы и фин. математика (перевод с английского языка)

16

Спенсер Дж. Вероятностный метод. Учебное пособие (перевод с английского языка)

17

Введение в анализ, синтез и моделирование систем. Учебное пособие

Примерная программа по олимпиадной информатике соответсвует программе, разработанной , председателем ЦПМК по информатике Всероссийских олимпиад школьников МОН РФ.