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

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

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

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

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

Цель: подготовка мотивированных учащихся к результативному участию во Всероссийской олимпиаде школьников по информатике

Ф.И. обучающихся:

·               Воронков Никита, 7В класс

·               Огуенко Марина, 7Б класс

Задачи:

- создать условия для развития творческого потенциала обучающихся по информатике

- сформировать у обучающихся  умения решать задания олимпиадного уровня

 Содержание олимпиад по информатике охватывает  следующие ключевые разделы, которые и составляют на сегодняшний момент основное содержание олимпиад школьников по информатике:

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

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

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

4. Средства ИКТ.

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

Раздел «Математические основы информатики» в значительной степени связан с дискретными структурами и является фундаментальной основой информатики. В олимпиадах по информатике это особенно важно, так как школьникам сложно достичь успешности на олимпиадных состязаниях без хорошей подготовки в области теории множеств, логики, теории графов и комбинаторики.

Большое значение имеют математические основы информатики и для дальнейшего обучения школьников, заинтересованных в изучении информатики в высших учебных заведениях, так как сведения из теории дискретных структур широко используются не только в структурах данных и алгоритмах, но и во всех остальных разделах информатики. Более того, по мере развития информатики, все возрастающая сложность методов анализа оказывает влияние на решение практических профессиональных задач и проблемы. Для того чтобы освоить вычислительные средства и высокие информационные технологии  будущего, сегодняшним школьникам крайне необходимы знания дискретных структур.

В связи с этим, для успешного выступления на олимпиаде по информатике школьники по темам раздела «Математические основы информатики» должны

знать/понимать:

·               основы терминологии функций, отношений и множеств;

·               перестановки, размещения и сочетания множества;

·               формальные методы символической логики высказываний

·               основы построения рекуррентных соотношений;

·               основные методы доказательств;

·               основы теории чисел;

уметь:

·               выполнять операции, связанные с множествами, функциями и отношениями;

·               вычислять перестановки, размещения и сочетания множества, а также интерпретировать их значения в контексте конкретной задачи;

·               решать типичные рекуррентные соотношения;

·               осуществлять формальные логические доказательства и логическое  рассуждение для моделирования алгоритмов;

·               определять, какой вид доказательства лучше подходит для решения конкретной задачи;

·               использовать основные алгоритмы теории чисел;

·               использовать при решении практических задач вышеназванные знания и умения.

Основными темами этого раздела являются:

1. Отношения, функции и множества.

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

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

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

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

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

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

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

9. Теорию графов.

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

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

Раздел «Разработка и анализ алгоритмов» является для олимпиад по  информатике очень важным и определяет основу продуктивной деятельности школьников, их творческого самовыражения. Именно в этой области информатики участники олимпиады имеют возможность продемонстрировать свои лучшие творческие качества при решении олимпиадных заданий.  Важность теории алгоритмов трудно переоценить. Фактическая ценность любой программы или программной системы зависит от двух факторов: применяемых в ней алгоритмов и эффективности их реализации на различных ее уровнях. Поэтому разработка хорошего алгоритма имеет решающее значение для производительности любой программной системы. Кроме того, изучение алгоритмов позволяет более глубоко вникнуть в задачу и может подсказать методы решения, не зависящие от языка программирования, парадигмы программирования, аппаратного обеспечения и других аспектов реализации.

Изучение теории алгоритмов помогает развивать у школьников способность выбирать алгоритм, наиболее подходящий для решения данной задачи, или доказать, что такого алгоритма не существует. Эта способность должна основываться на знании класса алгоритмов, которые предназначены для решения определенного набора известных задач, понимании их сильных и слабых сторон, применимости различных алгоритмов в заданном контексте с оценкой его эффективности.

В рамках этого раздела для успешного выступления на олимпиадах по информатике школьники должны

знать/понимать:

·               элементы теории алгоритмов;

·               основные структуры данных;

·               основные понятия теории графов, а также их свойства и некоторые специальные случаи;

·               связь графов и деревьев со структурами данных, алгоритмами и вычислениями;

·               свойства, присущие «хорошим» алгоритмам;

·               вычислительную сложность основных алгоритмов сортировки, поиска и хеширования;

