Примерная программа по олимпиадной информатике представляет собой следующее. Математические основы информатики

Вид материала

Примерная программа

Подобный материал:

Элективный курс Математические основы информатики, 18.01kb.
Рабочая программа элективного курса для 10 класса по информатике и икт «Математические, 45.88kb.
Примерная программа по олимпиадной информатике Всероссийских олимпиад школьников построена, 204.16kb.
Программа по информатике для специальных (коррекционных) классов VII вида 5 класс Пояснительная, 1447.84kb.
Примерная программа дисциплины Математические основы психологии Специальность «050706., 323.74kb.
Программа спецкурса по информатике для 10-11 классов составители: учитель информатики, 122.08kb.
Примерная программа подготовки водителей транспортных средств категории "C" общие положения, 721.06kb.
Программа профильного курса информатики 10-11 класс пояснительная записка, 62.72kb.
Планирование, содержание и особенности внеклассной работы по информатике. Кабинет информатики., 10.41kb.
Примерная программа среднего (полного) общего образования по информатике базовый уровень, 149.29kb.

Примерная программа по олимпиадной информатике представляет собой следующее.

Математические основы информатики
1. Функции, отношения и множества
  1. Функции
  2. Отношения (рефлексивность, симметричность, транзитивность, эквивалентность)
  3. Множества (диаграммы Венна, дополнения)
  4. Обратная функция, композиция *
  5. Лексикографический порядок *
  6. Декартовы произведения *
  7. Вполне упорядоченные множества **
  8. Мощность и счетность множества. Конечные и бесконечные
    множества **
2. Основные геометрические понятия
  1. Точка, прямая, отрезок, вектор, угол
  2. Треугольник, прямоугольник, многоугольник
  3. Выпуклые многоугольники
  4. Декартовы координаты в евклидовом пространстве
  5. Евклидово расстояние *
  6. Векторное и скалярное произведение на плоскости *
3. Основы логики
  1. Логические переменные, операции, выражения
  2. Таблицы истинности
  3. Булевы функции
  4. Формы задания и синтез логических функций *
  5. Преобразование логических выражений *
  6. Минимизация булевых функций **
  7. Основные законы логики суждений **
  8. Логика предикатов **
4. Основы вычислений
  1. Основы вычислений:

Правила суммы и произведения
Арифметические и геометрические прогрессии *
Числа Фибоначчи *
Принцип «включения-выключения» **

Рекуррентные соотношения *
Матрицы и действия над ними **

Методы доказательства
1. Прямые доказательства
2. Доказательство методом «от противного»
3. Доказательство методом исключения
4. Доказательство через контрпример
5. Математическая индукция *
6. Структура формальных доказательств **
Основы теории чисел
1. Простые числа
2. Деление с остатком
3. Наибольший общий делитель
4. Основная теорема арифметики *
5. Взаимно простые числа *
6. Делимость. Кольцо вычетов по модулю **
Основы алгебры
1. Многочлены и операции над ними. Решение квадратных уравнений. Теорема Виета *
2. Общий случай теоремы Виета. Симметрические многочлены **
3. Понятие группы **
4. Теоремы о гомоморфизме и изоморфизме **
Основы комбинаторики
1. Перестановки, размещения и сочетания:

Основные определения
Тождество Паскаля *
Биномиальная теорема *

Коды Грея: подмножества, сочетания, перестановки **
Таблицы инверсий перестановок **
Разбиения на подмножества. Числа Стирлинга **
Скобочные последовательности **

Теория графов
1. Типы графов
2. Маршруты и связность
3. Деревья
4. Операции над графами *
5. Остовные деревья *
6. Раскраска графов *
7. Эйлеровы и гамильтоновы графы *
8. Покрытия и независимость **
9. Укладка графов. Плоские (планарные) графы **
10. Двусвязность графа. Мосты, блоки, точки сочленения **
11. Связь ориентированных ациклических графов и отношений порядка. Транзитивное замыкание **
12. Двудольные графы **
13. Потоки и сети **
Основы теории синтаксического анализа
1. Обратная польская запись
2. Синтаксический анализ простых выражений *
3. Регулярные выражения, конечные автоматы **
Основы теории вероятностей
1. Понятие вероятности и математического ожидания *
2. Аксиомы теории вероятностей **
3. Основы вычисления вероятностей **
Основы теории игр
1. Понятие игры и результата игры
2. Простейшие игры
3. Простейшие стратегии игры *
4. Игры на матрицах **
5. Решение игровых задач с использованием функции Гранди **

