Программа
ресурсного центра по подготовке к республиканской олимпиаде по учебному предмету «Информатика»
Цель деятельности:
выявление образовательных потребностей, консультирование педагогических работников, оказание им информационно-методической поддержки по актуальным вопросам преподавания информатики
Задачи центра:
* Продолжить развитие информационной среды ГУО «Средняя школа №2 г.Мстиславля»;
* Обеспечивать эффективную информационно-методическую поддержку педагогов в вопросах информатизации образования;
* Совершенствовать информационно-методическое обеспечение преподавания учебного предмета «Информатика»;
* Формировать банк цифровых образовательных ресурсов для преподавания учебного предмета «Информатика»;
* Создать условия для организации работы с одарёнными учащимися в предметной области «Информатика»;
* Содействовать формированию информационной компетентности обучающихся, через проведение конкурсов, олимпиад и дистанционного обучения.
Содержание программы
Алгоритмизация и программирование
1. Линейные алгоритмы. Реализация линейных алгоритмов на языке программирования.
2. Условный оператор. Оператор выбора.
3. Оператор ветвления в полной и сокращенной форме. Составление разветвляющихся алгоритмов.
4. Составной оператор. Вложенные алгоритмические конструкции.
5. Составление разветвляющихся алгоритмов с использованием блок-схем и языка программирования.
6. Оператор выбора. Составление алгоритмов, содержащих оператор выбора.
7. Составление алгоритмов с вложенными алгоритмическими конструкциями.
8. Команда повторения.
9. Составление циклических алгоритмов.
10. Реализация циклических алгоритмов с использованием блок-схем и языка программирования.
11. Решение задач с использованием команд ветвления и повторения.
Целочисленная арифметика
1.Алгоритм Евклида. Нахождение НОД(а,b), НОК(a,b) рекурсивная и прямая реализация
2. Определение простоты числа.
3. Нахождение всех простых чисел из промежутка (a,b).
4. Разложение данного натурального числа на простые множители.
5. Дано разложение данного натурального числа на простые множители. Найти все делители этого числа.
6. Нахождение всех делителей натурального числа.
7. Нахождение цифрового корня натурального числа.
8. Алгоритм Евклида. Нахождение НОД(а,b), НОК(a,b) рекурсивная и прямая реализация
9. Длинная арифметика:
a) Считывание длинного числа из файла.
b) Запись длинного числа в файл.
c) Сложение двух длинных чисел
d) Умножение длинного числа на короткое в системе счисления с основанием 1000.
e) Умножение длинного числа на длинное.
f) Деление длинного на короткое
g) Вычисление n! и степени an при маленьких и больших значениях a и n, рекурсивная и нерекурсивная реализация.
h) Индийский алгоритм вычисления an
i) Дано натуральное число N. Найти последнюю ненулевую цифру суммы a1+a2+…+ak, где N=p1a1*p2a2*…*pkak.
j) Дано натуральное число N. Найти последнюю ненулевую цифру числа N!
k) Даны натуральные числа N и M. Найти последнюю ненулевую цифру числа сочетаний C из N по M.
l) Даны натуральные числа N и M. Вычислить число сочетаний C из N по M.
m) Найти все натуральные числа, не превосходящие данного натурального N, десятичная запись которых есть строго убывающая или строго возрастающая числовая последовательность. (длинная арифметика).
Одномерные массивы
1. Объявление и использование массивов.
2. Создание массивов:.вручную, по формуле, генератором случайных чисел, чтение из файла
3. Виды сортировок. Внешняя и внутренняя сортировка
4. Сортировка выбором.
5. Сортировка "пузырьком".
6. Сортировка Шелла.
7. Сортировка слиянием.
8. Внешняя сортировка слиянием.
9. Кучи. Сортировка с помощью кучи.
10. Сортировка подсчётом.
11. Хэширующая сортировка.
12. Цифровая сортировка
13. Сквозной поиск элемента в массиве.
14. Бинарный поиск элемента в массиве.
15. Извлечение корня n-ой степени из данного натурального числа.
16. Вычисление значения многочлена по схеме Горнера.
Двумерные массивы
Создание двумерных массивов.
Задачи на двумерные массивы:
1 Нахождение максимального и минимального элементов массива.
2 Сортировка массива по возрастанию и убыванию в строках и столбцах.
3 Поменять местами первую и последнюю строки (столбцы).
4 Отобразить массив симметрично относительно горизонтальной оси.
5 Отобразить массив симметрично относительно вертикальной оси.
6 Отобразить массив n*n симметрично относительно главной диагонали
7 Отобразить массив n*n симметрично относительно побочной диагонали
8 Повернуть массив n*n против часовой стрелки на 90 градусов.
9 На шахматной доске стоит слон и еще несколько фигур. Сколько клеток контролирует слон?
Создание трехмерных массивов.
Генерация комбинаторных объектов
1. Понятие "комбинаторных" алгоритмов.
2. Получение комбинаторных объектов.
3. Задачи:
- Сгенерировать все последовательности длины n из чисел от 1 до k.
- Сгенерировать все подмножества n-элементного множества.
- Сгенерировать все перестановки чисел от 1 до N.
- Сгенерировать все k-элементные подмножества n-элементного множества.
- Сгенерировать все представления числа N в виде суммы натуральных чисел.
- Код Грея и сходные задачи.
- Генерация перестановок методом транспозиции соседних элементов.
- Числа Каталана. Расстановка скобок.
Обработка текста
1.Процедуры и функции обработки текста на Паскале
2. Функции eof и eoln.
3. Функции seekeof и seekeoln.
4. Посимвольная обработка текста.
5. Отличие процедур read и readln.
5. Поиск заданной подстроки в тексте. Алгоритм Бойера-Мура.
7. Использование хэш-функции для поиска произвольной подстроки в строке.
8. Рекурсивный синтаксический анализ скобочных выражений.
Динамическое программирование
Концепция динамического программирования Сохранение решений, подзадач, которые приходится решать повторно или несколько раз. Построение динамических таблиц промежуточных результатов.
Структуры данных
1. Элементарная структура данных - запись.
Линейный список.
2. Специальные структуры данных: стек, очередь, дек.
3. Деревья. Упорядоченные деревья.
4. Обходы деревьев.
5. Двоичные деревья, деревья поиска.
6. Обходы двоичных деревьев.
7. Поиск элемента в дереве поиска.
8. Добавление/удаление элемента.
9. Характеристики кучи.
Перебор с возвратом
1. Перебор и его значение в программировании.
2. Методы оптимизации перебора.
3. Задача о расстановке ферзей.
4. Задача об обходе конём шахматной доски.
5. Задача комивояжора.
Алгоритмы на графах
1. Способы представления графа.
2. Обход в глубину.
3. Обход в ширину.
4. Кратчайшие пути.
1 Алгоритм Форда-Беллмана.
2 Алгортим Флойда.
3 Алгоритм Дейкстры
5. Поиск Эйлерова цикла
6. Поиск Гамильтонова цикла
7. Поиск компонент сильной связности
8. Поиск мостов
9. Поиск точек сочленения
10. Поиск максимального потока
11. Топологическая сортировка.