Комбинаторные алгоритмы решения школьных задач по информатике

ФГБОУ ВПО «Дагестанский государственный педагогический университет»

Инженерно-педагогический институт

Кафедра информатики

 

 

 

 

 

 

 

 

 

Ханапиева Хабсат Магомедовна

 

 

 

 

 

 

Выпускная квалификационная работа

 

 

Комбинаторные АЛГОРИТМЫ РЕШЕНИЯ ШКОЛЬНЫХ ЗАДАЧ

ПО ИНФОРМАТИКЕ

 

 

 

 

 

Научный руководитель -

канд. физ. мат. наук.,

доцент Шихиев Ш.Б.

 

 

 

 

 

 

 

 

 

Махачкала 2012

 

РЕФЕРАТ

Выпускная работа содержит 73 страницы машинописного текста, 15 рисунков, 3 таблиц, список из 25 использованных источников

Ключевые слова: КОМБИНАТОРИКА, ПЕРЕСТАНОВКА, РАЗМЕЩЕНИЕ, АЛГОРИТМ, СОЧЕТАНИЕ, ПЕРЕБОР ЭЛЕМЕНТОВ, МНОЖЕСТВО, ПОМНОЖЕСТВО, ДИСКРЕТНЫЙ АНАЛИЗ, РЕКУРСИЯ, БОЛЬШИЕ ЧИСЛА, ЭЛЕМЕНТ, ГЕНЕРАЦИЯ, НУМЕРАЦИЯ, СКОБОЧНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ, ЛЕКСИКОГРАФИЧЕСКИЙ ПОРЯДОК, ПОЛНЫЙ ПЕРЕБОР.

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

 

 

ОГЛАВЛЕНИЕ

 

Введение

 

 

ВВЕДЕНИЕ

 

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

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

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

В последнее время  издаются учебники для школьников по программированию, в которых делает акцент на изучение классических теорий, задач и алгоритмов. В этих книгах, как правило, излагаются олимпиадные задачи для школьников и при изучении этой литературы у школьника могут возникнуть трудности. (В течение последних трех лет по данной теме издавались книги Окулова С. М., Кирюхина В. М., Долинского М. С. и др.) Имеются книги попроще, например, Turbo Pascal и Delphi Никита Культина, которые имеются в продаже в достаточном количестве.

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

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

В. Дискретная математика традиционно была слабым звеном в  Советской школе математиков, 90% содержания дискретного анализа была разработана, начиная с 60-х годов XX века, в основном, благодаря исследованиям американских ученых. Еще в 1985 году при формировании центра по ликвидации компьютерной безграмотности вопрос о привлечении к этой работе авторитетных ученых был предметом дискуссии. Качество работы различных институтов и центров по информатике при министерстве образования оставляет желать лучшего.

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

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

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

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

- в отсутствии целенаправленной  переподготовки учителей информатики.

- в отношении руководителей  школ к информатике, считающих  ее вспомогательной и «внеклассной»  работой. 

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

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

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

Объект исследования  - элементы комбинаторики и задачи, сводимые к  перебору сочетаний и перестановок.

Предмет исследования – методика разработки алгоритмов построения элементов комбинаторики.

Гипотеза исследования. Качество подготовки выпускников к сдаче ЕГЭ повысится, если:

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

- осуществить отбор  алгоритмов решения задач дискретного анализа с обоснованием их корректности.

Задачи исследования:

1) изучить литературу  по теме выпускной работы;

2) провести сравнительный  анализ элементов комбинаторики и правил их построения, описания алгоритмов перебора сочетаний, перестановок и размещений;

3) описать методику  решения численных задач дискретного анализа;

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

Методологической  основой послужили положения:

- теории отбора содержания  учебного предмета на примере  комбинаторики;

- теории разработки и анализа алгоритмов;

- методики обучения  информатике.

Методы исследования: изучение и анализ литературы по информатике, по дискретному анализу, педагогике, методике решения задач по информатике и дискретному анализу; наблюдения; беседа; анкетирование.

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

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

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