Разработка и анализ алгоритмов
1. Алгоритмы и их свойства
  1. Понятие алгоритма
  2. Концепции и свойства алгоритмов
  3. Запись алгоритма на неформальном языке
2. Структуры данных
  1. Простые базовые структуры
  2. Множества
  3. Последовательности
  4. Списки
  5. Неориентированные графы *
  6. Ориентированные графы *
  7. Деревья *
  8. Пирамида и дерево отрезков **
  9. Сбалансированные деревья **
  10. Хэш-таблицы и ассоциативные массивы **
  11. Бор **
3. Основы анализа алгоритмов
  1. Нотация О большое *
  2. Стандартные классы сложности *
  3. Асимптотический анализ поведения алгоритмов в среднем и крайних
    случаях *
  4. Компромисс между временем и объемом памяти в алгоритмах **
  5. Использование рекуррентных отношений для анализа рекурсивных алгоритмов **
  6. NP-полнота **
4. Алгоритмические стратегии
  1. Алгоритмы полного перебора
  2. "Жадные" алгоритмы *
  3. Алгоритмы "разделяй и властвуй" *
  4. Перебор с возвратом *
  5. Эвристики **
5. Рекурсия
  1. Понятие рекурсии
  2. Рекурсивные математические функции *
  3. Простые рекурсивные процедуры *
  4. Реализация рекурсии *
  5. Рекурсивный перебор с возвратами **
6. Фундаментальные вычислительные алгоритмы
  1. Простые численные алгоритмы
  2. Классические комбинаторные алгоритмы
  3. Алгоритмы с подмножествами: генерация, восстановление по номеру и построение номера, генерация следующего и предыдущего (прибавление и вычитание единицы)
  4. Алгоритмы последовательного и бинарного поиска
  5. Алгоритмы с сочетаниями и перестановками (генерация, восстановление по номеру и построение номера, генерация следующего и предыдущего) *
  6. Квадратичные методы сортировки (сортировка методом выбора, сортировка вставками) *
  7. Сортировка подсчетом за линейное время *
  8. Алгоритмы сортировки за время O(N log N) (быстрая сортировка, пирамидальная сортировка, сортировка слиянием) **
  9. Цифровая сортировка **
  10. Алгоритм вычисления номера слова в лексикографически упорядоченном множестве перестановок его символов **
  11. Арифметика многоразрядных целых чисел **
7. Числовые алгоритмы
  1. Разложение числа на простые множители
  2. Решето Эратосфена *
  3. Алгоритм Евклида *
  4. Расширенный алгоритм Евклида. Способы реализации алгоритма без деления **
  5. Решение линейных сравнений с помощью алгоритма Евклида **
  6. Эффективная реализация решета Эратосфена (O(n)) **
  7. Эффективная проверка числа на простоту **
  8. Быстрые алгоритмы разложения чисел на простые множители.
    Ро-эвристика **
8. Алгоритмы на строках
  1. Поиск подстроки в строке. Наивный метод *
  2. Алгоритмы поиска подстроки в строке за O(N+M) **
  3. Периодические и циклические строки **
  4. Алгоритм поиска нескольких подстрок за линейное время **
9. Алгоритмы на графах
  1. Вычисление длин кратчайших путей в дереве
  2. Обход графа в ширину и в глубину
  3. Способы реализации поиска в ширину (“наивный” и с очередью) *
  4. Проверка графа на связность *
  5. Алгоритмы поиска кратчайшего пути во взвешенных графах *
  6. Топологическая сортировка графа, нахождение компонент сильной связности и построение диаграммы порядка **
  7. Циклы отрицательной длины – критерий наличия, поиск **
  8. Задача о синхронизации времени и задача о системе неравенств **
  9. Алгоритм поиска эйлерова цикла (в том числе лексикографически минимального) **
  10. Нахождение транзитивного замыкания графа **
  11. Алгоритмы нахождения взвешенных остовных деревьев **
  12. Алгоритмы отыскания компонент двусвязности, точек сочленения, мостов с помощью поиска в глубину **
  13. Алгоритм нахождения максимального паросочетания и минимального вершинного покрытия в двудольном графе **
  14. Поиск максимального потока в сети **
