Реферат: Разработка системы задач (алгоритмы-программы) по дискретной математике

Вятский Государственный Гуманитарный Университет

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

Курсовая работа по информатике

Тема:Разработка системы упражнений и задач (алгоритмы-программы) по дискретнойматематике.

Выполнил: Студент4 курса

факультетаинформатики

ЛепешкинАнтон Геннадъевич

Проверила:Ашихмина Татьяна Викторовна

Киров 2004

Содержание.

TOC o «1-3» h z u Содержание.PAGEREF _Toc90286509 h 2

Введение.PAGEREF _Toc90286510 h 3

Глава 1Теоретический материал.PAGEREF _Toc90286511 h 4

Перебор с возвратом.PAGEREF _Toc90286513 h 4

Поиск данных.PAGEREF _Toc90286514 h 5

Логарифмический(бинарный)поиск. PAGEREF _Toc90286515 h 5

Методысортировки.PAGEREF _Toc90286516 h 6

Сортировкаслияниями.PAGEREF_Toc90286517 h 6

Быстраясортировка Хоара.PAGEREF _Toc90286518 h 6

Графы.PAGEREF _Toc90286519 h 6

Представлениеграфа в памяти компьютера. PAGEREF _Toc90286520 h 6

Достижимость. PAGEREF _Toc90286521 h 7

Кратчайшиепути.PAGEREF _Toc90286522 h 8

АлгоритмДейкстры… PAGEREF _Toc90286523 h 8

АлгоритмФлойда (кратчайшие пути между всеми парами вершин).PAGEREF _Toc90286524 h 9

Глава 2Система задач и упражнений.PAGEREF _Toc90286525 h 9

Классификация задач.PAGEREF _Toc90286526 h 9

Комнаты музея.PAGEREF _Toc90286527 h 12

Пират вподземелье.PAGEREF _Toc90286528 h 13

Диспетчер имилиция.PAGEREF _Toc90286529 h 14

Задача офутболистах.PAGEREF _Toc90286530 h 15

Задача осемьях.PAGEREF _Toc90286531 h 16

Метро.PAGEREF _Toc90286532 h 16

Роботы.PAGEREF _Toc90286533 h 17

Вожатый влагере. PAGEREF _Toc90286534 h 20

Егерь.PAGEREF _Toc90286535 h 21

Игра «Найдидруга».PAGEREF _Toc90286536 h 22

Приложение.PAGEREF _Toc90286537 h 22

1. PAGEREF _Toc90286538 h 22

2. PAGEREF _Toc90286539 h 25

3. PAGEREF _Toc90286540 h 27

4. PAGEREF _Toc90286541 h 30

5. PAGEREF _Toc90286542 h 32

6. PAGEREF _Toc90286543 h 32

7. PAGEREF _Toc90286544 h 34

8. PAGEREF _Toc90286545 h 39

9. PAGEREF _Toc90286546 h 41

10. PAGEREF _Toc90286547 h 43

Заключение.PAGEREF _Toc90286548 h 45

Литература… PAGEREF _Toc90286549 h 45

Введение.

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

Цель: Разработать собственную классификацию для задачпо дискретной математике. Для достижения этой цели были поставлены следующиезадачи:

1) Разработать собственную системузадач и упражнений по дискретной математике.

2) Определить способы решенияданных задач, используя теоретический материал курса дискретной математики.

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

4) Разработать систему критериевклассификации данной системы задач.

Глава 1 Теоретическийматериал.

Перебор с возвратом.

Общая схема

Даны N упорядоченных множеств U1 U2,..., Un (N — известно), и требуетсяпостроить вектор А=(а1 а2, ..., аn), где a1€

U1, a2€U2, ..., an€Un, удовлетворяющийзаданному множеству условий и ограничений.

Начало

Выборы для А1

Выборы для А2 при А1

Выборы для А3 при данных А1 и А2

