Муниципальное автономное общеобразовательное учреждение
средняя общеобразовательная школа № 64

Приложение
к основной образовательной
программе
основного общего образования
приказ № 266-о от 31.08.2019г.

Рабочая программа
курса внеурочной деятельности «Олимпиадная информатика»

Уровень образования: основное общее
Направление: общеинтеллектуальное
срок реализации 1 год
класс обучения: 8,9
общее количество часов на реализацию программы: 70, 105

г. Екатеринбург

Результаты освоения курса

Личностные
1.
способность к эмоциональному восприятию математических объектов, рассуждений, решений задач, рассматриваемых
проблем;
2.
умение строить речевые конструкции (устные и письменные) с использованием изученной терминологии и символики,
понимать смысл поставленной задачи. Осуществлять перевод с естественного языка на математический и наоборот.
Метапредметные
1.
умение планировать свою деятельность при решении учебных математических задач, видеть различные стратегии решения задач, осознанно выбирать способ решения;
2.
умение работать с учебным математическим текстом (находить ответы на поставленные вопросы, выделять смысловые
фрагменты);
3.
умение проводить несложные доказательные рассуждения, опираясь на изученные определения, свойства, признаки;
распознавать верные и неверные утверждения; иллюстрировать примерами изученные понятия и факты; опровергать с помощью контрпримеров неверные утверждения;
4.
умение действовать в соответствии с предложенным алгоритмом, составлять несложные алгоритмы вычислений и построений;
5.
применение приёмов самоконтроля при решении учебных задач;
6.
умение видеть математическую задачу в несложных практических ситуациях и уметь реализовать её решение с помощью алгоритма.
Предметные
1.
владение базовым понятийным аппаратом по основным разделам содержания;
2.
умение составлять базовые алгоритмы, записывать их на языке программирования;
3.
владение навыками вычислений с натуральными числами, обыкновенными и десятичными дробями, положительными
и отрицательными числами;
4.
умение решать текстовые задачи арифметическим способом, используя различные стратегии и способы рассуждения;
5.
умение проводить несложные практические расчёты (включающие вычисления с процентами, выполнение необходимых измерений, использование прикидки и оценки);
6.
использование букв для записи общих утверждений, формул, выражений, уравнений; умение оперировать понятием
«буквенное выражение»;
7.
понимание и использование информации, представленной в форме таблиц, столбчатой и круговой диаграммы;
8.
умение решать простейшие комбинаторные задачи перебором возможных вариантов.
9.
вычислительные навыки: умение применять вычислительные навыки при решении практических задач, бытовых, кулинарных и других расчетах.

13. анализировать и осмысливать текст задачи; моделировать условие с помощью схем, рисунков; строить логическую цепочку рассуждений; критически оценивать полученный ответ;
14. умение решать задачи с помощью графов;
15. извлекать необходимую информацию из текста, осуществлять самоконтроль;
16. выполнять сбор информации в несложных случаях, представлять информацию в виде таблиц и диаграмм, в том числе с
помощью компьютерных программ;
17. выполнять вычисления с реальными данными;
18. проводить случайные эксперименты, в том числе с помощью компьютерного моделирования, интерпретировать их результаты.

Содержание курса
1. Математические основы информатики.
1. Отношения, функции и множества.
2. Основные геометрические понятия.
3. Основы логики.
4. Основы вычислений.
5. Методы доказательства.
6. Основы теории чисел.
7. Основы алгебры.
8. Основы комбинаторики.
9. Теорию графов.
10. Основы теории вероятностей.
11. Основы теории игр.
2. Разработка и анализ алгоритмов.
1. Алгоритмы и их свойства.
2. Структуры данных
3. Основы анализа алгоритмов.
4. Алгоритмические стратегии.
5. Рекурсия.
6. Фундаментальные вычислительные алгоритмы.
7. Числовые алгоритмы.
8. Алгоритмы на строках.
9. Алгоритмы на графах.
10. Динамическое программирование.
11. Алгоритмы теории игр.
3. Основы программирования.
1. Язык программирования Pascal.
2. Основные конструкции программирования.
3. Переменные и типы данных.
4. Типы структур данных.
5. Особенности программирования фундаментальных алгоритмов.
4. Методы вычислений и моделирование.
1. Основы вычислительной математики.
2. Введение в моделирование.