10. Динамическое программирование
  1. Основная идея динамического программирования. Рекурсивная реализация и развертывание в цикл *
  2. Задачи с монотонным направлением движения в таблице *
  3. Задача о рюкзаке – решение методом динамического программирования *
  4. Оптимизация решения задачи динамического программирования на примере задачи о рюкзаке (исключение лишних параметров) **
  5. Восстановление решения в задачах динамического программирования **
  6. Общая схема решения задач динамического программирования **
11. Алгоритмы теории игр
  1. Динамическое программирование и полный перебор как методы решения игровых задач **
  2. Игры на ациклическом графе **
  3. Оценка позиций. Альфа-бета отсечение **
12. Геометрические алгоритмы
  1. Алгоритмы определения совпадения точек, лучей, прямых и отрезков
  2. Представление точек, прямых и отрезков на плоскости *
  3. Нахождение расстояний между объектами на плоскости **
  4. Алгоритмы определения пересечения отрезков на плоскости **
  5. Алгоритмы вычисления площади многоугольника с заданными координатами вершин. Случай целочисленной решетки (формула Пика) **
  6. Алгоритмы построения выпуклой оболочки (алгоритмы Грэхема и Джарвиса) **
  7. Окружности на плоскости, пересечение их с другими геометрическими объектами **
  8. Эффективный алгоритм нахождения пары ближайших точек на
    плоскости **
Основы программирования
1. Языки программирования
  1. Классификация языков программирования
  2. Процедурные языки
  3. Основы синтаксиса и семантики языков высокого уровня *
  4. Формальные методы описания синтаксиса: форма Бэкуса-Наура **
  5. Объектно-ориентированные языки **
2. Основные конструкции программирования
  1. Переменные, типы, выражения и присваивания
  2. Основы ввода/вывода
  3. Операторы проверки условия и цикла
  4. Функции и передача параметров *
  5. Структурная декомпозиция **
3. Переменные и типы данных
  1. Концепция типа данных как множества значений и операций над ними
  2. Свойства объявлений (связывание, область видимости, блоки и время
    жизни) *
  3. Обзор проверки типов *
4. Типы структур данных
  1. Примитивные типы
  2. Массивы
  3. Записи *
  4. Стратегии выбора подходящей структуры данных *
  5. Представление данных в памяти **
  6. Статическое, автоматическое и динамическое выделение памяти **
  7. Указатели и ссылки **
  8. Связанные структуры **
  9. Методы реализации стеков, очередей и хэш-таблиц **
  10. Методы реализации графов и деревьев **
5. Механизмы абстракции.
  1. Классы и объекты, замыкания *
  2. Процедуры, функции и итераторы как механизмы абстракции *
  3. Механизмы параметризации (ссылки и значения) *
  4. Модули в языках программирования *
6. Особенности программирования фундаментальных алгоритмов.
  1. Стратегии решения задач
  2. Роль алгоритмов в процессе решения задач
  3. Стратегии реализации алгоритмов *
  4. Реализация рекурсии *
  5. Стратегии отладки **
Средства ИКТ
1. Цифровая логика
  1. Системы счисления
  2. Компьютерная арифметика
  3. Логические схемы *
2. Представление данных в памяти компьютера
  1. Биты, байты и слова *
  2. Представление числовых данных **
  3. Системы с фиксированной и плавающей точкой **
  4. Представление со знаковым битом и в дополнительном коде **
  5. Представление нечисловых данных (коды символов, графические данные) **
  6. Представление массивов и записей **
3. Организация работы компьютера
  1. Принципы фон Неймана
  2. Управляющее устройство: выборка инструкций, декодирование и выполнение *
  3. Набор инструкций и виды инструкций (манипуляция данными, управление, ввод-вывод) *
  4. Форматы инструкций **
  5. Режимы адресации **
  6. Механизм вызовов и возвратов из процедур **
  7. Ввод-вывод и прерывания **
4. Устройство памяти компьютера
  1. Организация основной памяти и операции с ней
  2. Иерархия памяти *
  3. Кодирование данных, сжатие данных и целостность **
  4. Кэш-память **
