Программа курса информатики/программирования

Составитель: С. Е. Столяр

Тематическая программа

Хронологическая последовательность тем определяется согласно общей граф-схеме.

Для удобства просмотра отдельные модули представлены также пятью подсхемами:

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

Граф-схема

1.1. Элементы теории множеств
       1.1.1. Терминология
       1.1.2. Операции
       1.1.3. Диаграммы
1.2. Алфавиты и нумерации
       1.2.1. Естественные и искусственные языки
       1.2.2. Алфавиты
       1.2.3. Системы счисления, перевод
1.3. Алгебра логики
       1.3.1. Терминология
       1.3.2. Операции и таблицы истинности
       1.3.3. Решение логических задач
1.4. Элементы комбинаторики
       1.4.1. Перестановки
       1.4.2. Размещения и сочетания
       1.4.3. Числа Фибоначчи и золотое сечение
       1.4.4. Треугольник Паскаля
       1.4.5. Разбиения
1.5. Информация
       1.5.1. Единицы измерения количества информации
       1.5.2. Оценка количества информации в сообщении
1.6. Рекуррентные соотношения
       1.6.1. Правильные рекуррентные соотношения
       1.6.2. Задачи и приложения
       1.6.3. L-системы 2
1.7. Операции и выражения, линейные бесскобочные записи
       1.7.1. Типы операций и выражений
       1.7.2. Скобочные и бесскобочные линейные записи
       1.7.3. Преобразование скобочных записей к префиксному виду
       1.7.4. Преобразование скобочных записей к постфиксному виду
1.8. Введение в теорию отношений и теорию баз данных 1
       1.8.1. Классификация БД
       1.8.2. Отношения
       1.8.3. Операции над отношениями
       1.8.4. БД реляционного типа
1.9. Элементы теории графов 1
       1.9.1. Таблицы-отношения
       1.9.2. Терминология теории графов
       1.9.3. Виды графов и приложения

2. Архитектура ЭВМ, представление данных, операционные системы

Граф-схема

2.1. Архитектура ЭВМ. Архитектура фон-неймановской вычислительной машины. Память
2.2. Машинное слово. Полусумматор и сумматор
2.3. Битовая арифметика
2.4. Целочисленная арифметика
2.5. Вещественная арифметика
2.6. Файловая система
2.7. Команды ОС, утилиты
2.8. Пакетная обработка команд ОС
2.9. Контроль данных, передача данных, протоколы 1
2.10. Видеопамять и устройства отображения
2.11. История ЭВМ

3. Структуры данных, модели данных и алгоритмы

Граф-схема

3.1. Понятие алгоритма. Способы описания алгоритма
       3.1.1. Алгоритм и его свойства
       3.1.2. Блок-схемы
       3.1.3. Граф-схемы
       3.1.4. Диаграммы
3.2. Вычислительная сложность алгоритмов
       3.2.1. Нотация Бахмана-Ландау
       3.2.2. ВременнАя сложность
       3.2.3. Емкостная сложность
3.3. Массивы
       3.3.1. Общие сведения
       3.3.2. Линейные массивы (векторы)
       3.3.3. Многомерные массивы
3.4. Динамическое программирование
3.5. Поиск элемента в векторе
       3.5.1. Постановка задачи
       3.5.2. Последовательный поиск
       3.5.3. Дихотомический поиск в упорядоченном векторе
3.6. Строки. Точные алгоритмы поиска образца
       3.6.1. Постановка задачи. Обзор методов
       3.6.2. Алгоритм .грубой силы.
       3.6.3. Алгоритм Бойера-Мура
       3.6.4. Алгоритм Кнута-Морриса-Пратта
       3.6.5. Алгоритм Рабина-Карпа
3.7. Сортировки вектора
       3.7.1. Постановка задачи
       3.7.2. O(n2)-сортировки вектора
       3.7.3. Двоичная куча на базе вектора и пирамидальная сортировка
       3.7.4. Быстрая сортировка вектора
       3.7.5. Сортировки вектора слиянием
       3.7.6. O(n)-сортировки линейного массива
3.8. Последовательности и файлы
       3.8.1. Задачи обработки строк-последовательностей
       3.8.2. Сортировки файла
