Автор конспекта:
Автор(ы): — Колотова Инна Владимировна

Место работы, должность: —

учитель информатики МОУ "Медико-биологический лицей" г.Саратова

Регион: — Саратовская область

Характеристика конспекта:
Уровни образования: — основное общее образование

Класс(ы): — 8 класс
Класс(ы): — 9 класс

Предмет(ы): — Информатика и ИКТ

Целевая аудитория: — Учащийся (студент)
Целевая аудитория: — Учитель (преподаватель)

Ресурс для профильной школы: — Ресурс для профильной школы

Тип ресурса: — методическая разработка

Краткое описание ресурса: —

Предпрофильный элективный курс Введение в комбинаторику для 8-го или 9-го кдасса.

Тема: «Введение в комбинаторику.

Комбинаторные задачи в программировании».

Содержание

Введение. 2

Перестановки. Правило умножения.2

Перестановки. Правило сложения. Понятие факториала.2

Сочетания. 2

Перестановки с повторениями. 2

Циклы с заранее известным числом повторений. 2

Заключение. 2

Приложение №1. Задачи .2

Приложение №2. Задачи .2

Приложение №3. Задачи. 2

Приложение №4. Задачи.2

Приложение 5. Поурочное планирование. 2

Список литературы.. 2

Введение

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

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

Данные уроки введения в комбинаторику проводились в гимназических классах в 1999 году, учащиеся которых к данному моменту уже окончили ВУЗы. Выпускникам, избравшим экономические специальности, он значительно облегчил изучение основ теории вероятностей и статистики. В 2003-2004 учебном году введение в комбинаторику преподавалось в 10 классе, что расширило кругозор и повысило математическую культуру выпускников. Пятеро из них поступили в СГУ на механико-математический факультет и один – на КНиТ.

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

Перестановки. Правило умножения.

Многие поколения людей интересовали задачи, в которых необходимо было найти количество способов расположения множества объектов. Сколькими способами можно поставить 10 человек в очередь к билетной кассе? Сколько существует различных автомобильных номеров? Сколько «счастливых» трамвайных билетов? Сколько способов выбора маршрута из пункта А в пункт Б ? и т.п.

Рассмотрим пример 1. Сколькими способами можно расставить на полке 3 книги ? (Обозначим их А, В, С ).

Решение 1. На первое место мы можем поставить любую из трех книг, следовательно это можно сделать тремя способами, поставив книгу А, или В, или С. Остаются две книги. На второе место можно поставить любую из двух оставшихся, т.е. имеем две возможности заполнить второе место на полке. На третье место ставим оставшуюся одну книгу:

книга на 1 книга на 2 книга на 3 Возможные размещения

месте месте месте

В С АВС

А

С В АСВ

А С ВАС

О В

С А ВСА

А В САВ

С

В А СВА

Получили граф (в математике графами называют геометрические фигуры, состоящие из точек-вершин, и линий, их соединяющих, — рёбер), называемый деревом. Точка О – вершина графа. Двигаясь от вершины к правым крайним точкам дерева, получаем все шесть возможных размещений.

Основным различием этих размещений служит порядок объектов; изменение порядка дает другое размещение.

Решение 2. Будем рассуждать так: требуется заполнить три места на полке. Изобразим их так:

На первое место мы можем поместить А, либо В, либо С. Следовательно, первое место на полке может быть заполнено тремя способами:

3

( На дереве этот факт иллюстрируется тремя ветвями, исходящими из т.О).

Для каждого из этих трех способов заполнения первого места есть 2 варианта заполнения второго места, т.к. можно поставить любую из оставшихся 2-х книг:

3

2

После заполнения первого и второго места остается одна книга, следовательно, для каждого из шести вариантов заполнения 1-го и 2-го места остается один вариант заполнения 3-го места:

3

2

1

Общее число размещений находится умножением: 3*2*1=6

Определение. Подобные размещения называются линейными, т.к. они подобны упорядочению точек на прямой. (В отличие, например, от расположения цветов в вазе).

Для описанного типа размещений введем специальное название.

Определение.Перестановкойнекоторого количества объектов называется подобное размещение объектов в определенном линейном порядке.

Т.О., «переставить» множество объектов – значит расположить их в каком-то выбранном порядке.

Рассмотрим пример 2. Пусть имеется три экземпляра книги А, три экземпляра книги В и три экземпляра книги С. Сколькими различными способами можно расставить на полке три книги ? (Экземпляры считаем неразличимыми между собой).