В дипломной работе рассматриваются следующие вопросы.

 Арифметика больших чисел. Если задача оперирует числами, которые не вмешаются в ячейку компьютера (число переполняет ячейку оперативной памяти), то оно разбивается на части и записывается по частям в нескольких ячейках оперативной памяти. В связи с этим появляются вопросы, которые необходимо решать. Например, правило разбиения и восстановления числа и правила выполнения арифметических операций над большими числами.

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

Для сочетания, перестановки и размещения формулируется и  решается четыре классические задачи. Для перестановок они таковы.

1. Найти алгоритм перечисления всевозможных перестановок из n элементов.
2. Найти отношение порядка на множестве перестановок из n элементов.
3. По порядковому номеру перестановки определить перестановку.
4. По перестановке определить ее порядковый номер.

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

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

 

1. Комбинаторные задачи  в школьном курсе математики

1.1. Сочетание по m элементов из n

 

    Сочетанием из n элементов по m (иногда читают просто: из n по m) называется m-элементное подмножество некоторого n-элементного множества.       

 Таким образом, чтобы назвать какой – либо объект сочетанием из n по m, необходимо проверить одновременное выполнение следующих условий (существенных признаков понятия «сочетание»):                 

1. Заданы два множества.

2. Одно из множеств является  подмножеством другого.

3. Основное множество содержит n элементов.

4. Подмножество содержит m элементов.    

 Число сочетаний из n элементов по m обозначается через  и вычисляется по формуле:

 

Пример: Сколькими способами  можно составить букет из 3 цветов, если в вашем распоряжении 5 цветов: мак, роза, тюльпан, лилия, гвоздика?

Решение:

Основное множество: {мак, роза, тюльпан, лилия, гвоздика}   n=5

Соединение – букет  из трех цветков  m=3

Проверим, важен ли порядок:

{тюльпан, лилия, гвоздика} и {лилия, тюльпан, гвоздика} –  один и тот же букет  порядок  неважен это подмножество  это  сочетание «из пяти по три».

 (букетов)

 
Ответ: 10 букетов 

Генерирование сочетаний.    

 Опишем алгоритм генерирования  всех k-элементных подмножеств n-элементного множества X.  Можно принять X = {1,..., n}. Тогда каждому k-элементному подмножеству взаимно-однозначно соответствует возрастающая последовательность длины к с элементами из X: например, подмножеству {3,5,1} соответствует последовательность (1,3,5). Можно легко указать алгоритм, с помощью которого генерируются все такие последовательности. Для этого достаточно заметить, что при таком порядке, последовательностью, непосредственно следующей за последовательностью (a1,..., аk), является     (b1,...,bk) = (a1,...,ap-i,ap +1,ap + 2,...,ap + k-p+1),  где p=max{i:ai<n-k+1}.

Более того, последовательностью, непосредственно  следующей за (b1,…,bk), является

(c1,...,ck) = (b1,...,bp’-1,bp’ +1, bp’+2,..., bp’> +k-p’ + 1), где

 

(будем предполагать, что последовательности (a1,... ,ak) и (b1,...,bk) отличаются от (n-k+1,...,n) — последней последовательности в нашем порядке.            

 Это приводит к следующему  простому алгоритму.

Алгоритм. (Генерирование всех k-элементных подмножеств множества {1,... ,n}.)

Данные: n, к.

Результат: последовательность всех k-элементных подмножеств множества {1,...,n}.

1.begin

2. for i:=1 to k do A[i]:=i; (*первое подмножество*)

3. p:=k;

4. while p≥1 do

5. begin write (A[1],…,A[k]);

6. if A[k]=n then p:=p-1 else p:=k;

7. if p≥1 then

8.  for i:=k downto p do A[i]:=A[p]+i-p+1;

9. end;

10.end.

Рассмотрим примеры:

Пример 1. Сколькими способами можно составить команду из 4 человек для соревнования по бегу, если имеются 7 бегунов?