·               понятие рекурсии и общую постановку рекурсивно-определенной  задачи;

·               хэш-функцию и ее назначение;

·               простые численные алгоритмы;

·               основные комбинаторные алгоритмы;

·               основные алгоритмы вычислительной геометрии;

·               наиболее распространенные алгоритмы сортировки;

·               наиболее важные алгоритмы на строках;

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

·               основные алгоритмические стратегии: полный перебор, перебор с возвратом, "жадные", "разделяй и властвуй" и эвристические;

·               основы динамического программирования;

·               основные положения теории игр;

уметь:

·               выбирать подходящие структуры данных для решения задач;

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

·               определять сложность по времени и памяти алгоритмов;

·               реализовывать рекурсивные функции и процедуры;

·               использовать при решении практических задач вышеназванные знания и умения.

Основными темами этого раздела являются:

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

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

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

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

5. Рекурсия.

6. Фундаментальные вычислительные алгоритмы.

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

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

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

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

11. Алгоритмы теории игр.

12. Геометрические алгоритмы.

Раздел «Основы программирования» и высокий технологический уровень его освоения является необходимыми условиями успешного выступления любого школьника на олимпиадах по информатике. Чтобы участвовать в олимпиаде по информатике, каждый школьник должен не просто знать, а применять на практике, хотя бы один язык программирования. Более того, освоение участниками олимпиады по информатике языков, которые используют, по крайней мере, две парадигмы программирования, также желательно.   Важно заметить, что знания и умения в области программирования состоят из тех концепций и навыков, которые важны для практики программирования, независимо от применяемой парадигмы программирования. Поэтому данный раздел включает в себя материал по фундаментальным концепциям программирования, основным структурам данных и алгоритмам, а также собственно языки программирования. Языки программирования являются основным средством общения школьника и компьютера во время решения олимпиадных заданий. Школьники должны не просто уметь написать программу на каком-либо одном языке, они должны понимать различные стили программирования, присущие разным языкам. Понимание разнообразия языков программирования и различных парадигм значительно облегчает быстрое освоение ими новых языков. 

В рамках этого раздела для успешного выступления на олимпиаде по информатике школьники должны  знать/понимать:

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

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

·               основные типы данных;

·               основные структуры данных: массивы, записи, строки, связные списки, стек, очереди и хэш-таблицы;

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

·               альтернативные представления структур данных с точки зрения производительности;

·               основы ввода/вывода;

·               операторы, функции и передача параметров;

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

·               управление памятью во время исполнения программы;

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

·               методы реализации графов и деревьев;

·               механизм передачи параметров;

·               особенности реализации рекурсивных решений;

·               стратегии, полезные при отладке программ;

уметь:

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

·               модифицировать и расширить короткие программы, использующие стандартные условные и итеративные операторы и функции;

·               разработать, реализовать, протестировать и отладить программу, которая использовать все наиболее важные конструкции программирования;

·               применять методы структурной (функциональной) декомпозиции для разделения программы на части;

·               реализовать основные структуры данных на языке высокого уровня;

·               реализовать, протестировать и отладить рекурсивные функции и процедуры;

·               использовать при решении практических задач вышеназванные знания и умения и уверенно программировать хотя бы на одном из допустимых на олимпиадах по информатике языков программирования (C/C++, Pascal, VisualBasic).

Основными темами этого раздела являются:

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

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

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

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

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

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

Средства ИКТ, основу которых составляет компьютер, – неотъемлемые инструменты, которые школьники должны использовать во время проведения олимпиад по информатике. Чтобы участники олимпиады грамотно выполняли олимпиадные задания, они не должны воспринимать компьютер как черный ящик, исполняющий программы с помощью неизвестной магии. Все школьники в процессе решения олимпиадных задач должны понимать устройство функциональных компонент, из которых состоит компьютер, их характеристики, производительность и взаимодействие между ними. Понимание устройства и организации компьютера также позволяет писать более эффективные программы. При выборе используемой системы, они должны понимать значение характеристик различных компонентов, таких как тактовая частота процессора и объем памяти и т.п.

В рамках этого раздела для успешного выступления на олимпиаде по информатике школьники должны  знать/понимать:

·               логические переменные, операции, выражения;

·               системы счисления;

·               форматы представления числовых данных;

·               как представление данных с фиксированной разрядностью влияет на точность;

·               внутреннее представление нечисловых данных;

·               внутреннее представление символов, строк, записей и массивов;

·               организацию классической машины фон Неймана и ее основные функциональные блоки;

·               как инструкции представляются на машинном уровне;

·               основы ввода-вывода;

·               основные виды памяти;

·               основы управления памятью

·               использование прерываний для реализации управления вводом-выводом и передачей данных;

·               как осуществляется доступ к данным с магнитного диска;

·               интерфейсы, необходимые для поддержки мультимедиа;

уметь:

·               переводить числа из одной системы счисления в другую;

·               использовать математические выражения для описания функций простых последовательных и комбинационных схем;

·               преобразовывать числовые данные из одного формата в другой;

·               настраивать свое компьютерное место для выполнения поставленной задачи;

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

Основными темами этого раздела являются:

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

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

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

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

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

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

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

·                отличие примитивных пакетных систем от сложных многопользовательских операционных систем,

·               понятие логического уровня,

·               как вычислительные ресурсы используются прикладным ПО и

·               управляются системным ПО,

·               преимущества и недостатки использования прерываний,

·               страничная и сегментная организация,

·               различные способы экономии памяти

·               различия между механизмами, используемыми для взаимодействия с устройствами компьютера,

·               преимущества и недостатки прямого доступа к памяти,

·               требования к восстановлению после сбоев. 

Приобретенные знания этого раздела должны обеспечить участнику олимпиады уверенную работу в рамках используемой на олимпиаде операционной системы при реализации всех этапов решения олимпиадного задания с помощью компьютера.

Основными темами этого раздела являются:

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

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

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

Тематическое планирование

7 класс
№	Тема занятия	Сроки проведения	Корректировка
1	Кодирование информации	декабрь
2	Логика	январь
3	Логические задачи	февраль
4	Алгебра логики	март
5	Теория вероятности. Основы теории игр	апрель
6	Теория графов	май
7	Практикум по решению олимпиадных задач	июнь
8 класс
1	Основы анализа алгоритмов	сентябрь
2	Алгоритмические стратегии	октябрь
3	Рекурсии	ноябрь
4	Алгоритмы на строках	декабрь
5	Языки программирования	январь
6	Программирование на простейшем языке	февраль
7	Основные конструкции программирования	март
8	Переменные и типы данных	апрель
9	Типы структур данных	май
9 класс
1	Механизмы абстракции	сентябрь
2	Особенности программирования фундаментальных алгоритмов.	октябрь
3	Задачи на технику программирования	ноябрь
4	Решение задач на технику программирования	декабрь
5	Задачи на идею	январь
6	Решение задач на идею	февраль
7	Динамическое программирование	март
8	Программирование на языках высокого уровня	апрель
9	Программирование на языках высокого уровня	май

Список литературы

1. Алексеев А. В., Беляев С. Н. Подготовка школьников к олимпиадам  по информатике с 2. Волчёнков С. Г., Корнилов П. А., Белов Ю. А. и др. Ярославские олимпиады по информатике. Сборник задач с решениями. М.: БИНОМ. Лаборатория знаний. 2010. 405 с.

2. Долинский М. С. Алгоритмизация и программирование на TurboPascal: от простых до олимпиадных задач: учеб.пособие. СПб.:  Питер Принт, 2004. 240 с.

3. Кирюхин В. М. Всероссийская олимпиада школьников по информатике. М.: АПК и ППРО, 2005. 212 с.

4. Кирюхин В. М. Информатика. Всероссийские олимпиады. Вып. 3. М.: Просвещение, 2011. 222 с. (Пять колец).  

5. Окулов С. М. Основы программирования. М.: БИНОМ. Лаборатория знаний, 2005. 440 с.

6. Окулов С. М. Алгоритмы обработки строк: учеб.пособие. М.: БИНОМ. Лаборатория знаний, 2009. 255 с.

7. Скиена С. С., Ревилла М. А. Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям. М.: Кудицобраз, 2005. 416с.

Краткое описание документа:

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

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

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

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