Решение. Вспомним второй способ решения предыдущей задачи. Теперь на первое место мы можем поставить любую из трех книг, на второе – тоже любую из трех книг, на третье – также любую из трех:

3

3

3

Как и раньше, общее количество перестановок найдем умножением: 3*3*3=27.

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

Правило умножения.

Пусть необходимо выполнить одно за другим какие-то k действий.

Если первое действие можно выполнить n1 способами, после чего второе действие можно выполнить n2способами, после чего третье действие можно выполнить n3способами, и так далее до k-го действия, которое можно выполнить nkспособами, то все k действий вместе могут быть выполнены

n1*n2*n3*…*nk

способами

Пример 3. Номер автомобиля состоит из пяти мест, на первом – буква, затем – три цифры, за ними еще две буквы. Сколько существует автомобильных номеров ?

Могут быть использованы любые из 33 букв русского алфавита, кроме «ь», «ъ» и «й».

Решение. На первое место можно поставить любую из 30 букв. На второе – любую из 10-ти цифр, на третье – также любую из 10 цифр. На 4-е место можно поставить любую из 30-ти букв, на 5-е – также любую из 30 букв. По правилу умножения имеем:

30*10*10*10*30*30=27*106

Такое количество номеров автомобилей может быть выдано ГАИ в Саратовской области!

Задача. (самостоятельно). Сколько пятибуквенных «слов» можно составить из букв русского алфавита ?(«словом» будем называть любую комбинацию из букв)(подсказка: учесть, что «слово» не может начинаться на «ь», «ъ» и «й»).

Решение. Т.к. количество букв условием задачи не ограничено, то по правилу умножения имеем: 30*33*33*33*33= 35577630

Вывод.Пусть имеются два действия, первое из которых может быть выполнено m способами, а второе – n способами. Правило умножения утверждает: если, после того, как первое действие выполнено любым из mспособов, второе можно выполнить nспособами, то оба действия вместе могут быть выполнены mnспособами. Т.о., это такая ситуация, когда мы можем выполнить сначала первое действие, а затем второе.

Задачи для самостоятельного решения в приложении №1

При решении этих задач следует использовать правило умножения.

Перестановки. Правило сложения. Понятие факториала.

Рассмотрим следующую задачу. Имеются три различных флага. На флагштоке поднимается сигнал, состоящий не менее чем из двух флагов. Сколько различных сигналов можно поднять на флагштоке, если порядок флагов в сигнале учитывается ?

Условимся первым действием считать подъем на флагштоке двух флагов, а вторым действием – трех флагов. По правилу умножения два флага можно поднять 3*2, или шестью, способами. Три флага – 3*2*1 , т.е. шестью способами.

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

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

6+6=12.

Правило сложения. Если два действия взаимно исключают одно другое, причем одно из них можно выполнить m способами, а другое – n способами, то какое-либо одно из них можно выполнить m+n способами.

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

Решение. Из условия задачи следует, что каждый сигнал может состоять либо из двух, либо из трех, либо из четырех флагов. Из двух флагов можно поднять 4*3=12 сигналов, а из трех 4*3*2=24 сигнала и из четырех 4*3*2*1=24 сигнала . Итого по правилу сложения 12+24+24=60 сигналов.

Правило умножения дает общий метод нахождения числа перестановок множества объектов. Например, 5 человек могут стать в очередь 5*4*3*2*1 способами.

Определение. Произведение всех натуральных чисел от 1 до n обозначается n! (читается «n факториал»).

Вычислить n! при больших n трудно, т.к. с увеличением n факториалы очень быстро растут. Так, 10! – число порядка 3.5 миллионов, а число перестановок букв русского алфавита, равное 33! Больше, чем 4*1033.

Т.о., из предыдущих рассуждений следует

Теорема 1. Число перестановок из n элементов по n равно n!. Оно обозначается .

Поэтому

=n!

Рассмотрим еще одну задачу. Сколькими способами из семи книг можно отобрать три и расставить их на три места на полке ?

Решение.По правилу умножения все три места можно заполнить 7*6*5 способами. Запишем это выражение, используя символ факториала:

7*6*5=

=

Число перестановок из семи объектов по три обозначается

и равно 7*6*5.

Поэтому

=

Определение. Размещением из nэлементов по mназывается произвольная перестановка mэлементов, которые принадлежат множеству, содержащему всего nэлементов.

Из предыдущих рассуждений следует:

Теорема 2. Число размещений из nэлементов по m равно (при условии, что n