3.9. Алгоритмы теории чисел и вычислительные алгоритмы
       3.9.1. Алгоритм Евклида
       3.9.2. Схема Горнера для полинома *
       3.9.3. Факторизация целого числа
       3.9.4. Длинная арифметика
       3.9.5. Приближенное вычисление определенного интеграла *
       3.9.6. Численное решение уравнения *
3.10. Комбинаторные алгоритмы 1
       3.10.1. Комбинаторные конфигурации и приложения
       3.10.2. Ханойские башни
       3.10.3. Перебор перестановок +
       3.10.4. Перебор сочетаний +
       3.10.5. Перебор разбиений +
3.11. Линейные динамические структуры данных
       3.11.1. Терминология. Разновидности линейных динамических структур
       3.11.2. Списки и операции, приложения
       3.11.3. Стеки, стековая арифметика; приложения
       3.11.4. Очереди и операции, приложения. Деки
       3.11.5. Задача о пути в лабиринте
3.12. Деревья
       3.12.1. Терминология, виды. Приложения
       3.12.2. Упорядоченное дерево
       3.12.3. Двоичное дерево, обходы
       3.12.4. Сильноветвящиеся деревья 1
3.13. Словари
       3.13.1. Словари и словарные операции
       3.13.2. Словарь на основе двоичного дерева поиска
       3.13.3. Словари на основе сильноветвящихся деревьев поиска +
       3.13.4. Словарь на основе хеш-таблиц 1
3.14. Упаковка данных
       3.14.1. Постановка задачи. Обзор методов
       3.14.2. 7-битное кодирование
       3.14.3. RLE и применение
       3.14.4. Посимвольное кодирование на основе кодового дерева
       3.14.5. Семейство алгоритмов Лемпела-Зива +
       3.14.6. Упаковка изображений +
3.15. Очереди с приоритетами 2
       3.15.1. Терминология, операции, приложения
       3.15.2. Двоичные кучи
       3.15.3. Биномиальные кучи
3.16. Алгоритмы на графах 2
       3.16.1. Терминология, определения. Компьютерные представления графа
       3.16.2. Обходы графа в глубину и в ширину
       3.16.3. Построение глубинного и широтного каркасов графа
       3.16.4. Поиск связных компонент графа
       3.16.5. Поиск мостов, точек сочленения и блоков в графе +
       3.16.6. Взвешенные графы. Построение минимального остова
       3.16.7. Построение матрицы достижимостей орграфа
       3.16.8. Кратчайшие пути между всеми парами вершин взвешенного графа
       3.16.9. Кратчайшие пути от заданной вершины взвешенного графа +
       3.16.10. Топологическая сортировка ациклического орграфа +
3.17. Алгоритмы классической криптографии 2
       3.17.1. Подстановочные шифры
       3.17.2. Перестановочные шифры
       3.17.3. Смешанная техника
3.18. Алгоритмы вычислительной геометрии 2
       3.18.1. Пересечение отрезков
       3.18.2. Принадлежность точки
       3.18.3. Построение выпуклой оболочки набора точек плоскости
       3.18.4. Поиск пар ближайших точек
       3.18.5. Поиск пар наиболее удалённых точек
3.19. Альтернативные алгоритмические системы 2
       3.19.1. Обзор алгоритмических систем
       3.19.2. Машина Тьюринга
       3.19.3. Алгоритмическая система Поста
       3.19.4. Марковские алгорифмы
3.20. Алгоритмические стратегии
       3.20.1. Разделяй и властвуй
       3.20.2. Алгоритмы с возвратом
       3.20.3. Жадные алгоритмы. Приложения
       3.20.4. Метод ветвей и границ. Приложения

4. Парадигмы программирования, языки и среды программирования

Граф-схема

