Решение нестандартных задач по информатике

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

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

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

Цели изучения курса:

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

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

·      формирование навыков совместной деятельности и исследовательской работы;

Задачи курса:

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

·      научить отлаживать программы и составлять тестовые примеры.

Программа рассчитана на 1 час в неделю в 11 классе (всего 34 часа в год).

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

Требования к уровню
подготовки выпускников 11 класса

В результате изучения информатики и ИКТ на базовом уровне ученик должен

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

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

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

·                назначение и функции операционных систем;

уметь

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

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

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

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

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

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

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

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

·                соблюдать правила техники безопасности и гигиенические рекомендации при использовании средств ИКТ;

использовать приобретенные знания и умения в практической деятельности и повседневной жизни для:

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

·                ориентации в информационном пространстве, работы с распространенными автоматизированными информационными системами;

·                автоматизации коммуникационной деятельности;

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

·                эффективной организации индивидуального информационного пространства.

СОДЕРЖАНИЕ ПРОГРАММЫ

Разбор задач на предмет нестандартности в программировании 2ч

Примеры задач: числа Фибоначчи, простые числа, числа треугольника Паскаля, поиск кратчайшего пути, вычисление чисел π и е, вычисление n! (вычисление первых n чисел натурального ряда). Влияние ограничений на выбор структуры данных и алгоритма решения задачи. Анализ алгоритмов на эффективность и быстроту вычислений.

Пример олимпиадной задачи с форматами входных выходных данных, с ограничением по времени, границами изменения входных данных. Разбор этой задачи на предмет нестандартности в программировании.

Стандартные алгоритмы в программировании 8ч

Рассмотрение отдельных тем в теории алгоритмов:

1)      Алгоритмы работы с целыми числами: алгоритм Евклида для вычисления НОД и НОК; решето Эратосфена для нахождения простых чисел; нахождение суммы цифр целого числа; разложение числа на простые множители; палиндромы, совершенные числа.

2)      Алгоритмы для работы с одномерными массивами: вычисление суммы и произведения элементов массива; нахождение наибольшего и наименьшего элементов массива; поиск элементов  в массиве; сортировка массивов.

3)      Алгоритмы для работы с двумерными массивами: произведение матриц; транспонирование матриц; симметричность матриц; алгоритм для поиска пути в лабиринте.

4)      Алгоритмы для обработки строк: выделение слова в тексте; поиск, удаление, вставка и редактирование символов или слов в тексте; методы кодирования информации.

5)      Алгоритмы для решения геометрических задач: нахождение расстояния между точками, прямыми, плоскостями; вычисление площади и объёмов простых геометрических фигур; определение вершин правильного многоугольника.

6)      Алгоритмы для набора с графами: представление графа; алгоритм нахождения минимального пути; закрашивание вершин графа; обход дерева графа.

7)      Алгоритмы на полный перебор: алгоритмы решения задач о рюкзаке  и о коммивояжёре.

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

1)      Простые типы:

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

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

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

d.      Логический тип.

e.       Указатель на адрес в памяти компьютера; понятие кучи.

2)      Структурированные типы:

a.       Множества, их представление в памяти компьютера, основные операции с ними.

b.      Файлы: текстовые и типизированные.

c.       Одномерные и двумерные массивы; ввод и вывод из файла. Динамические массивы.

d.      Записи. Списки, стеки, деки, очереди кА тип данных для динамического представления записей. Двоичные деревья как представление разветвлённого графа.

Понятие «тестирование» и разработка тестов к задачам 2ч

Основные методы работы с текстовым файлом. Разработка тестов. Составление вспомогательной программы.

Методы отладки программ 2ч

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

Решение олимпиадных задач 8ч

