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

Задача коммивояжера

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

Решение может быть осуществлено методом прямого перебора, что потребует рассмотрения р! вариантов с последующим выбором оптимального. Даже для небольших р это весьма затруднительно.

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

1. Акимов О.Е. Дискретная математика. – М., Лаборатория Базовых Знаний, 2003.

2. Белоусов А.И., Ткачев С.Б. Дискретная математика. – М.,изд. МГТУ им. Н.Э. Баумана, 20004

3. Березина Л.Ю. Графы и их применение. – М.: Просвещение, 1979.

4. Берж К. Теория графов и ее применения. – М.: ИЛ, 1962.

5. Булос ДЖ., Джеффри Р. Вычислимость и логика. М.; Мир, 1994.

6. Виленкин Н. Я. Комбинаторика. М.; Наука, 1969.

7. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. – М.: Наука, 1992.

8. Гиндикин С.Г. Алгебра логики в задачах. – М.: Наука, 1972.

9. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа, 1987.

10. Грэхем Р., Кнут Д, Поташник О. Конкретная математика. Основание информатики. М. – Мир, 1998.

11. Евстигнеев В.А. Применение теории графов в программировании. – М.: Наука, 1985.

12. Зыков А.А. Основы теории графов. – М.: Наука, 1987.

13. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.: Энергия, 1980.

14. Линский В. Комбинаторика для программистов. – М.: Мир, 1988.

15. Ломазова И. А. Дискретная математика. Математические основы обработки информации. Учеб. пособие.- ЯГУ. Ярославль, 2000.

16. Мелехов А.Н. Ориентированные графы и конечные автоматы. – М.: Наука, 1971.

17. Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Изд-во МАИ, 1992.

18. Никольская И.Л. Математическая логика. – М.: Высшая школа, 1981.

19. Новиков Ф. А. Дискретная математика. – С-Пб.: Питер, 2001.

20. Спирина М.С., Спирин П.А. Дискретная математика. – М., ACADEMA, 2004.

21. Трахтенброт Евстигнеев В.А. Применение теории графов в программировании. – М.: Наука, 1985.

22. Яблонский С.В. Введеие в дискретную математику. 3-е изд. – М., Высш. Шк., 2001.

ОГЛАВЛЕНИЕ

Предисловие………………………………………………………………..3

1. Основные понятия………………………………………………………4

2. Множества…………...……………………………………………….4

2.1. Подмножества. 5

2.2. Равенство множеств. 5

2.3. Мощность множеств. 6

2.4. Алгебра множеств. Операции над множествами. 6

2.5. Свойства операций. 7

2.6. Разбиение множества на классы.. 9

2.7. Декартово произведение множеств. 10

2.7.1. Декартова степень. 12

2.7.2. Декартово произведение n множеств. 12

2.7.3. Свойства декартового произведения. 12

2.8. Отношения. 13

2.8.1 Композиция отношений. 13

2.8.2. Отношения на множестве. 14

2.8.3. Виды отношений. 14

2.9. Функции. 15

2.9.1. Представление функций в ЭВМ... 16

3. Комбинаторика……………...……………………………………...17

3.1. Размещения. 17

3.1.1. Формула числа размещений без повторений. 17

3.1.2. Другой вид формулы числа размещений. 18

3.2. Перестановки. 19

3.3. Сочетания. 19

3.3.1. Свойства сочетаний. 20

3.4. Размещения с повторениями. 20

3.4.1. Число подмножеств данного множества. 21

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

3.6. Сочетания с повторениями. 22

4. Основы математической логики…………….………………………...24

4.1. Высказывания. 24

4.2. Основные операции над высказываниями. 24

4.3. Формулы.. 28

4.3.1. Соглашение о скобках. 28

4.3.2. Булевы функции. 28

4.3.3 Равносильные формулы.. 29

4.3.4. Основные равносильности. 29

4.4. Решение логических уравнений. 31

4.5. Виды формул. 32

4.5.1. Связь равносильности и эквиваленции. 32

4.6. Нормальные формы.. 33

4.6.1. Дизъюнктивная нормальная форма формулы.. 33

4.6.2. Конъюнктивная нормальная форма. 33

4.6.3. Методы доказательства тавтологии. 34

4.6.4. Совершенные нормальные формы.. 35

4.7. Решение логических задач. 38

4.8. Анализ рассуждений. 39

4.8.1. Правила вывода. 41

4.8.2. Вывод. 43

4.8.3. Теорема дедукции. 44

4.9. Предикаты.. 45

4.9.1 Область истинности. 46

4.9.2. Операции над предикатами. 46

4.9.3. Кванторы.. 47

4.9.4. Операции с кванторами. 48

4.9.5. Формулы.. 49

4.9.6. Равносильность. 49

4.9.7. Равносильности с кванторами. 50

4.9.8. Запись математических предложений с помощью предикатов 51

4.9.9. Общезначимые формулы.. 52

4.9.10. Некоторые общезначимые формулы с кванторами. 53

4.9.11. Рассуждения. 54

4.9.12. Вывод. 55

5. Кодирование информации……....……….…………………………….57

5.1. Задача кодирования. 57

5.2. Равномерное кодирование. 58

5.3. Алфавитное кодирование. 59

5.4. Кодирование с минимальной избыточностью.. 59

5.5. Префиксное кодирование. 60

5.6. Неравенство Макмиллана. 61

5.7. Понятие вероятности. 62

5.8. Цена кодирования. 62

5.9. Алгоритм Фано префиксного кодирования. 63

5.10. Оптимальное кодирование. 65

5.10.1. Теорема об оптимальном кодировании. 67

5.10.2. Алгоритм Хаффмена. 69

5.11. Помехоустойчивое кодирование. 71

61.1. Смежность. 73

6.1.2. Виды графов. 74

6.1.3. Изоморфизм.. 75

6.1.4. Инварианты.. 76

6.2. Подграфы.. 77

6.3. Маршруты. Цепи. Циклы.. 77

6.3.1. Расстояние. 78

6.3.2. Связность. 79

6.4. Задание графа. 79

6.5. Метод математической индукции. 84

6.6.1. Задача о наименьшем числе аварий. 85

6.7. Взвешенный граф.. 89

6.7.1. Задача о кратчайшем пути. 89

6.7.2. Алгоритм Форда. 90

6.8. Задача о максимальном потоке. 93

6.8.1. Теорема Форда – Фолкерсона. 94

6.9. Связность в графах. 107

6.10. Циклы.. 109

6.11. Деревья. 110

6.11.1. Задача о минимальном остовном дереве. 112

6.11.2. Жадный алгоритм Краскала построения. 112

6.11.3. Ориентированные деревья. 113

6.11.4. Упорядоченные деревья. 114

6.11.5..Бинарные деревья. 115

6.12. Эйлеровы циклы.. 115

6.13. Гамильтоновы графы.. 118

6.13.1. Существование гамильтоновых графов. 119

6.13.2. Задача коммивояжера. 119

Библиографический список……………….…………………………….120

Дата добавления: 2014-01-06