2 направление

Методические рекомендации по изучению тем для подготовки к олимпиадам по информатике и ИКТ

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

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

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

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

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

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

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

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

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

1. Раздел «Математические основы информатики» школьники должны

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

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

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

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

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

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

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

уметь:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• нотации для описания объема вычислений, производимых алгоритмом сложность по времени и памяти простых алгоритмов;

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

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

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

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

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

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

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

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

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

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

уметь:

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

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

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

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

• использовать нотации для описания объема вычислений, производимых алгоритмом и асимптотических оценок;

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

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

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

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

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

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

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

5. Рекурсия.

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

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

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

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

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

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

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

3. Раздел «Основы программирования»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

уметь:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4. Раздел «Средства ИКТ»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

уметь:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 Раздел «Основы технологии программирования»

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

• назначение и состав сред программирования;

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

• свойства проектирования «хорошего» программного обеспечения;

• отличия между различными типами и уровнями тестирования (тестирование модулей, интеграционное тестирование, системное тестирование) программных продуктов;

уметь:

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

• использовать инструментальные средства при разработке программного продукта; разработать программу в виде готового программного продукта;

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

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

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

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

7. Раздел «Методы вычислений и моделирование»

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

• понятия ошибки, устойчивости, машинной точности и погрешности приближенных вычислений;

• источники погрешности в приближенных вычислениях;

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

• понятия модели и моделирования, основные типы моделей;

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

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

уметь:

• вычислять оценку погрешности приближенных вычислений;

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

• формализовывать объекты моделирования;

• разрабатывать компьютерные модели простейших объектов;

• использовать при решении практических задач компьютерные модели в виде «черного ящика»;

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

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

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

8 Раздел «Компьютерные сетевые технологии» в информатике.

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

• иерархическую многоуровневую структуру сетевых архитектур;

• наиболее важные сетевые стандарты;

• роли и ответственности клиентов и серверов для различных приложений;

• проблемы управления сетями, возникающие из-за угроз безопасности, включая вирусы, "червей", Троянских коней и атак, направленных на инициирование отказов в обслуживании;

• области применения мобильных компьютеров в настоящее время и в перспективе, их возможности, ограничения и потенциал,

уметь:

• эффективно использовать ряд распространенных сетевых приложений, включая электронную почту, web-браузеры, web-курсы и системы мгновенной передачи сообщений;

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

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

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

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

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

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

Индивидуальная карта учащегося

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

1. Владеть технологией программирования с использованием не менее двух языков программирования, уметь сравнивать их возможности. Для подготовки к IOI - владение языком Си (версии см. на сайте IOI).

2. Владеть математическими основами решения алгоритмических задач по темам, обозначенным содержанием программы подготовки к олимпиадам по информатике (не ниже (*) - для подготовки к заключительному этапу ВсОШ, не ниже (**) для подготовки к IOI).

3. Свободно вслепую владеть клавиатурным набором.

4. Свободно владеть средствами отладки и тестирования программ, знать принципы написания тестов к программам.

5. Быть знакомым с операционной системой Линукс.

6. Ежедневно самостоятельно решать задачи из коллекции задач ВсОШ/IOI, знать возможности современных систем автоматической проверки решений и уметь ими свободно пользоваться. Вести дневник решений в форме таблицы – год ВсОШ/IOI, номер тура, номер задачи, тема программы подготовки, набранный балл при самостоятельном решении. Стремиться доводить все решения до 100 балльной оценки.

7. Обязательно участвовать в международных и российских он-лайн соревнованиях в течение года.

8. Участвовать и успешно продвигаться по рейтингу в Codeforces /TopCoder.

9. Иметь рекомендованную подборку книг по олимпиадной информатике и математике, получить на сборах уточнения по личной библиотеке книг. Учиться внимательно работать с книгой.

10. Знать правила для участия в ВсОШ/ IOI, владеть элементарными навыками разговорной речи и чтения текстов задач на английском языке.

@akaVeta