Разбор задач с прошедших олимпиад. Проверка программ на тестируемой системе (http://acm.timus.ru, http://zvn.by.ru)

Творческий проект 4ч

Составить задачу, поставить ограничения на ввод данных, предложить методы решения задачи или составить алгоритм её решения.

Учебно-тематический план 11 класс

№ п/п	Раздел	Кол-во часов (всего)	В том числе
			проект	практическая работа
1	Разбор задач на предмет нестандартности в программировании	2
2	Стандартные алгоритмы в программировании	7		7
3	Анализ структур данных и примеры их использования	9		8
4	Понятие «тестирование» и разработка тестов к задачам. Методы отладки программ	3		2
5	Решение олимпиадных задач	8		8
6	Творческий проект	4	1
	Итого:	34	1	25

Поурочное планирование 11 класс

Тема раздела	№ урока	Тема урока
Разбор задач на предмет нестандартности в программировании 2 часа	1	Примеры задач: числа Фибоначчи, простые числа, числа треугольника Паскаля, поиск кратчайшего пути, вычисление чисел π и е, вычисление n!
	2	Пример задачи с форматами входных выходных данных.
Стандартные алгоритмы в программировании 7 часов	3 (1)	Алгоритмы работы с целыми числами.
	4 (2)	Алгоритмы для работы с одномерными массивами.
	5 (3)	Алгоритмы для работы с двумерными массивами.
	6 (4)	Алгоритмы для обработки строк.
	7 (5)	Алгоритмы для решения геометрических задач.
	8 (6)	Алгоритмы для набора с графами.
	9 (7)	Алгоритмы на полный перебор.
Анализ структур данных и примеры их использования 9 часов	10 (8)	Представление простых чисел в памяти компьютера и ограничения на каждый тип.
	11 (1)	Представление вещественных чисел в памяти компьютера и ограничения на каждый тип.
	12 (2)	Представление символов и строк в памяти компьютера и ограничения на каждый тип.
	13 (3)	Логический тип. Указатель на адрес в памяти компьютера; понятие кучи.
	14 (4)	Множества, их представление в памяти компьютера, основные операции с ними.
	15 (5)	Файлы: текстовые и типизированные.
	16 (6)	Одномерные и двумерные массивы; ввод и вывод из файла. Динамические массивы.
	17 (7)	Записи. Списки, стеки, деки, очереди кА тип данных для динамического представления записей.
	18 (8)	Основные методы работы с текстовым файлом.
Понятие «тестирование» и разработка тестов к задачам. Методы отладки программ 3 часа	19 (1)	Разработка тестов. Составление вспомогательной программы.
	20 (2)	Пошаговое прохождение выполнения программы. Просмотр изменения значений переменных и выражений во время выполнения программы.
	21 (3)	Отладка с заходом в процедуры и без захода. Ключи компиляции.
Решение олимпиадных задач 8 часов	22 (1)	Решение олимпиадной задачи
	23 (2)	Решение олимпиадной задачи
	24 (3)	Решение олимпиадной задачи
	25 (4)	Решение олимпиадной задачи
	26 (5)	Решение олимпиадной задачи
	27 (6)	Решение олимпиадной задачи
	28 (7)	Решение олимпиадной задачи
	29 (8)	Решение олимпиадной задачи
Творческий проект 4 часа	30 (1)	Выполнение творческого проекта
	31 (2)	Выполнение творческого проекта
	32 (3)	Выполнение творческого проекта
	33 (4)	Выполнение творческого проекта

Перечень учебно-методических средств обучения

1.      Алгоритмизация и программирование в школьном курсе информатики. Учебно-методическое пособие. Е.В.Андреева. Газета «Информатика». Первое сентября, № 14, 16-2008

2.      Основы алгоритмизации и программирования на языке Pascal. Н.Е.Тимошевская, Е.А.Пёрышкина. Учебное пособие. Рекомендовано Российской академией образования к использованию в образовательных учреждениях, реализующих образовательные программы общего образования. Томск, 2005.

3.      Информатика: А.И. Сенокосов, А.Г Гейн. Учеб. для 8-11 классов с углубленным изучением информатики и программирования.-М.: Просвещение, 1995.

4.      Основы алгоритмизации и программирования на языке Pascal. Л.А.Татарникова. Учебное пособие. Рекомендовано Российской академией образования к использованию в образовательных учреждениях, реализующих образовательные программы общего образования. Томск, 2008.