Математическая логика

 

                            A1=

 

 

 

Подсчитываем Kпр=1+1+1+1+1+1=6. 

б) Для каждого нулевого элемента определяются коэффициенты   Кi,j по формуле 2.

(4)

К15=3;  К26=3; К34=2;  К43=2;  К51=3; К62=3; К15=3

Выбираем наибольший из коэффициентов (К1,5=3). Следовательно, в наш гамильтонов граф будет включено ребро, соединяющее 1 и 5 вершины с весом 13. Далее вычеркиваем строку и столбец, соответствующие индексу

                                      

                               A2=

 

 

         Повторяем  шаг под буквой а и получаем:

Kпр=6+3 =9.

                              A3=

                                  

                               

 

 

Далее повторяем шаг б:

К21=1; K26=2; K34=2; K43=1; K53=0; K54=0; K62=3.

Следующим ребром, которое будет включено в граф – это K62=3

Повторяем шаг а

 

A4=                  A5              =

 

Получаем Kпр=11

Повторяем шаг б:

K21=2; K34=0; K36=3; K43=3; K53=0; K54=0

Получаем, что будет включено ребро K36=3

                                         A6=

                                                 

 

Добавляем к  графу ребро K21=2

                                          A7=

 

 

В ходе решения задачи были выделены элементы матрицы:

К1,5  , К6,2,  К3,6   , К2,1 ,  К5,4  ,К4,3, которым соответствуют ребра (1-5), (6-2), (3-6), (2-1), (5-4), (4-3) с весами 3, 3, 3, 2.

Длина маршрута равна 11, что совпадает с суммой всех коэффициентов приведения: 6 + 3 + 2 = 11. Построим граф (рисунок 8) и, если все вершины соединились, следовательно, задача  было решена правильно.

 

 

 

 

 

Рисунок 8- Результирующий граф

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

В  курсовой работе было рассмотрено три части дискретной математики, а именно применение ее на практике. Рассмотрены такие темы как математическая логика, графы, нечеткие множества. В первой части было рассмотрено применение дискретной математики в информатике, а именно применение ее в программировании, в построении схем и в криптографии. Также были рассмотрены применение математической логики на практическом примере: составлена таблица истинности, нахождение двух производных, конъюнктивная и дизъюнктивная  нормальная функция, а также метод неопределенных коэффициентов для построения полинома Жегалкина. Во второй части рассматривается применение теории графов в экономических задачах, которые подразделяются на: алгоритм построения минимального остова, в результате чего были  определены минимальные затрат на проезд от дома до супермаркета; Жадный алгоритм, где была решена задача о максимальной загруженности линий, которые соединяют нефтеперерабатывающие заводы с новым месторождением нефти; Алгоритм Дейкстра – задача о нахождении оптимального пути, нахождения  минимальных затрат на обеспечение отдыха своим сотрудникам; Задача Коммивояжера – максимизация прибыли и уменьшения затрат времени.

 

 

 

 

 

 

 

 

 

 

 

Список использованных источников:

1. Воротников А.П., Практикум по введению в математическую логику.- СПб., 1986 – 300с.

2. Новиков  Ф.А.,  Дискретная математика для программистов. – СПб., 2002 – 302с.

3. Новиков  Ф.А.,  Введение в крипторафию. – СПб, 1993 – 190 с.         

4. Логинов Б.М.,  Лекции по дискретной математике. – Калуга, 1993 – 140с.

5. Яблонский С.В., Введение в дискретную математику .-M.:Наука, 1996 – 200с.