Тематическое планирование к программе «Олимпиадная информатика»
Тематический план для учащихся 8 классов
Раздел

Основные разделы
математической
информатики.

Номер занятия
1

Тема

Количество
часов
1

2

Положение о Всероссийской олимпиаде школьников. Методические рекомендации по
проведению школьного, муниципального и регионального этапов Всероссийской олимпиады школьников по информатике.
Типы олимпиадных задач по информатике для 7-8 классов.

3

Функции, отношения и множества. Обратная функция, композиция

1

4
5

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

1
1

6

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

1

7
8

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

1
1

9
10
11

Преобразование логических выражений
Основы вычислений
Арифметические и геометрические прогрессии. Числа Фибоначчи

1
1
1

12
13
14

Методы доказательства. Доказательство через противоречие
Математическая индукция
Основы теории чисел. Основная теорема арифметики

1
1
1

15
16
17
18
19

Взаимно простые числа. Основы алгебры
Многочлены и операции над ними. Решение квадратных уравнений. Теорема Виета
Основы комбинаторики
Тождество Паскаля. Биномиальная теорема
Теория графов. Операции над графами. Раскраска графов

1
1
1
1
1

1

Алгоритмы

20

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

1

21

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

1

22
23
24
25
26

Понятие математического ожидания.
Алгоритмы и их свойства
Ориентированные графы. Деревья
Основы анализа алгоритмов. Стандартные классы сложности
Асимптотический анализ поведения алгоритмов в среднем и крайних случаях

1
1
1
1
1

27

Алгоритмические стратегии. "Жадные" алгоритмы

1

28
29
30

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

1
1
1

31
32
33

Квадратичные методы сортировки (сортировка методом выбора, сортировка вставками)
Сортировка подсчетом за линейное время.
Алгоритмы сортировки за время (быстрая сортировка, пирамидальная сортировка)

1
1
1

34
35

1
1

37

Алгоритмы на строках
Проверка графа на связность. Алгоритмы поиска кратчайшего пути во взвешенных графах
Динамическое программирование. Основная идея динамического программирования. Рекурсивная реализация и развертывание в цикл.
Задачи с монотонным направлением движения в таблице

38
39
40
41

Задача о рюкзаке – решение методом динамического программирования
Геометрические алгоритмы
Представление точек, прямых и отрезков на плоскости
Языки программирования

1
1
1
1

42
43
44

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

1
1
1

45

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

1

36

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

1
1

46

Основные структуры данных.

1

47

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

1

48
49
50
51
52

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

1
1
1
1
1

53

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

1

54
55
56

Обзор проверки типов
Записи
Записи. Решение задач.

1
1
1

57
58
59

Стратегии выбора подходящей структуры данных
Процедуры, функции и итераторы как механизмы абстракции
Процедуры, функции. Решение задач.

1
1
1

60
61
62
63
64
65

Механизмы параметризации (ссылки и значения)
Модули в языках программирования
Стратегии реализации алгоритмов
Реализация рекурсии
Реализация рекурсии. Решение задач
Введение в моделирование.

1
1
1
1
1
1

66

1

67
68
69

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

70

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

1
1
1

Тематический план для учащихся 9 классов
Раздел

Основные разделы
математической информатики.

Номер занятия
1

2
3

4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Тема
Положение о Всероссийской олимпиаде школьников. Методические рекомендации по
проведению школьного, муниципального и регионального этапов Всероссийской олимпиады школьников по информатике.
Типы олимпиадных задач по информатике для 9 классов.
Функции, отношения и множества
Вполне упорядоченные множества. Мощность и счетность
Основы логики. Минимизация булевых функций
Основные законы логики суждений. Логика предикатов
Основы вычислений. Принцип включения-выключения
Матрицы и действия над ними
Методы доказательства. Структура формальных доказательств
Основы теории чисел
Кольцо вычетов по модулю
Основы алгебры. Симметрические многочлены
Понятие группы. Свойства групп
Теоремы о гомоморфизме и изоморфизме
Основы комбинаторики
Коды Грея: подмножества, сочетания, перестановки
Таблицы инверсий перестановок.Разбиения на подмножества. Числа Стирлинга
Скобочные последовательности
Теория графов. Покрытия и независимость
Укладка графов. Плоские (планарные) графы
Двусвязность графа. Мосты, блоки, точки сочленения
Связь ориентированных ациклических графов и отношений порядка. Транзитивное замыкание
Двудольные графы.Потоки и сети
Основы теории вероятностей.Аксиомы теории вероятностей