4.1. Программирование на процедурном языке высокого уровня (Pascal, С/C++, Java или Python)
       4.1.1. Среда разработчика (Delphi, MinGW, Visual Studio, Eclipse или PyCharm)
       4.1.2. Код программы. Этапы обработки
       4.1.3. Структура программы
       4.1.4. Консольные приложения
       4.1.5. Типизация данных
       4.1.6. Простые типы и операции над ними
       4.1.7. Битовая арифметика. Контрольная сумма машинного слова
       4.1.8. Управляющие конструкции
       4.1.9. Технология отладки
       4.1.10. Организация ввода-вывода, контроль ввода
       4.1.11. Алгоритмы обмена
       4.1.12. Составные структуры данных
       4.1.13. Множества: операции, решение задач
       4.1.14. Подпрограммы. Процедуры и функции
       4.1.15. Реализация рекурсии
       4.1.16. Стандартные и пользовательские модули / библиотеки
       4.1.17. Строки и операции
       4.1.18. Массивы: ввод-вывод, решение задач (синхронная и асинхронная обработка)
       4.1.19. Массивы: реализация алгоритмов раздела 3, решение задач
       4.1.20. Записи, обработка и использование
       4.1.21. Указатели. Списки: реализация моделей и алгоритмов раздела 3.11.2.
       4.1.22. Реализация структур «стек» и «очередь»
       4.1.23. Реализация двоичных деревьев поиска
       4.1.24. Графические средства системы программирования
       4.1.25. Механизмы анимации, реализация
       4.1.26. Разработка интерфейсов пользовательских программ
4.2. Альтернативные парадигмы программирования: обзор
4.3. Программирование с поддержкой ООП (Object Pascal, C++, Java или Python)
       4.3.1. Объекты и классы
       4.3.2. Коллекции и контейнеры
       4.3.3. Принципы ООП
       4.3.4. Компьютерное моделирование средствами ООП 2
       4.3.5. Анимация средствами ООП 2
       4.3.6. Критика ООП
4.4. Языки сценариев 1
       4.4.1. Пакетная обработка команд ОС
       4.4.2. Язык разметки HTML: основные средства, каскадная таблица стилей, вопросы дизайна страниц, средства валидации
       4.4.3. Введение в JavaScript 2
       4.4.4. Стековый язык Postscript 2
       4.4.5. Объектно-ориентированное программирование на языке Java 2

5. Пользовательские средства и технологии

Граф-схема

5.1. Правовые аспекты использования ПО и Web-ресурсов
5.2. Работа в локальной сети ФТШ
5.3. Файловый менеджер, работа с файлами
5.4. Обработка текста
       5.4.1. Основные кодировки, конвертирование
       5.4.2. Простой текстовый редактор (уровня NotePad)
       5.4.3. Текстовый редактор с расширенными возможностями (уровня NotePad++)
5.5. Обработка изображений
       5.5.1. Простой графический редактор (уровня MS Paint)
       5.5.2. Обработка растровой графики (редактор уровня Gimp) +
5.6. Кодирование данных
       5.6.1. Кодирование на основе алфавита
       5.6.2. Разновидности двоично-десятичных кодов
       5.6.3. Избыточное кодирование, приложения
       5.6.4. Телеграфный код: история, устройство
       5.6.5. Штрих-коды: история, разновидности, устройство
       5.6.6. EAN, ISBN: история, устройство
5.7. Основы документоведения 2
       5.7.1. Введение в делопроизводство
       5.7.2. Виды документов
       5.7.3. Классификации УДК и ББК: история, назначение, устройство
       5.7.4. Правила и стандарты форматирования документа
5.8. Офисные технологии
       5.8.1. Текстовый процессор (уровня MS Office Word)
       5.8.2. Электронные таблицы (уровня MS Office Excel) 3
       5.8.3. Средства создания презентаций (уровня MS PowerPoint) 3
       5.8.4. Реляционные базы данных (уровня MS Office Access) 3
5.9. Работа в Web
       5.9.1. Браузеры. Поиск в Web
       5.9.2. Web-сервисы
       5.9.3. Электронная почта
5.10. Полиграфические технологии +
       5.10.1. Введение в полиграфию
       5.10.2. Набор текста в TeX-системах
       5.10.3. Графика в TeX-системах
       5.10.4. Создание презентаций в TeX-системах
5.11. Обработка медиа 3
5.12. Математические пакеты 3

Обозначения

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

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

3 Отмеченные таким знаком темы обычно предлагаются учащимся к самостоятельному изучению по рекомендуемым источникам.

* Отмеченные таким знаком темы обычно обсуждаются в курсе математики. Включение некоторых из них в план курса информатики/программирования . на усмотрение учителя.

+ Отмеченные таким знаком темы обычно обсуждаются в рамках факультативных курсов:

Включение некоторых из них в план основного курса — на усмотрение учителя.