<img src="/cache/referats/18941/image001.gif" align=«left» v:shapes="_x0000_s1026 _x0000_s1027 _x0000_s1028 _x0000_s1029 _x0000_s1030 _x0000_s1031 _x0000_s1032 _x0000_s1033 _x0000_s1034 _x0000_s1035 _x0000_s1036 _x0000_s1037 _x0000_s1038 _x0000_s1039 _x0000_s1040 _x0000_s1041 _x0000_s1042 _x0000_s1043 _x0000_s1044 _x0000_s1045 _x0000_s1046 _x0000_s1047 _x0000_s1048 _x0000_s1049 _x0000_s1050 _x0000_s1051 _x0000_s1052 _x0000_s1053 _x0000_s1054 _x0000_s1055 _x0000_s1056">В алгоритме переборавектор А строится покомпонентно слева
направо. Предположим, что уже найдены значения первых (к-1)
компонент, A=(a1, a2, ..., a(k-1)), ?, ..., ?), тогдазаданное множество
условий ограничивает выбор следующей компоненты аkнекоторым
множеством SkCUk. Если Sk<>[ ] (пустое), мы вправевыбрать в
качестве ак

наименьший элемент Sk и

перейти к выбору ^/^ "^выборы п«я»,

(к+1) компоненты и