Количество
часов
1

1
1

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

Алгоритмы

25
26
27
28
29
30
31
32
33
34
35
36
37
38

39
40
41
42
43
44
45

46
47

Формула полной вероятности и формула Байеса. Условное математическое ожидание
Основы теории игр.
Игры на матрицах
Алгоритмы и их свойства.Пирамида и дерево отрезков.Сбалансированные деревья
Хэш-таблицы и ассоциативные массивы.Бор
Основы анализа алгоритмов.Компромисс между временем и объемом памяти в алгоритмах
Использование рекуррентных отношений для анализа рекурсивных алгоритмов.NPполнота
Алгоритмические стратегии. Алгоритмы "разделяй и властвуй".Перебор с возвратом
Эвристики.Рекурсия.Стратегия "разделяй и властвуй".Рекурсивный перебор с возвратами
Фундаментальные вычислительные алгоритмы
Алгоритмы сортировки (сортировка слиянием).Цифровая сортировка
Алгоритм вычисления номера слова в лексикографически упорядоченном множестве перестановок его символов
Арифметика многоразрядных целых чисел.Числовые алгоритмы
Расширенный алгоритм Евклида. Способы реализации алгоритма без деления.Решение
линейных сравнений с помощью алгоритма Евклида.Эффективная проверка числа на
простоту.Быстрые алгоритмы разложения чисел на простые множители.
Алгоритмы на строках.Периодические и циклические строки.Алгоритм поиска нескольких подстрок за линейное время
Алгоритмы на графах.Топологическая сортировка графа, нахождение компонент сильной связности и построение диаграммы порядка
Циклы отрицательной длины – критерий наличия, поиск
Задача о синхронизации времени и задача о системе неравенств
Алгоритм поиска эйлерова цикла (в том числе лексикографически минимального).Нахождение транзитивного замыкания графа
Алгоритмы нахождения взвешенных остовных деревьев
Алгоритмы отыскания компонент двусвязности, точек сочленения, мостов с помощью
поиска в глубину.Алгоритм нахождения максимального паросочетания и минимального
вершинного покрытия в двудольном графе
Поиск максимального потока в сети
Динамическое программирование.Оптимизация решения задачи динамического программирования на примере задачи о рюкзаке (исключение лишних парамет-

1
1
1
1
1
1
1
1
1
1
1
1
1
1

1
1
1
1
1
1
1

1
1

48
49
50
51
52
53
54

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

55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

ров).Восстановление решения в задачах динамического программирования.Общая схема
решения задач динамическогопрограммирования
Алгоритмы теории игр
Динамическое программирование и полный перебор как методы решения игровых задач.
Игры на ациклическом графе
Оценка позиций. Альфа-бета отсечение
Геометрические алгоритмы
Нахождение расстояний между объектами на плоскости
Алгоритмы определения пересечения отрезков на плоскости
Алгоритмы вычисления площади многоугольника с заданными координатами вершин.
Случай целочисленной решетки (формула Пика)
Алгоритмы построения выпуклой оболочки (алгоритмы Грэхема и Джарвиса)
Окружности на плоскости, пересечение их с другими геометрическими объектами
Эффективный алгоритм нахождения пары ближайших точек на плоскости
Языки программирования
Основные конструкции программирования
Следование
Ветвление
Цикл.
Процедуры, функции.
Типы структур данных
Особенности программирования фундаментальных алгоритмов.
Программные средства и окружения.
Проверка соответствия программного обеспечения.
Формальные методы описания синтаксиса:
форма Бэкуса-Наура
Объектно-ориентированные языки
Структурная декомпозиция
Представление данных в памяти
Статическое, автоматическое и динамическое выделение памяти
Указатели и ссылки
Связанные структуры
Методы реализации стеков, очередей и хэш-таблиц

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

