Элементы дискретной математики, учебное пособие, часть 2, Дурнев В.Г., Башкин М.А., Якимова О.Г., 2007

Элементы дискретной математики, Учебное пособие, Часть 2, Дурнев В.Г., Башкин М.А., Якимова О.Г., 2007.

В учебном пособии рассматриваются основные математические понятия, традиционно включаемые в программу дисциплины “Дискретная математика”: булевы и к-значимые функции, комбинаторика, графы, алфавитное кодирование, регулярные выражения и регулярные языки, конечные автоматы и автоматные языки. Пособие предназначено для студентов, обучающихся по направлению подготовки 510100 Математика и по специальностям 010100 Математика и 090102 Компьютерная безопасность. Оно может быть использовано при изучении дисциплины “Дискретная математика”, а также базирующихся на ней специальных дисциплин.




Начальные понятия.
Отцом теории графов является Л.Эйлер, решивший в 1730 г. широко известную в то время задачу, называвшуюся проблемой кёнигсбергских мостов. В городе Кёнигсберге (нынешний Калининград) было два острова, соединенных семью мостами с берегами реки Преголя и друг с другом так, как показано на рисунке 1.1. Задача состояла в следующем: найти маршрут прохождения всех четырех частей суши, который начинался бы с любой из них, кончался бы на этой же части и ровно один раз проходил по каждому мосту. Если такой маршрут существует, то его можно найти путем полного перебора. Исключительный вклад Л. Эйлера в решение этой задачи заключается в доказательстве, что такой маршрут построить невозможно.

Оглавление.
1.Графы.
1.Начальные понятия.    
2.Виды графов и операции над графами.    
3.Связность.     
3.1.Пути и связность.     
3.2.Вершинная связность и реберная связность.    
3.3.Двусвязные графы.    
4.Деревья.     
4.1.Определение и простейшие свойства дерева.    
4.2.Остов минимального веса.    
4.3.Помеченные деревья.    
5.Планарность.    
5.1.Плоские и планарные графы.    
5.2.Алгоритм укладки графа на плоскости.    
6.Обходы.    
6.1.Эйлеровы графы.    
6.2.Гамильтоновы графы.    
6.3. Задача коммивояжера н понятие NP-полноты.    
7.Независимые множества, клики, доминирующие множества.
7.1.Независимые множества.    
7.2.Шенноновская емкость графов.    
7.3.Задача Рамсея.    
7.4.Доминирование и покрытия.    
7.5.Паросочетания.    
7.6.Паросочетания в двудольном графе.    
8.Раскраски.    
8.1.Правильная раскраска.    
8.2.Раскраска ребер.    
8.3.Раскраска планарных графов.    
9.Алгоритмы на графах.    
9.1.Способы задания графов.    
9.2.Поиск в графе.    
9.3.Нахождение кратчайших путей в орграфе.    
9.4.Потоки в сетях.
2.Алфавитное кодирование.
1.Алфавитное кодирование.    
2.Однозначность раскодирования.    
3.Избыточность кодов.    
4.Помехоустойчивое кодирование.    
3.Конечные автоматы.
1.Алфавиты. Слова. Языки.    
2.Конечные представления языков.     
3.Конечные автоматы.    
4.Конечные автоматы и регулярные выражения.
5.Некоторые алгоритмические проблемы для языков.    
6.Минимизация автоматов.    
7.Конечные автоматы с выходом.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Элементы дискретной математики, учебное пособие, часть 2, Дурнев В.Г., Башкин М.А., Якимова О.Г., 2007 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.






Теги: Дурнев. :: Башкин :: Якимова :: учебник по математике :: математика :: дискретная математика