5. Взаимодействие и коммуникации
  1. Интерфейс пользователя. Основы ввода-вывода информации. Основы скоростного клавиатурного ввода.
  2. Введение в сетевые технологии
  3. Внешняя память, физическая организация и устройства *
  4. Прямой доступ к памяти **
Операционные системы
1. Основы операционных систем
  1. Роль и задачи операционных систем
  2. Функционирование типичной операционной системы
  3. Директории: содержимое и структура
  4. Именование, поиск, доступ, резервное копирование *
2. Основные функции операционных систем
  1. Абстракции, процессы и ресурсы *
  2. Организация устройств *
  3. Защита, доступ и аутентификация *
3. Управление памятью
  1. Обзор физической памяти и аппаратного обеспечения, предназначенного для управления памятью *
  2. Страничная и сегментная организации памяти **
  3. Кэширование **
Основы технологии программирования
1. Программные средства и окружения
  1. Среды программирования
  2. Инструментальные средства тестирования *
2. Проверка соответствия программного обеспечения
  1. Основы тестирования программ
  2. Создание тестового плана и генерация тестов *
  3. Тестирование методом "черного ящика" и "белого ящика" *
  4. Тестирование элементов, интеграционное, системное тестирование и проверка соответствия **
Методы вычислений и моделирование
1. Основы вычислительной математики
  1. Основные методы вычислительной математики

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

Арифметика с плавающей точкой *
Вычисление функций с шагом. Метод сеток **
Ошибка, устойчивость, сходимость**

Введение в моделирование
1. Понятия модели и моделирования
2. Основные типы моделей
3. Компоненты компьютерной модели и способы их описания: входные и выходные переменные, переменные состояния, функции перехода и выхода, функция продвижения времени *
4. Основные этапы и особенности построения компьютерных моделей *
5. Основные этапы использования компьютерных моделей при решении практических задач *

Компьютерные сетевые технологии
1. Сети и телекоммуникации.
  1. Сетевые устройства
  2. Среды передачи данных
  3. Использование паролей и механизмов контроля доступа
  4. Использование сетевых ресурсов
  5. Сетевые архитектуры *
  6. Вопросы качества обслуживания: производительность, восстановление после сбоев **
2. Беспроводные сети.
  1. Специфические проблемы беспроводных и мобильных компьютеров
  2. Установка программ на мобильные и беспроводные компьютеры *
  3. Беспроводные локальные сети и линии связи *

Список рекомендуемой литературы