Методы реализации графов и деревьев
Реализация рекурсии
Стратегии отладки
Инструментальные средства тестирования
Основы тестирования, включая создание тестового плана и генерацию тестов
Тестирование методом "черного ящика" и "белого ящика"
Тестирование элементов, интеграционное, системное тестирование и проверка соответствия
Основы вычислительной математики.
Основные методы вычислительной математики:вычисление значения и корней функции
Основные методы вычислительной математики:вычисление периметра, площади и объема плоских фигур
Вычисление функций с шагом. Метод сеток
Арифметика с плавающей точкой
Ошибка, устойчивость, сходимость
Основные методы вычислительной математики
Вычисление функций с шагом. Метод сеток
Арифметика с плавающей точкой
Ошибка, устойчивость, сходимость
Вычисление функций с шагом. Метод сеток
Решения задач по разделам из коллекцииwww.olympiads.ru .
Решения задач по разделам из коллекции www.olympiads.ru .
Решения задач по разделам из коллекции www.olympiads.ru .
Решения задач по разделам из коллекции www.olympiads.ru .
Решения задач по разделам из коллекции www.olympiads.ru .
Решения задач по разделам из коллекции www.olympiads.ru .
Решения задач по разделам из коллекции www.olympiads.ru .
Решения задач по разделам из коллекции www.olympiads.ru .
Решения задач по разделам из коллекции www.olympiads.ru .
Решения задач по разделам из коллекции www.olympiads.ru .
Решения задач по разделам из коллекции www.olympiads.ru .
Решения задач по разделам из коллекцииwww.olympiads.ru .

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

Представлены интернет-ресурсы олимпиадной информатики:
1. Интернет-ресурсы для теоретической подготовки к олимпиадам:
http://www.intuit.ru/courses.html (сайт Интернет-университета информационных технологий);
http://www.olympiads.ru/sng/index.shtml (сайт МИОО, МЦНМО, и оргкомитета Московской олимпиады по информатике для проведения дистанционных семинаров по подготовке к олимпиадам по информатике);
http://vzshit.net.ru/ (сайт Всесибирской заочной школы информационных технологий).
2. Интернет-ресурсы с коллекциями олимпиадных задач:
http://old.info.rosolymp.ru (сайт с самой большой в России коллекцией задач международных и всероссийских олимпиад по информатике с
методическими рекомендациями по их решению);
http://www.olympiads.ru/moscow/index.shtml (сайт московских олимпиад по информатике);
http://neerc.ifmo.ru/school/russia-team/archive.html (сайт с архивом задач Всероссийских командных олимпиад школьников по программированию);
http://contest.ur.ru (сайт Уральских олимпиад по информатике);
http://www.olympiads.ru/ (сайт по олимпиадной информатике);
http://olimpic.nsu.ru/nsu/ (сайт открытой Всесибирской олимпиады по программированию им. И.В. Поттосина).
3. Интернет-ресурсы с коллекциями олимпиадных задач и возможностью их тестирования в реальном масштабе времени:
http://acm.timus.ru/ (сайт Уральского государственного университета, содержащий большой архив задач с различных соревнований по спортивному программированию);
http://acm.sgu.ru (сайт Саратовского государственного университета, содержащий архив задач с системой онлайн-проверки).
4. Сайты интернет-олимпиад для школьников:
http://info-online.rusolimp.ru/ (сайт интернет-туров заключительного этапа Всероссийской олимпиады школьников по информатике);
http://olymp.ifmo.ru/ (сайт городских интернет – олимпиад школьников Санкт-Петербурга);
http://neerc.ifmo.ru/school/io/index.html (сайт интернет-олимпиад по информатике, проводимых жюри Всероссийской командной олимпиады
школьников по программированию);
http://www.olympiads.ru/online/index.shtml (сайт московских онлайн-олимпиад);
http://olimpic.nsu.ru/acmSchool/archive/2006-2007/train2006/index.shtml (сайт тренировочных олимпиад школьников, поддерживаемый Новосибирским государственным университетом).
Электронные ссылки
Сайт Методического центра олимпиадной информатики:
http://metodist.lbz.ru/lections/6/
Портал Всероссийской олимпиады школьников:
http://www.rosolymp.ru/
Сайт с архивом олимпиадных задач:
http://old.rosolymp.ru/
Модуль поддержан видеолекциямичленов Центральной предметно-методической комиссии на сайте http://metodist.lbz.ru/content/videocourse.php

Powered by TCPDF (www.tcpdf.org)