Элементы комбинаторики в содержании начального курса информатики

Комбинаторика - это раздел математики, посвященный решению задач выбора и расположения элементов некоторого конечного множества в соответствии с заданными правилами.

Способы решения комбинаторных задач делятся на две группы:

1)неформальные;

2)формальные.

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

К неформальным способам решения комбинаторных задач относят полный (непосредственный, хаотичный) перебор. Это самый элементарный способ, так как он не требует знания определений и формул. Поэтому именно его целесообразно использовать в начальной школе.

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

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

В начальной школе такой способ решения не используется, хотя имеются исследования (Керовой Г.В., Солнышко С.В., Целишевой И.И., Румянцевой И.Б., Ермаковой Е.С.), в которых отмечается, что младшие школьники способны усвоить правила суммы и произведения.

Учащиеся начальных классов встречаются с элементами комбинаторики не только на уроках математики, но и информатики. При этом дети

· знакомятся с понятием комбинаторной задачи (на уровне представления);

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

· приобретают умение решать комбинаторные задачи практическим и графическим способами.

В основе изучения элементов комбинаторики лежат следующие принципы:

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

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

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

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

1 этап. Подготовительный (свойства предметов, отношений).

Сложность комбинаторных задач заключается в том, что при их решении должна быть выбрана такая система перебора, которая давала бы полную уверенность в том, что рассмотрены все возможные случаи (без повтора комбинаций).

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

В основе комбинаторных действий, в частности перебора всех возможных вариантов, лежат действия с конечными множествами. Объективный анализ ситуации, описанной в комбинаторной задаче, и правильное выполнение операций с множествами, о которых в ней идет речь, предполагают:

· владение рядом логических и теоретико-множественных понятий («некоторый», «каждый», «все», «отдельные», «множество», «элемент множества», «часть», «целое»);

· понимание смысла логических связок И, ИЛИ;

· умение устанавливать (выявлять) заданные отношения между элементами множеств и между множествами.

Для подготовки к изучению элементов комбинаторики целесообразно предлагать учащимся задачи на группировки по различным признакам, задачи типа «составь всевозможные равенства с числами», на составление определенной суммы различными наборами монет, допускающие различные варианты решения.

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

В программе А.В.Горячева «Информатика в играх и задачах» используются различные игры.

Игра «Угадай, сколько фишек в каждой руке».

Учитель объявляет, что у него в руке 7 фишек. После этого он за спиной раскладывает их по обеим рукам (например, в одной руке 3 фишки, а в другой - 4).

Затем учитель просит угадать, сколько фишек у него в каждой руке. Дети могут перебирать все возможные варианты числа семь. Тот, кто угадает, тот победил. Фишек у учителя может быть 8, 9, 11 или любое другое число.

Игра «Займи домик».

На доске рисуется домик, на крыше проставляется число, которое дети будут раскладывать. Должны быть перебраны все возможные варианты состава этого числа (рис. 43).

Рис. 43

Далее можно таким же образом представить числа 7, 8, 9 или любое другое число.

2 этап. Решение комбинаторных задач на основе практических действий

На данном этапе комбинаторные задачи предлагаются детям как задания, основная цель которых заключается в предметной интерпретации словесной модели.

Основным способом выполнения комбинаторных упражнений является полный (хаотичный), а затем системный перебор. Термин «комбинаторная задача» учащимся не сообщается.

Впервые ставится вопрос о различных вариантах размещения элементови их количестве.

Например, у каждого учащегося имеются фигуры разного цвета и размера: три круга (красный, желтый, зеленый) и два треугольника (желтый и зеленый) (рис. 44).

Рис. 44

В беседе с детьми учитель поясняет, что эти фигуры обозначают фрукты разного цвета: три яблока и две груши. Он сообщает, что к ним в гости на занятие пришли герои сказки (три медведя и девочка Маша), которые просят «сварить» для них разные компоты. Каждому медведю надо приготовить свой компот. В компоте должны быть яблоки и груши. Всего получается 4 фрукта. Каждый ребенок самостоятельно выполняет задание, составляя 4 вида компотов, с помощью перебора различных комбинаций геометрических фигур разного цвета.

Далее можно предложить упражнения на перебор цветов, несколько усложнив задание. Например, из учебника «Информатика в играх и задачах» А.В. Горячева (рис. 45).

Рис. 45 [12]

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

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

1) Решение задач с помощью таблицы.

К решению комбинаторных задач с использованием таблиц можно перейти после того, как освоен принцип их составления. Целесообразно использовать специальные трафареты таблиц, в которых сделаны «окошки» в верхней строке в первом столбике, а также прорези, намечающие места записи всех комбинаций (Таблица 6). Это позволяет экономить время на вычерчивание самой таблицы.

Например: «Для записи букв в одном царстве писарь предложил использовать знаки V, N, Z. Сколько слов он сможет записать с помощью этих знаков, если для записи каждого из них можно использовать только два знака?»

Работая с трафаретом, дети вписывают в «окошки» данные задачи, а через прорези намечают записи составляемых объектов. Убрав трафарет, они могут отчертить прямыми линиями условие задачи. Затем с помощью предложенных значков учащиеся вписывают в соответствующие клетки слова и подсчитывают их количество (Таблица 7).

Таблица 6 Таблица 7

При заполнении таблиц, особенно на начальном этапе, важно обращать внимание детей на то, следует ли записывать составленное соединение, не повторяет ли оно уже имеющееся и удовлетворяет ли условиям задачи.

2) Использование графов в процессе решения задач.

Например, «Встретились пятеро друзей. Здороваясь, они пожали друг другу руки. Сколько всего рукопожатий было сделано?»

Сначала выясняется, как можно обозначить каждого человека. Рассматривая разные предложения, дети приходят к выводу, что удобнее изображать людей точками. Учитель советует расположить точки по кругу. Дети придумывают, как показать, что два человека пожали друг другу руки.

От двух точек навстречу друг другу проводятся черточки – «руки», которые, встречаясь, образуют одну линию. Так происходит переход к символическому изображению рукопожатия. Сначала составляются все рукопожатия одного человека (точка соединяется со всеми остальными). Потом переходят к другому человеку. И так действуют до тех пор, пока все не «поздороваются» друг с другом (рис. 46). По получившемуся графу подсчитывают число рукопожатий (10).

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

Например: «Сколько различных башенок можно построить из трех кубиков красного, синего и желтого цветов?»

Рис. 47

Анализируя построенный граф (рис. 47), учитель может обратить внимание детей на закономерность: каждый кубик два раза оказывается на каждом «этаже» (кроме нижнего). Осознав эту закономерность, ученики могут сделать вывод, что по условию задачи можно построить всего 6 башенок.

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

Рассмотрим задачу: «Сколько двузначных чисел можно составить из цифр 5, 6, 7?»

Решение:

Чтобы показать, какое число записывается с помощью двух цифр (десятков и единиц) используется стрелка. Обозначим цифры 5, 6, 7 точками. Для того, чтобы показать образование числа 56, нужно провести дугу от точки 5 к точке 6 с указанием направления (рис. 48)

Рис. 48

Стрелка показывает, что запись числа начинается с цифры 5: 56, 57. Аналогично изображаем числа 65, 67, 76, 75.

Двузначные числа, в записи которых используется одна цифра, на графе изображаются «петлей».

Так изображаются все варианты записи двузначных чисел, и пересчет получившихся стрелок графов дает ответ на вопрос задачи (таких чисел всего 9) (рис.49).

Рис. 49

Рассмотрим примеры комбинаторных задач и целесообразные способы их решения.