1.Постановка задачи
Настоящаякурсовая работа моделирует логическую задачу, состоящую из следующих частей:
1) Изучениеконкретного раздела дискретной математики.
2) Решение 5-тизадач по изученной теме с методическим описанием.
3) Разработка и реализация в виде программыалгоритма по изученной теме. Разработка программного интерфейса.
2.Введение
2.1Теоретическая часть
дискретный математика программа интерфейс
Пусть данграф G=(X, Г), дугам которогоприписаны веса (стоимости), задаваемые матрицей C=[cij]. Задача о кратчайшемпути состоит в нахождении кратчайшего пути от заданной начальной вершины s/>X до заданной конечнойвершины t/>X, при условии, что такойпуть существует, т.е. при условии t/>R(s). Здесь R(s) – множество, достижимоеиз вершины s.Элементы cij матрицы весов C могут быть положительными, отрицательными или нулями.Единственное ограничение состоит в том, чтобы в G не было циклов сотрицательным суммарным весом. Если такой цикл Ф все же существует и xi – некоторая его вершина,то, двигаясь от s к xi, обходя затем Ф достаточно большое число раз и попадаянаконец в t,мы получим путь со сколь угодно малым (/>) весом. Таким образом, вэтом случае кратчайшего пути не существует.
Если, сдругой стороны, такие циклы существуют, но исключаются из рассмотрения, тонахождение кратчайшего пути (простой цепи) между s и t эквивалентно нахождениюв этом графе кратчайшего гамильтонова пути с концевыми вершинами s и t. Это можно усмотреть изследующего факта. Если из каждого элемента cij матрицы весов C вычесть достаточнобольшое число L,то получится новая матрица весов C'=[cij'], все элементы cij' которой отрицательны.Тогда кратчайший путь от s к t – с исключением отрицательных циклов – необходимо будетгамильтоновым, т.е. проходящим через все другие вершины. Так как вес любогогамильтонова пути с матрицей весов C' равен весу этого пути с матрицей весов C, но уменьшенному на постояннуювеличину (n-1)×L, то кратчайший путь(простая цепь) от s к t с матрицей C' будет кратчайшим гамильтоновым путем от s к t при первоначальнойматрице C.Задача о нахождении кратчайшего гамильтонова пути намного сложнее, чем задача ократчайшем пути. Поэтому мы будем предполагать, что все циклы в G имеют неотрицательныйсуммарный вес. Отсюда также вытекает, что неориентированные дуги (ребра) графа G не могут иметь отрицательныевеса.
Следующиезадачи являются непосредственными обобщениями сформулированной выше задачи ократчайшем пути.
1) Длязаданной начальной вершины s найти кратчайшие пути между t и всеми другимивершинами xi/>X.
2) Найтикратчайшие пути между всеми парами вершин.Частные случаи, когда все cijнеотрицательны, встречаются на практике довольно часто (например, когда cijявляются расстояниями), так что рассмотрение этих специальных алгоритмовоправдано. Мы будем предполагать, что матрица не удовлетворяет, вообще говоря,условию треугольника, т.е. не обязательно /> длявсех />. В противном случаекратчайший путь между xj и xj состоит из одной единственной (xj xj)дуги, если такая дуга существует, и задача становится тривиальной. Если в графеGдуга (xj xj) отсутствует, то ее вес полагается равным />.
На практикечасто требуется найти не только кратчайший путь, но также второй, третий и т.д.кратчайшие пути в графе. Располагая этими результатами, можно решить, какой путьвыбрать в качестве наилучшего. Кроме того, второй, третий и т.д. кратчайшиепути можно использовать при анализе «чувствительности» задачи о кратчайшемпути.
Существуюттакже задачи нахождения в графах путей с максимальной надежностью и смаксимальной пропускной способностью. Эти задачи связаны с задачей о кратчайшемпути, хотя в них характеристика пути (скажем, вес) является не суммой, анекоторой другой функцией характеристик (весов) дуг, образующих путь. Такиезадачи можно переформулировать как задачи о кратчайшем пути. Однако можнопоступить иначе: непосредственно приспособить для их решения те методы, которыеприменяются в задачах о кратчайшем пути.
Существуеттакже случай, когда учитываются и пропускные способности, и надежности дуг. Этоприводит к задаче о пути с наибольшей ожидаемой пропускной способностью. И хотятакая частная задача не может быть решена при помощи техники отысканиякратчайшего пути, но итерационный алгоритм, использующий эту технику в качествеосновного шага, является эффективным методом получения оптимального ответа.
Наиболееэффективный алгоритм решения задачи о кратчайшем (s – t) – пути первоначальнодал Дейкстра. В общем случае этот метод основан на приписывании вершинамвременных пометок, причем пометка вершины дает верхнюю границу длины пути от s к этой вершине. Этипометки (их величины) постепенно уменьшаются с помощью некоторой итерационнойпроцедуры, и на каждом шаге итерации точно одна из временных пометок становитсяпостоянной. Последнее указывает на то, что пометка уже не является верхнейграницей, а дает точную длину кратчайшего пути от s к рассматриваемойвершине. Опишем этот метод подробно.
АлгоритмДейкстры (/>)
Пусть l(xi) – пометка вершины xi.
Присвоениеначальных значений
Шаг 1. Положить /> и считать эту пометкупостоянной. Положить /> для всех xi/>s и считать эти пометкивременными. Положить p=s.
Обновлениепометок
Шаг 2. Для всех />, пометки которыхвременные, изменить пометки в соответствии со следующим выражением: />.
Превращениепометки в постоянную
Шаг 3. Среди всех вершин свременными пометками найти такую, для которой />.
Шаг 4. Считать пометку вершиныxi* постоянной и положить p= xi*.
Шаг 5. (1) (Если надо найтилишь путь от sк t.)
Если p=t, то l(p) является длинойкратчайшего пути. Останов.
Если p/>t, перейти к шагу 2.
(2) (Если требуется найтипути от sко всем остальным вершинам.)
Если всевершины отмечены как постоянные, то эти пометки дают длины кратчайших путей.Останов.
Еслинекоторые пометки являются временными, перейти к шагу 2.
Доказательствотого, что вышеприведенный алгоритм действительно дает кратчайшие пути,чрезвычайно простое, дадим набросок этого доказательства.
Допустим, чтона некотором этапе постоянные пометки дают длины кратчайших путей. Пусть S1 – множество вершин сэтими пометками, а S2 – множество вершин с временными пометками. В конце шага 2 каждойитерации временная пометка l(xi) дает кратчайший путь от s к xi, проходящий полностью повершинам множества S1. (Так как при каждой итерации во множество S1 включается только однавершина, то обновление пометки l(xi) требует только одного сравнения на шаге 2.)
Пустькратчайший путь от s к xi* не проходит целиком по S1 и содержит по крайнеймере одну вершину из S2, и пусть xj/>S2 – первая такая вершина вэтом пути. Так как по предположению cij неотрицательны, то частьпути от xj к xi* должна иметь неотрицательный вес /> и/>. Это, однако, противоречитутверждению, что l(xi*) – наименьшая временная пометка, и, следовательно,кратчайший путь к xi* проходит полностью по вершинам множества S1, и поэтому l(xi*) является его длиной.
Так каквначале множество S1 равно (s) при каждой итерации к S1 добавляется xi*, то предположение, что l(xi*) равно длинекратчайшего пути/> xi/>S1, выполняется при каждойитерации. Отсюда по индукции следует, что алгоритм дает оптимальный ответ.
Еслитребуется найти кратчайшие пути между s и всеми другими вершинами полного связного графас n вершинами, то в процессеработы алгоритма выполняются />операцийсложения и сравнения на шаге 2 и еще /> операцийсравнения на шаге 3. Кроме того, при осуществлении шагов 2 и 3 необходимоопределить, какие вершины временные, а для этого нужно еще /> операций сравнения. Этивеличины являются верхними границами для числа операций, необходимых приотыскании кратчайшего пути между заданными вершинами s и t. Они действительнодостигаются, если окажется, что вершина t будет последнейвершиной, получившей постоянную пометку.
Как толькодлины кратчайших путей от s будут найдены (они будут заключительными значениями пометоквершин), сами пути можно получить при помощи рекурсивной процедуры сиспользованием соотношения (*). Так как вершина xi' непосредственнопредшествует вершине xi в кратчайшем пути от s к xi, то для любой вершины xi соответствующую вершину xi' можно найти как одну изоставшихся вершин, для которой
/>'/>'/>. (*)
Есликратчайший путь от s до любой вершины xi является единственным, то дуги (xi', xi) этого кратчайшего путиобразуют ориентированное дерево с корнем s. Если существуетнесколько «кратчайших» путей от s к какой-либо другой вершине, то при некоторой фиксированнойвершине xi' соотношение (*) будет выполняться для более чем однойвершины xi. В этом случае выбор может быть либо произвольным (еслинужен какой-то один кратчайший путь между s и xi), либо таким, чторассматриваются все дуги (xi', xi), входящие в какой-либо из кратчайших путей ипри этом совокупность всех таких дуг образует не ориентированное дерево, аобщий граф, называемый базой относительно s или кратко – s-базой.
2.2 Задачи с методическим описанием
Найтикратчайшие пути от вершины 1 ко всем другим вершинам графа
Неориентированноеребро будем рассматривать как пару противоположно ориентированных дуг равноговеса. Воспользуемся алгоритмом Дейкстры. Постоянные пометки будем снабжатьзнаком +, остальные пометки рассматриваются как временные.
x1
x2
x3
x4
x5
x6
x7
x8
x9
x1 10 3 6 12
x2 10 18 2 13
x3 18 25 20 7
x4 25 5 16 4
x5 5 10
x6 20 10 14 15 9
x7 2 4 14 24
x8 6 23 15 5
x9 12 13 9 24 5
Алгоритмработает так:
Шаг 1. />.
Перваяитерация
Шаг 2. /> — все пометки временные.
/>; />; />; />
Шаг 3. /> соответствует x7.
Шаг 4. x7 получает постоянную пометкуl(x7)=3+, p=x7.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Втораяитерация
Шаг 2. /> — все пометки временные.
/>; />; />; />
Шаг 3. /> соответствует x2.
Шаг 4. x2 получает постояннуюпометку l(x2)=5+, p=x2.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Третьяитерация
Шаг 2. /> — только вершины x3 и x9 имеют временные пометки.
/>; />
Шаг 3. /> соответствует x8.
Шаг 4. x8 получает постояннуюпометку l(x8)=6+, p=x8.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Четвертаяитерация
Шаг 2. /> — только вершины x5, x6 и x9 имеют временные пометки.
/>; />; />
Шаг 3. /> соответствует x4.
Шаг 4. x4 получает постояннуюпометку l(x4)=7+, p=x4.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Пятаяитерация
Шаг 2. /> — только вершины x5, x6 и x3 имеют временные пометки.
/>; />; />
Шаг 3. /> соответствует x9.
Шаг 4. x9 получает постояннуюпометку l(x9)=11+, p=x9.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Шестаяитерация
Шаг 2. /> — только вершина x6 имеет временную пометку.
/>
Шаг 3. /> соответствует x5.
Шаг 4. x5 получает постояннуюпометку l(x5)=12+, p=x5.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Седьмаяитерация
Шаг 2. /> — только вершина x6 имеет временную пометку.
/>
Шаг 3. /> соответствует x6.
Шаг 4. x6 получает постояннуюпометку l(x5)=17+, p=x6.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Восьмаяитерация
Шаг 2. /> — только вершина x3 имеет временную пометку.
/>
Шаг 3. x3 получает постояннуюпометку l(x3)=23+.
Найтикратчайшие пути от вершины 1 ко всем другим вершинам графа
Неориентированноеребро будем рассматривать как пару противоположно ориентированных дуг равноговеса. Воспользуемся алгоритмом Дейкстры. Постоянные пометки будем снабжатьзнаком +, остальные пометки рассматриваются как временные.
x1
x2
x3
x4
x5
x6
x7
x8
x9
x1 3 2
x2 5 15 12
x3 8 24
x4 6 8 18 4 11
x5 12 7 20
x6 20 9 13
x7 10 4 9 16
x8 24 16 22
x9 11 13
Алгоритмработает так:
Шаг 1. />.
Перваяитерация
Шаг 2. /> — все пометки временные.
/>; />
Шаг 3. /> соответствует x5.
Шаг 4. x5 получает постояннуюпометку l(x5)=2+, p=x5.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Втораяитерация
Шаг 2. /> — все пометки временные.
/>; />; />
Шаг 3. /> соответствует x2.
Шаг 4. x2 получает постояннуюпометку l(x2)=3+, p=x2.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Третьяитерация
Шаг 2. /> — только вершины x3 и x4 имеют временные пометки.
/>; />
Шаг 3. /> соответствует x3.
Шаг 4. x3 получает постояннуюпометку l(x3)=8+, p=x3.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Четвертаяитерация
Шаг 2. /> — все пометки временные.
/>; />
Шаг 3. /> соответствует x4.
Шаг 4. x4 получает постояннуюпометку l(x4)=9+, p=x4.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Пятаяитерация
Шаг 2. /> — только вершины x7, x6 и x9 имеют временные пометки.
/>; />; />
Шаг 3. /> соответствует x7.
Шаг 4. x7 получает постояннуюпометку l(x7)=13+, p=x7.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Шестаяитерация
Шаг 2. /> — только вершины x6 и x8 имеют временные пометки.
/>; />
Шаг 3. /> соответствует x9.
Шаг 4. x9 получает постояннуюпометку l(x9)=20+, p=x9.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Седьмаяитерация
Шаг 2. /> — только вершина x6 имеет временную пометку.
/>
Шаг 3. /> соответствует x6.
Шаг 4. x6 получает постояннуюпометку l(x6)=17+, p=x6.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Восьмаяитерация
Шаг 2. /> временных пометок нет.
Шаг 3. x8 получает постояннуюпометку l(x8)=29+.
Найти кратчайшиепути от вершины 1 ко всем другим вершинам графа.
дискретный математика программа интерфейс
x1
x2
x3
x4
x5
x6
x7
x8
x9
x1
x2 9
x3 8 3
x4 7
x5 6
x6 17 4
x7 4
x8 7
x9 9 5
Алгоритмработает так:
Шаг 1. />.
Перваяитерация
Шаг 2. /> — все пометки временные.
/>; />
Шаг 3. /> соответствует x4.
Шаг 4. x4 получает постояннуюпометку l(x4)=7+, p=x4.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Втораяитерация
Шаг 2. /> — все пометки временные.
/>; />
Шаг 3. /> соответствует x2.
Шаг 4. x2 получает постояннуюпометку l(x2)=9+, p=x2.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Третьяитерация
Шаг 2. />; />
Шаг 3. /> соответствует x7.
Шаг 4. x7 получает постояннуюпометку l(x7)=11+, p=x7.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Четвертаяитерация
Шаг 2. />; />
Шаг 3. /> соответствует x8.
Шаг 4. x8 получает постояннуюпометку l(x8)=14+, p=x8.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Пятаяитерация
Шаг 2. />; />
Шаг 3. /> соответствует x3.
Шаг 4. x3 получает постояннуюпометку l(x3)=14+, p=x3.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Шестая итерация
Шаг 2. />; />
Шаг 3. /> соответствует x9.
Шаг 4. x9 получает постояннуюпометку l(x9)=19+, p=x9.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Седьмаяитерация
Шаг 2. />; />
Шаг 3. /> соответствует x5.
Шаг 4. x5 получает постояннуюпометку l(x5)=17+, p=x5.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Восьмаяитерация
Шаг 2. />; />
Шаг 3. x6 получает постояннуюпометку l(x6)=29+.
Найтикратчайшие пути от вершины 1 ко всем другим вершинам графа.
Алгоритмработает так:
Шаг 1. />.
Перваяитерация
Шаг 2. />
/>; />; />
Шаг 3. /> соответствует x2.
Шаг 4. x2 получает постояннуюпометку l(x2)=5+, p=x2.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Втораяитерация
Шаг 2. />
/>; />;
Шаг 3. /> соответствует x6.
Шаг 4. x6 получает постояннуюпометку l(x6)=8+, p=x6.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Третьяитерация
Шаг 2. />
/>; />; />
Шаг 3. /> соответствует x4.
Шаг 4. x4 получает постояннуюпометку l(x4)=10+, p=x4.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Четвертаяитерация
Шаг 2. />
/>; />
Шаг 3. /> соответствует x3.
Шаг 4. x3 получает постояннуюпометку l(x3)=13+, p=x3.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Пятаяитерация
Шаг 2. />
/>; />
Шаг 3. /> соответствует x8.
Шаг 4. x8 получает постояннуюпометку l(x8)=16+, p=x8.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Шестаяитерация
Шаг 2. />
/>; />
Шаг 3. /> соответствует x7.
Шаг 4. x7 получает постояннуюпометку l(x7)=17+, p=x7.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Седьмаяитерация
Шаг 2. />
/>; />; />
Шаг 3. /> соответствует x10.
Шаг 4. x10 получает постояннуюпометку l(x10)=18+, p=x10.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Восьмаяитерация
Шаг 2. />; />
Шаг 3. />соответствует x5.
Шаг 4. x5 получает постояннуюпометку l(x5)=19+, p=x5.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Девятаяитерация
Шаг 2. />; />
Шаг 3. x9 получает постояннуюпометку l(x9)=21+.
Найтикратчайшие пути от вершины 1 ко всем другим вершинам графа
Алгоритмработает так:
Шаг 1. />.
Перваяитерация
Шаг 2. />
/>; />; />
Шаг 3. /> соответствует x7.
Шаг 4. x7 получает постояннуюпометку l(x7)=6+, p=x7.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Втораяитерация
Шаг 2. />
/>; />
Шаг 3. /> соответствует x2.
Шаг 4. x2 получает постояннуюпометку l(x2)=7+, p=x2.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Третьяитерация
Шаг 2. />
/>; />
Шаг 3. /> соответствует x4.
Шаг 4. x4 получает постояннуюпометку l(x4)=8+, p=x4.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Четвертаяитерация
Шаг 2. />
/>; />; />;
Шаг 3. /> соответствует x5.
Шаг 4. x5 получает постояннуюпометку l(x5)=16+, p=x5.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Пятаяитерация
Шаг 2. />
/>; />; />
Шаг 3. /> соответствует x8.
Шаг 4. x8 получает постоянную пометкуl(x8)=16+, p=x8.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Шестаяитерация
Шаг 2. />; />
Шаг 3. /> соответствует x3.
Шаг 4. x3 получает постояннуюпометку l(x3)=18+, p=x3.
Шаг 5. Не все вершины имеютпостоянные пометки, поэтому переходим к шагу 2.
Седьмаяитерация
Шаг 2. />; />
Шаг 3. x6 получает постояннуюпометку l(x6)=20+.
3.Алгоритмизация задачи
1) Вводимколичество вершин неориентированного графа.
2) Есликоличество вершин больше 5, то переходим к пункту 3; иначе переходим к пункту4.
3) Генераторомслучайных чисел произвольно задаются связи между вершинами в матрицесмежностей, переходим к пункту 5.
4) Вводимсвязи между вершинами, исходя из следующего условия:
- если не существует пути длиной в одноребро из одной вершины в другую, то ставим «100»,
- еслисуществует путь между двумя вершинами, то ставим произвольное положительноененулевое значение веса дуги.
Все введенные данные заносятся в матрицу смежностей.
5) Вводимномера вершин, путь между которыми нужно найти.
6) Задаемначальные значения длин путей равных 100 (в программе это обозначает бесконечность),а пометки всех вершин обнуляем.
7) Дляначальной вершины в матрицу, хранящую пути (предшествующие вершины), заносимзначение нуль, поскольку нет вершин предшествующих началу, значению путиприсваиваем значение нуля, пометку на вершину устанавливаем в единицу.
8) Измененяемдлины путей между вершинами «i» и начальной при условии, что рассматриваемая дуга не идетиз вершины в саму себя и пометка этой вершины равна нулю, то тогда:
а)просматриваем длину пути в вершину «i» и сравниваем с длиной пути из начальной вершины«Nac»
б) получаем,что длина пути из вершины «s» меньше начального значения пути в вершину «i», то запоминаем в T[i] – ом элементеновую длину пути (меньшую) и H[i] – му присваиваем значение «s».
9) Присваиваемпеременной ‘t»значение 100 (бесконечность), а переменной для хранения текущей вершины «k» присваиваем значениенуль.
10) Производимпопытку уменьшить длину пути. Если вершина не помечена (ее пометка равна нулю),то если длина пути меньше значения «t» то значению «t» присваиваем текущеезначение пути, а переменной для хранения текущей вершины «k» даем значение этой переменной.
11) Еслипеременная для хранения текущей вершины имеет значение нуля, то пути нет,переходим к пункту 14, иначе переходим к пункту 12.
12) Еслипеременная для хранения текущей вершины имеет значение конечной вершины, топуть найден, он кратчайший, переходим к пункту 14, иначе переходим к пункту 13.
13) Пометкуна вершину, которую хранит переменная «k», изменяем на единицу ипереходим к пункту 8.
14) Выводимна экран сообщение о длине пути между вершинами, если такой путь существует (т.е.путь имеет неотрицательную длину).
4 Экранная формаинтерфейса и инструкция пользователя Press the first letter of item that you needs
Пункты меню:
1. Алгоритм реализации поставленной задачи.
2. Изображение исходного графа.
3. Выход из программы.
Для выбора пункта необходимо нажать на соответствующую клавишу:
- если это пункт 1, то нажмите «A» или «a»;
- если это пункт 2, то нажмите «D» или «d»;
- если это пункт 3, то нажмите «E» или «e».
Заключение
В соответствии с поставленной задачей в курсовой работе было выполнено следующее:
1) Изученконкретный раздел дискретной математики.
2) Решены 5задач по изученной теме с методическим описанием.
3) Разработан и реализован в виде программыалгоритм по изученной теме. Разработан программный интерфейс.
Литература
1. Новиков Ф.А. Дискретная математика дляпрограммистов – СПб.: Питер, 2002 год
1. Немнюгин С.А. TurboPascal: практикум – СПб.: Питер, 2002 год