Алексеев А.В., Беляев С.Н. Подготовка школьников к олимпиадам по информатике с использованием веб-сайта: учебно-методическое пособие для учащихся 7-11 классов. – Ханты-Мансийск: РИО ИРО, 2008. – 284 с.
Андреева Е.В., Босова Л.Л., Фалина И.Н. Математические основы информатики. Элективный курс: Учебное пособие. – М.: БИНОМ. Лаборатория Знаний, 2007.
– 312 с.
Арсак Ж. Программирование игр и головоломок. – М.: Наука, 1990. – 224 с.
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — Пер. с англ. — М.: Мир, 1979. — 536 с.
Бентли Д. Жемчужины творчества программистов: пер. с англ. – М.: Радио и связь, 1990. – 224 с.
Босова Л.Л., Босова А.Ю., Коломенская Ю.Г. Занимательные задачи по информатике. – М.: БИНОМ. Лаборатория знаний. 2007. – 119 с.
Брудно А.Л., Каплан Л.И. Московские олимпиады по программированию/ Под ред. акад. Б.Н. Наумова.- 2-е изд., доп. и пераб. – М.: Наука, гл. ред. физ.-мат. лит., 1990. – 208 с.
Великович Л.С., Цветкова М.С. Программирование для начинающих. – М.: БИНОМ. Лаборатория знаний. 2007. – 287 с.
Волчёнков С.Г., Корнилов П.А., Белов Ю.А. и др. Ярославские олимпиады по информатике. Сборник задач с решениями. – М.: БИНОМ. Лаборатория знаний. 2010. – 405 с.
Долинский М.С. Алгоритмизация и программирование на Turbo Pascal: от простых до олимпиадных задач: Учебное пособие. – СПб.: Питер Принт, 2004. – 240 с.
Задачи по программированию /С.М. Окулов, Т.В. Ашихмина, Н.А. Бушмелева и др.; Под ред. С.М. Окулова. – М.: БИНОМ. Лаборатория знаний, 2006. – 820 с.
Златопольский Д. М. Программирование: типовые задачи, алгоритмы, методы. – М.: БИНОМ. Лаборатория знаний, 2007. – 223 с.
Иванов С.Ю., Кирюхин В.М., Окулов С. М. Методика анализа сложных задач по информатике: от простого к сложному // Информатика и образование. 2006. №10.
С. 21 – 32.
Кирюхин В.М. Всероссийская олимпиада школьников по информатике. М.: АПК и ППРО, 2005. –212 с.
Кирюхин В.М. Информатика. Всероссийские олимпиады. Выпуск 1. – М.: Просвещение, 2008. – 220 с. – (Пять колец).
Кирюхин В.М. Информатика. Всероссийские олимпиады. Выпуск 2. – М.: Просвещение, 2009. – 222 с. – (Пять колец).
Кирюхин В.М. Информатика. Всероссийские олимпиады. Выпуск 3. – М.: Просвещение, 2010. – 201 с. – (Пять колец). (Планируется к выпуску в конце 2010 года).
Кирюхин В.М. Информатика. Международные олимпиады. Выпуск 1. – М.: Просвещение, 2009. – 239 с. – (Пять колец).
Кирюхин В.М., Окулов С. М. Методика анализа сложных задач по информатике // Информатика и образование. 2006. №4. С. 42 – 54.
Кирюхин В.М., Окулов С. М. Методика анализа сложных задач по информатике // Информатика и образование. 2006. №5. С. 29 – 41.
Кирюхин В.М., Окулов С. М. Методика решения задач по информатике. Международные олимпиады. – М.: БИНОМ. Лаборатория знаний, 2007. – 600 с.
Кирюхин В.М., Цветкова М.С. Всероссийская олимпиада школьников по информатике в 2006 году. – М.: АПК и ППРО, 2006. – 152 с.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.
– М.: МЦНМО, 1999. – 960с.
Меньшиков Ф.В. Олимпиадные задачи по программированию. – СПб.: Питер, 2006. – 315 с.
Московские олимпиады по информатике. 2002 – 2009. / Под ред. Е.В. Андреевой, В.М. Гуровица и В.А. Матюхина. – М.: МЦНМО, 2009. – 414 с.
Окулов С.М. Основы программирования. – М.: БИНОМ. Лаборатория знаний, 2005. – 440 с.
Окулов С.М. Программирование в алгоритмах. – М.: БИНОМ. Лаборатория знаний. 2002. – 341 с.
Окулов С.М. Дискретная математика. Теория и практика решения задач по информатике: учебное пособие. – М.: БИНОМ. Лаборатория знаний. 2008. – 422 с.
Окулов С.М. Алгоритмы обработки строк: учебное пособие. – М.: БИНОМ. Лаборатория знаний, 2009. – 255 с.
Окулов С.М., Лялин А.В. Ханойские башни. – М.: БИНОМ. Лаборатория знаний. 2008. – 245 с. (Развитие интеллекта школьников).
Пинаев В.Н. Олимпиадные задачи по программированию: Учебное пособие / РГАТА. – Рыбинск, 1997. – 41 с.
Просветов Г.И. Дискретная математика: задачи и решения: учебное пособие. – М.: БИНОМ. Лаборатория знаний. 2008. – 222 с.
Пупышев В.В. 128 задач по началам программирования. – М.: БИНОМ. Лаборатория знаний. 2009. – 167 с.
Рейнгольд Э. Комбинаторные алгоритмы: теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Део. – М.: Мир, 1980. – 476 с.
Скиена С.С., Ревилла М.А. Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям. – М.: Кудиц-образ, 2005. – 416 с.
Столяр С.Е., Владыкин А.А.. Информатика. Представление данных и алгоритмы. – СПб.: Невский Диалект; М.: БИНОМ. Лаборатория знаний. 2007. –382 с.
Сулейманов Р.Р. Организация внеклассной работы в школьном клубе программистов: методическое пособие. – М.: БИНОМ. Лаборатория знаний. 2010.
– 255 с.
Уэзерелл Ч. Этюды для программистов. – М.: Мир, 1982. – 288 с.
Шень А. Программирование: теоремы и задачи. – М.:МЦНМО, 1995. – 264 с.

Blog

Примерная программа по олимпиадной информатике представляет собой следующее. Математические основы информатики