так далее. Однако /[ ■ Д Jfcv при данном а,

если условия условия

а,, ^иаз

таковы, что Sk оказалось пустым, то мы возвращаемся к выбору

(к-1) компоненты, отбрасываем

а(k-1)и выбираем в качественового a(k-1) тот элемент S(k-i), который непосредственноследует за только что отброшенным. Может оказаться, что для нового a(k-1)условия задачи допускают непустое Sk, и тогда мы пытаемся снова выбратьэлемент ак. Если невозможно выбрать a(k-1), мы возвращаемся ещена шаг назад и выбираем новый элемент а(к-2) и так далее.

Графическое изображение — дерево поиска. Корень дерева (0 уровень) есть пустой вектор. Его сыновья сутьмножество кандидатов для выбора а1 и, в общем случае, узлы k-го уровня являютсякандидатами на выбор ак при условии, что а1, а2, ..., a(k-1)выбраны так, как указывают предки этих узлов. Вопрос о том, имеет ли задачарешение, равносилен вопросу, являются ли какие-нибудь узлы дерева решениями.Разыскивая все решения, мы хотим получить все такие узлы.

Рекурсивная схема реализации алгоритма,

procedureBacktrack(Beктop,i);

begin

if <вектор является решением> then <записать его>

else begin <вычислить Si>;

for a€

Si do Васкtrаск(вектор| | a,i+l);{| | — добавление к вектору компоненты}

end; end;

Оценка временной сложности алгоритма. Данная схема реализации перебораприводит к экспоненциальным алгоритмам. Действительно, Пусть все решения имеютдлину N, тогда исследовать требуется порядка | Si| *| S2| *...*| SN| узловдерева. Если значение S; ограничено некоторой константой С, то получаем порядкаCN узлов.

Поиск данных.Логарифмический(бинарный)поиск

Логарифмический (бинарный или метод деления пополам)поиск данных применим к сортированному множеству элементов а1< а2 <… < ап, размещениекоторого выполнено на смежной памяти. Для большейэффективности поиска элементов надо, чтобы пути доступа к ним сталиболее короткими, чем просто последовательный перебор. Наиболееочевидный метод: начать поиск со среднего элемента, т.е.выполнить сравнение с элементом а. Результат сравнения позволит определить, вкакой половине последовательности а{,а2,..., а, 1+„,,...,ап продолжить поиск,

применяяк ней ту же процедуру, и т.д. Основная идея бинарного поиска довольнопроста, однако «для многих хороших программистов не одна попытка написатьправильную программу закончилась неудачей». Чтобы досконально разобраться валгоритме, лучше всего представить данные ах< а2 <… < ап в виде двоичного дерева сравнений, которое отвечает бинарномупоиску.

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

{Вершины левого поддерева}<Вершина корня<{Вершины правогоподдерева }.

Рис

. Пример дерева сравнений, отвечающего бинарному поиску среди сортированных элементов: 3,5,7,9,12,19,27,44

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

Используется,когда имеется какая-либо информация о массиве, например массив упорядочен понеубыванию. Общее количество сравнений имеет порядок О(N*logN).

Методы сортировки.Сортировкаслияниями.

Используется,когда необходимо объединить упорядоченные фрагменты массивов: A[k],…,A[m] и B[m+1],…,B[q] в один C[k],…,C[q], тожеупорядоченный (k<=m<=q). Основная идеярешения состоит в сравнении очередных элементов каждого фрагмента, выяснении,какой из элементов меньше, переносе его во вспомогательный массив С (дляпростоты) и продвижении по тому фрагменту массива, из которого взят элемент.При этом следует не забыть записать в С оставшуюся часть того фрагмента,который не успел себя «исчерпать».

Метод слияний – один из первых в теорииалгоритмов сортировки. Он предложен Дж. Фон Нейманом в 1945 году. Эффективностьалгоритма, по Д. Кнуту, составляет С=О(N*logN).

Быстраясортировка Хоара.

Метод предложенЧ.Э.Р.Хоаром в 1962 году.

Идея метода. Висходном массиве А выбирается некоторый элемент Х (барьерный элемент). Основнойцелью алгоритма является запись Х «на свое место» в массиве, пусть это будетместо k, такое, что слева от Х были элементымассива, меньшие или равные Х, а справа – элементы массива, большие Х, т.е.массив А будет иметь вид: (А[1],A[2],…,A[k-1]),A[k] (X), (A[k+1],…, A[n]).

В результате элемент A[k] находится насвоем месте и исходный массив А разделен на две неупорядоченные части, барьероммежду которыми является элемент A[k]. Дальнейшиедействия очевидны – независимо сортировать полученные части по той же логике дотех пор, пока не останутся части массива, состоящие из одного элемента, то естьпока не будет отсортирован весь массив.

Графы.Представлениеграфа в памяти компьютера

Определим графкак конечное множество вершин V и набор Е неупорядоченных и упорядоченных парвершин и обозначим G=(V,E). Мощности множеств V и Е будем обозначать буквами Nи М Неупорядоченная пара вершин называется ребром, а упорядоченная пара — дугой.Граф, содержащий только ребра, называется неориентированным; граф, содержащийтолько дуги, — ориентированным, или орграфом. Вершины, соединенные ребром,называются смежными. Ребра, имеющие общую вершину, также называются смежными.Ребро и любая из его двух вершин называются инцидентными. Говорят, что ребро(u, v) соединяет вершины и и v. Каждый граф можно представить на плоскостимножеством точек, соответствующих вершинам, которые соединены линиями,соответствующими ребрам. В трехмерном пространстве любой граф можно представитьтаким образом, что линии (ребра) не будут пересекаться.

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

Матрицасмежности — это двумерный массивразмерности N*N. 1, вершина с номером i смежна с вершиной с номером j, 0, вершина с номером i не смежна с вершиной с номером j

Для храненияперечня ребер необходим двумерный массив R размерности М*2. Строка массиваописывает ребро.

Достижимость

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

Простой путь — это путь, в котором каждая дуга используется не более одного раза.

Элементарныйпуть — это путь, в котором каждая вершина используется не более одного раза.

Если существуетпуть из вершины графа v в вершину i, то говорят,что iдостижима из v.

Матрицудостижимости определим следующим образом:

<img src="/cache/referats/18941/image005.jpg" align=«left» hspace=«3» v:shapes="_x0000_s1057">1, если вершина iдостижима из vи

R[v,u]=0, при недостижимости

Множество R(v) — это множество таких вершин графа G, каждая из которых может быть достигнута извершины v. Обозначим через F(v) множество таких вершин графа G, которыедостижимы из v с использованием путей длины 1. T2(v) — это Г(Г(у)), то есть сиспользованием путей длины 2 и так далее. В этом случае:

R(v)={v}UГ(v)UГ2(v)U...UГp(v).

При этом р — некоторое конечное значение, возможно, достаточно большое.

Пример (длярисунка). R(1)={1}U{2,5}U{1,6}U{2,5,4}U{1,6,7}={1,2,4,5,6,7}

Выполняя этидействия для каждой вершины графа, мы получаем матрицу достижимостей R.

Кратчайшие пути.АлгоритмДейкстры

Дано. Ориентированныйграф G=<V,E>, s — вершина источник; матрица смежности A(A:array[1..n,1..n] ofinteger); для любых u, v€Vвес дуги неотрицательный (А[u,v]>=0). Результат. Массив кратчайших расстояний — D.

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

Пример

<img src="/cache/referats/18941/image007.jpg" align=«left» hspace=«3» v:shapes="_x0000_s1058"> Его матрица смежности:

∞ 3 7 ∞ ∞ ∞

1 ∞ 2 ∞ ∞ 1

А= ∞ 1 ∞ 4 4 ∞

∞ ∞ ∞ ∞ 1 5

∞ ∞ 1 ∞ ∞ 3

∞ ∞ ∞ 2 ∞ ∞

В таблицеприведена последовательность шагов (итераций) работы алгоритма. На первом шагеминимальное значение D достигается на второй вершине. Она исключается измножества Т, и улучшение оценки до оставшихся вершин (3,4,5,6) ищется не по всемвершинам, а только от второй.

№ итерации

D[1]

D[2]

D[31

D[4]

D[5]

D[6]

∞

[2,3,4,5,6]

∞

[3,4,5,6]

∞

[3,4,5]

[4,5]

[5]

Время работыалгоритма пропорционально N2.

АлгоритмФлойда (кратчайшие пути между всеми парами вершин).

Дано. Ориентированныйграф G=<V,E>, s — вершина источник; матрица смежности A(A:array[1..n,1..n] ofinteger); для любых u, v€Vвес дуги неотрицательный (А[u,v]>=0). Результат. Матрица Dкратчайших расстояний между всеми парами вершинграфа и кратчайшие пути.

Идея алгоритма.Обозначим через Dm[i,j] оценкукратчайшего пути из iв jс промежуточными вершинами из множества [1..m]. Тогдаимеем: D0[i,j]:=A[i,j] иD(m+1)[i,j]=min{Dm[i,j],Dm[i,m+1]+Dm[m+1,j]}.Второе равенство требует пояснения. Пусть мы находим кратчайший путь из iв jс промежуточными вершинами из множества [1..(m+1)]. Если этот путь не содержит вершину (m+1), то D(m+1)[i,j]=Dm[i,j]. Если же он содержит эту вершину, тоего можно разделить на две части от iдо (m+1) до j. Время работыалгоритма пропорционально N3.

Глава 2 Система задач и упражнений.

Классификациязадач.

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

Задачи с использованием алгоритма перебора с возвратом

Задачи с использованием

алгоритмов поиска данных

Задачи с использованием методов сортировки

Задачи с использова -нием алгоритмов на графах

Логарифмический поиск

Линейный поиск

Сортировка Хоара

Сортировка слияниями

Достижимость

Кратчайшие пути в графе

Алгоритм Дейкстры

Алгоритм Флойда

<img src="/cache/referats/18941/image008.gif" v:shapes="_x0000_s1205 _x0000_s1202 _x0000_s1184 _x0000_s1176 _x0000_s1177 _x0000_s1178 _x0000_s1179 _x0000_s1180 _x0000_s1181 _x0000_s1182 _x0000_s1183 _x0000_s1185 _x0000_s1186 _x0000_s1187 _x0000_s1188 _x0000_s1192 _x0000_s1193 _x0000_s1194 _x0000_s1195 _x0000_s1196 _x0000_s1197 _x0000_s1198 _x0000_s1199 _x0000_s1200 _x0000_s1201 _x0000_s1204">По тематике.

Задачи высокого уровня сложности

Задачи среднего уровня сложности

Задачи низкого уровня сложности

<img src="/cache/referats/18941/image010.gif" v:shapes="_x0000_s1214 _x0000_s1208 _x0000_s1209 _x0000_s1210 _x0000_s1211 _x0000_s1212 _x0000_s1213">По уровню сложности задачи.

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

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

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

По формулировке задачи.

еще рефераты

Еще работы по программированию, базе данных

Реферат по программированию, базе данных

Системы принятия решений, оптимизация в Excel и базы данных Access

29 Августа 2013

Реферат по программированию, базе данных

Обработка текстовых файлов на языке Турбо Паскаль

29 Августа 2013

Реферат по программированию, базе данных

Разработка программы рисования линий с помощью мыши

29 Августа 2013

Реферат по программированию, базе данных

Технологии программирования

29 Августа 2013