Чему учить?
В настоящее время с точки зрения обучения программированию можно выделить несколько категорий учащихся. Во-первых, это ученики основной школы, курс информатики в которой преподается за счет часов вариативной части Базового учебного плана. Министерством образования рекомендован “Обязательный минимум содержания образования”, который условно имеет два уровня.
Уровень А определяет содержание образования по информатике, обязательное для всех учащихся общеобразовательных школ. Согласно ему учащиеся должны освоить реализацию основных алгоритмических конструкций в одном из языков программирования, познакомиться с простыми типами данных и массивами как способом представления информации. То есть при подборе задач для основной школы внимание должно уделяться преимущественно задачам, способствующим отработке применения основных алгоритмических конструкций с использованием простых типов данных и массивов.
Уровень Б соответствует углубленного курса информатики, который преподается в основном в физико-математических классах. Помимо перечисленных выше знаний в области программирования, учащиеся таких школ должны уметь оперировать всеми основными типами данных одного из современных алгоритмических языков, включая объекты, использовать при разработке программ процедуры, функции и операции над объектами и разрабатывать программы методом последовательной детализации. В требованиях к результатам обучения на таком уровне говорится, что учащиеся должны уметь расписывать на языке программирования типовые алгоритмы, такие, как: поиск минимального и максимального элемента в массиве, упорядочивание элементов массива, определение количества слов в тексте - и т.д. Данные требования фактически и определяют содержание обучения для такой категории учащихся.
Остается вопрос, как увязать все эти требования к тому малому количеству часов, которое выделено учителям на данном этапе. И еще один аспект – олимпиадные задачи.
Задачи, предлагаемые на олимпиадах, охватывают различные разделы информатики и программирования. Тем не менее их темы, а также основные алгоритмы решения возможно формализовать. Помимо традиционных учебных тем, зачастую эти задачи используют идеи и приемы, применяемые в профессиональном программировании, например, идеи шифрования, принципы организации поиска в большом объеме информации, синтаксический и семантический разбор выражений, методы решения NP-полных задач и т.д.
Рассмотрим основные классы задач, изучение которых будет необходимо для качественной подготовки учащихся в плане обучения программированию.
1. Задачи на операции ввода и вывода . Подобный класс задач важен, так как, выполняя подобные задания, учащиеся смогут понять формальные требования, которые предъявляются к программам при их автоматическом тестировании.
2. Задачи на оператор присваивания. Несмотря на кажущуюся простоту, в данный раздел могут быть включены задачи различной сложности. В частности, требование не использовать в программе условный оператор и операторы цикла переводит ряд элементарных задач в задачи повышенной сложности. Такое ограничение с методической точки зрения можно рассматривать как работу с исполнителем, имеющим ограниченный набор команд.
Пример. Обозначим дни недели числами от 1 — понедельник до 7 — воскресенье, соответственно. Программа должна вводить с клавиатуры два натуральных числа: 0 < N < 32 — число в текущем месяце и 0 < M < 8 — день недели для первого числа в текущем месяце. Вывести на экран число от 1 до 7, обозначающее, на какой день недели приходится число N.
Пример. Bвести с клавиатуры 2 целых числа: 0 <= H < 12, 0 <= M < 60, указывающие момент времени H часов M минут. Определить и вывести на экран наименьшее число полных минут, которое должно пройти до того момента, когда часовая и минутная стрелки на циферблате совпадут.
При решении данного класса задач учащиеся осваивают основные операции и функции изучаемого языка программирования. Особое внимание при этом уделяется арифметике остатков, знания по которой, как показывает практика, у учащихся недостаточны. Однако именно операции целочисленной арифметики имеют важную роль в программировании.
3. Задачи на логические выражения. При изучении логических выражений полезным является выполнение следующего практического задания.
Каждому учащемуся выдается индивидуальный рисунок. То есть на координатной плоскости изображены линии, описываемые уравнениями окружности, прямой, параболы, ромба, прямоугольника и т.п. (сложность рисунка зависит от категории учащихся). Несколько областей, ограниченных этими линиями, заштрихованы. Требуется описать всю заштрихованную часть плоскости с помощью одного логического выражения. Программа должна запрашивать с клавиатуры координаты (x, y) некоторой произвольной точки плоскости и определять, принадлежит ли точка с координатами (x, y) заштрихованной области. Ответ выдать в следующем виде: true, если точка с координатами (x, y) принадлежит заштрихованной области, и false, если точка с координатами (x, y) не принадлежит ей. При выполнении задания от учащихся следует требовать, чтобы для описания каждой области была введена своя логическая переменная, что упрощает процесс отладки и поиска ошибок при приеме задания. Основное логическое выражение конструируется только из таких переменных.
4. Условный оператор. Цель данного раздела — научить учащихся составлять алгоритмы с использованием простых и вложенных операторов условия и выбора. Обратите внимание на последовательность – сначала логические выражения, потом условный оператор.
5. Операторы цикла. Основные классы задач, относящиеся к данному разделу, это задачи на обработку числовых последовательностей без использования массивов для их хранения, включая нахождение НОД или НОК для последовательностей натуральных чисел, задачи на рекуррентные соотношения и суммирование числовых рядов. В последнем случае важное значение имеет эффективность программы. Так, при суммировании рядов, аналогичных рядам Тейлора, операции возведения в степень или циклы для вычисления целочисленной степени или факториала применяться не должны. Вместо этого каждое следующее слагаемое должно выражаться через предыдущее с помощью основных арифметических операций.
6. Строковые величины. Цель данного раздела – ознакомить учащихся со строковым типом данных и показать приемы обработки информации такого типа при помощи базовых операций: конкатенации, «вырезка» справа, слева и с любой позиции строки.
7. Простейшие операции над одномерными массивами. Цель данного раздела - научить учащихся правильно описывать, вводить, выводить и обрабатывать одномерные массивы. Стандартными в данном разделе следует считать задачи на поиск максимального и минимального элементов, сдвиг и перестановку элементов массива и, наконец, его сортировку. Следует использовать также нетривиальные задачи, при решении которых используются одномерные массивы, например вычислить по схеме Горнера значение полинома или такие.
Пример. С клавиатуры вводятся два целых числа 0 < m, n < 101, а затем m + n элементов целочисленных элементов массива, каждый из которых по модулю не превосходит 32 767. Не используя дополнительных массивов, требуется переставить местами первые n и последующие m элементов массива. Вывести на экран полученный в результате перестановки массив, разделяя его элементы пробелами.
Пример. С клавиатуры вводится некоторый текст на английском языке, заканчивающийся точкой. Распечатать сведения о том, сколько каких английских букв в тексте. Учесть, что в тексте могут встречаться символы, отличные от латинских букв. Прописные и строчные буквы при подсчете не различать. Вывести на экран 26 чисел, каждое в новой строке, первое из которых соответствует количеству букв a в тексте, второе — букв b и т.д.
8. Двумерные массивы. Набор задач – тот же, что и для одномерных массивов. Обработку двумерных массивов следует рассматривать как усложненный алгоритмический (не математический!) вариант простых массивов. Согласитесь, что основным усложнением будет правильное использование вложенных циклов для решения задач с использованием двумерных массивов.
9. Процедуры и функции . Наиболее удачным примером для применения процедур на начальном этапе обучения программированию являются задачи сортировки и поиска. Другой класс задач, требующий естественного применения процедур и функций, - простейшие численные методы интегрирования, а также решение трансцендентных уравнений методами деления пополам, хорд, касательных или итераций.
Дополнительными к перечисленным категориям являются программирование графики и программирование операций с файлами.
После изучения основ программирования на любом алгоритмическом языке круг решаемых задач существенно зависит от категории учащихся.. Сформулируем лишь некоторые из тем, задания по которым могут быть полезны для широкого круга учащихся.
1. Задачи по системам счисления. Решение задач данного типа позволяет не только овладеть данным разделом теоретической информатики, но и усовершенствовать технику программирования.
2. Задачи на “длинную арифметику”. Помимо традиционных задач на сложение, вычитание, умножение и целочисленное деление “длинных” чисел (порядка 20-30!), в данный раздел можно включить различные задачи, получить точный ответ в которых можно, лишь самостоятельно реализовав те или иные арифметические операции. Для хранения "длинных" чисел используется массив, или стек, реализованный с помощью списка. Типы задач: поиск наибольшего общего делителя двух "длинных" чисел; поиск наименьшего общего кратного двух "длинных" чисел; извлечение квадратного корня из "длинного" числа и т.д.
3. Задачи на использование динамических структур данных. Это такие задачи, как: список, стек, очередь, дерево, сбалансированное дерево бинарного поиска и т.п.
4. Алгоритмы на графах. В частности, наиболее часто в программировании встречаются следующие задачи: обход графа в глубину и в ширину, подсчет компонент связности, построение минимального остовного дерева, поиск кратчайшего пути в графе, нахождение эйлерова цикла, задача коммивояжера (гамильтонов цикл), задачи о размещениях. Следует отметить, что здесь очень важна очень мощная математическая подготовка как учащихся, так и самого учителя.
5. Целочисленные задачи линейного программирования. Это задача о назначениях, задача о максимальном потоке, общая задача линейного программирования, при решении которой используется симплекс-метод.
6. Задачи на полный перебор вариантов, при решении которых используется перебор с возвратом с применением метода ветвей и границ и других методов сокращения перебора. В частности, задачи на программирование игр и головоломок с использованием отсечений.
7. Комбинаторные задачи . Для каждой из основных комбинаторных конфигураций — множество всех подмножеств, сочетания, перестановки, размещения и т.п. — можно поставить следующие задачи. Для заданных входных параметров подсчитать количество всех возможных конфигураций того или иного типа, сгенерировать все конфигурации соответствующего типа, определить конкретную конфигурацию по ее номеру в лексикографическом порядке конфигураций и, наоборот, по конфигурации определить ее номер, для любой заданной конфигурации построить следующую в лексикографическом порядке.
8. Задачи вычислительной геометрии и компьютерной графики. Сюда можно отнести множество задач, решение которых должно быть получено в графическом представлении. Самыми простыми задачами такого рода можно считать такие.
Пример. Построить столбиковую (гистограммную) интерпретацию одномерного массива, в которой максимальный элемент выделен красным цветом, минимальный – зеленым, все остальные элементы представляются желтым цветом.
Пример. Найти площадь фигуры, изображенной на экране при помощи метода Монте-Карло.
9. Задачи по теории формальных грамматик и конечных автоматов. Начиная с проверки правильности записи арифметических выражений и подсчета их значений до элементов интерпретации и компиляции программ.
10. Задачи криптографии. Следует рассмотреть задачи, основанные на алгоритмах шифрации. Этот тип задач плотно связан с задачами на перебор.
Итак, мы с вами рассмотрели основной набор задач, который следует решать с учащимися на базовых занятиях по программированию, а так же с помощью спецкурса.
Отдельным вопросом можно считать олимпиадные задачи, но тут, кроме простого практикума по решению как можно большего числа задач олимпиадного типа с выработкой навыка различения типов этих задач, на мой взгляд, предложить нечего.
Практика, практика и еще раз практика.
