Число внешней устойчивости графа определяется мощностью минимального внешне устойчивого подмножества, содержащего наименьшее число вершин.

Число скрещиваний (пересечений) графа – наименьшее число пересечений ребер, которое получается при расположении графа на плоскости.

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

Библиографический комментарий

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

Ф. Бэкон

Модуль 1.

Задачам теории множеств посвящена обширная библиография, привести которую авторы не считают необходимым. Авторы при написании данного учебного пособия использовали концепции построения и описания множеств, приведенные в книге Шихановича [1]. Энциклопедической монографией по части 1 является классический труд группы известных французских математиков под псевдонимом Бурбаки [2]. Она может быть использована для углубления знаний, полученных при изучении данного пособия.

Различным аспектам теории множеств посвящены книги [3 – 10]. Всевозможные операции над множествами и большое количество примеров приведено в книгах [1, 3, 8 - 10]. Более подробный материал по упорядоченным множествам и кортежам можно найти в книгах [1, 2, 8 - 13]. Сведения об отношениях в том или ином объеме включены в множество книг по теоретико-множественной тематике. Различные способы представления отношений описаны в книгах [1, 2, 8 - 11].

Наиболее полно вопросы представления соответствий и примеры представления и преобразования соответствий даны в монографии Шихановича [1]. Материал по бесконечным множествам наиболее удачно для студентов описан в книгах [1, 2, 12, 13, 23]. Понятие мультимножества является относительно новым и более полно описано в монографии Петровского [14].

Основателем теории нечетких множеств является Заде [15]. Для подробного изучения теории нечетких множеств рекомендуем следующую литературу [11, 16 - 20]. Различные разделы дискретной математики описаны на доступном языке в учебнике [21,22].

Вопросы посвященные приближенным множествам подробно описаны в книге [24].

Модуль 2.

Задачам теории алгоритмов посвящена обширная библиография. Авторы при написании данного учебного пособия использовали концепции классического учебника Кормен Т., Лейзерсон Ч., Ривест Р. «Алгоритмы: построение и анализ». Он является энциклопедической монографией по дискретной математике. Кроме того, этот учебник может быть использован для углубления знаний, полученных при изучении данного пособия [25], Авторы советуют также книги О.П. Кузнецова «Дискретная математика для инженеров» [7, 26], Сигорского В.П. «Математический аппарат инженера», а также методические разработки по теории алгоритмов авторов данного пособия [27,42-44].

Различным аспектам теории алгоритмов посвящены книги [28 – 31,35,45]. Всевозможные описания типов универсальных алгоритмических моделей приведены в учебном пособии Гладков Л.А., Курейчик В.В., Курейчик В.М. Основы теории алгоритмов [27]. Более подробный материал по нечетким моделям и алгоритмам можно найти в книгах [17-20,32].

Наиболее полно примеры и задачи с решениями приведены в книге Шапорева [33] и учебном пособии авторов [27].

В книге [34] изложены методы и средства теории алгоритмов. Освещены основные математические свойства теории алгоритмов, необходимые для реальной практической деятельности.

В учебнике Дж. Макконелла [35] обсуждаются алгоритмы решения распространенных задач программирования: сортировки, сравнения с образцом, на графах, поиска и выборки и др.

Фундаментальный учебник Д.А. Андерсона [8] по дискретной математике подробно рассматривает вопросы логики, исчисления предикатов, алгоритмов и рекурсии. Особое внимание уделено теории доказательств. Книга содержит большое количество примеров и упражнений.

Сведения о комбинаторике в том или ином объеме включены в множество книг по дискретной математике.

Модуль 4.

В книге [34] приведены методы и средства дискретной математики как инструментарий при обработке информации на ЭВМ. Книга удобна для студентов, так как содержит обширный материал по решению задач, особенно в разделе по теории графов.

В книге [35] широко обсуждаются практические алгоритмы на графах. Книга будет особенно интересна студентам, так как содержит описание реальных программ для решения графовых задач.

Книга [8] – это современный классический учебник по дискретной математике. Особое внимание уделено теории доказательств. Материал сопровождается многочисленными примерами и упражнениями, особенно по теории графов.

Книгу [30] можно рассматривать как справочник по графовым и сортировочным алгоритмам. Для студентов интерес может представлять наличие программ.

Пособие [47] можно рекомендовать для студентов с углубленной математичской подготовкой. В нем в сжатой форме приведены основные разделы теории графов с задачами.

В книге [48] представлено систематизированное введение в теорию графов с доказательствами теорем и примерами.

Учебник [3] является единым методически взаимосвязанным курсом. Особый интерес для студентов может представлять раздел по графам и мографам, ориентированный на практическое применение в области информационных технологий.

Книга [49] представляет интерес для студентов тем, что авторы показали связь общей теории сетей с прикладными задачами на графах различного вида.

В учебном пособии [50] с методической точки зрения излагается теория графов. Особый интерес для студентов представляет сведение прикладных практических задач к задачам теории графов.

Учебное пособие [51] ориентировано на студентов технических вузов с хорошей математической подготовкой.

Книга [24] ориентирована на инженеров в области информационных технологий. Особое внимание уделено оптимизационным задачам на графах, имеющим практическое применение.

В монографии [52] изложены фундаментальные основы ИКТ с применением теории графов. Интерес для студентов может представлять наличие программных кодов для решения основных графовых задач.

В книге [53] с математической точки зрения рассматривается решение важнейшей теоретической и практической задачи: «сколько существует графов». Интерес для студентов представляет обзор решенных и нерешенных задач, перечисления графов.

Книга [54] дает полное представление о направлениях исследований в теории графов, приводятся упражнения и нерешенные задачи.

В книге [55] приводится множество интересных приложений теории графов в различных областях науки и техники.

В учебном пособии [56] особое внимание уделено алгоритмическим методам теории графов.

Основное внимание в учебнике [57] уделено алгебраическим методам анализа графов, ориентированным на практические инженерные задачи.

Книгу [58] можно использовать как справочное руководство по современной теории графов.

В книге [59] описаны основы теории графов и ее применение к сетям в ЭВМ.

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

ЛИТЕРАТУРА

Книга – немой учитель

Платон

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

У. Оден

1. Шиханович Ю.А. Введение в дискретную математику. М.: Наука, 1965.

2. Бурбаки Н. Теория множеств. Под ред. В.А. Успенского. – М.: Мир, 1965.

3. Горбатов В.А. и др. Дискретная математика. Учебник для студентов ВТУЗов. – М.: ООО «Издательство АСТ», 2003.

4. Прикладная комбинаторная математика. Сб. статей под ред. Э. Беккенбаха. – М.: Мир, 1968.

5. Хаггарти Р. Дискретная математика для программистов. Учебное пособие. – М.: Техносфера, 2003.

6. Яблонский С.В. Введение в дискретную математику. Учебное пособие. – М.: Наука, 1979.

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

8. Андерсон Д. Дискретная математика и комбинаторика. – М.: Издательский дом «Вильямс», 2003.

9. Новиков Ф.А. Дискретная математика для программистов. М.: Из-дательский дом «Питер», 2000.

10. Стол Р. Множества. Логика. Аксиоматические теории. – М.: Просвещение, 1968.

11. Мелихов А.Н., Берштейн Л.С. Конечные четкие и расплывчатые множества. Ч. 1, 2. – Таганрог, ТРТУ, 1981.

12. Александров П.С. Введение в теорию множеств и общую топологию. – М.: Наука, 1977.

13. Куратовский К., Мостовский А. Теория множеств. – М.: Мир, 1970.

14. Петровский А.Б. Пространства множеств и мультимножеств. – М.: УРСС, 2003.

15. Заде Л. Понятие лингвистической переменной и его применение к принятию приближенных решений. – М.: Мир, 1976.

16. Борисов А.Н. и др. Обработка нечеткой информации в системах принятия решений. – М.: Радио и связь, 1989.

17. Ярушкина Н.Г. Основы теории нечетких и гибридных систем. Учебное пособие. – М.: Финансы и статистика, 2004.

18. Нечеткие множества и теория возможностей. Под ред. В.Б. Кузьмина. – М.: Радио и связь, 1986.

19. Рыжов А.П. Элементы теории нечетких множеств и измерения нечеткости. – М.: Диалог-МГУ, 1998.

20. Кофман А. Введение в теорию нечетких множеств. – М.:Радио и связь, 1982.

21. Спирина М.С., Спирин М.А. Дискретная математика. – М.: Издательский центр «Академия», 2004.

22. Микони С.В. Теория и практика рационального выбора. – М.: Изд-во «Маршрут», 2004.

23. Хаусдорф Ф. Теория множеств. – М.: КомКнига, 2006.

24. Вагин В.Н., Головина Е.Ю., Загорянская А.А., Фомина М.В. Достоверный и правдоподобный вывод в интеллектуальных системах. – М.: Физматлит, 2004.

25. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.- М.: Издательский дом «Вильямс», 2000.

26. Кузнецов О.П. Дискретная математика для инженера. – СПб: Лань, 2004.

27. Гладков Л.А., Курейчик В.В., Курейчик В.М. Основы теории алгоритмов. Учебное пособие. – Таганрог: изд-во ТРТУ, 2003.

28. Ерусалимский Я.М. Дискретная математика: Теория, задачи, приложения. – М.: Вузовская книга, 2002.

29. Судоплатов С.В., Овчинникова Е.В. Дискретная математика: Учебник. – М.: ИНФРА-М, 2005.

30. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. Учебное пособие. – М.: Лаборатория базовых знаний, 2001.

31. Плотников А.Д. Дискретная математика: Учебное пособие. – М.: Новое знание, 2005.

32. Берштейн Л.С., Боженюк А.В. Нечеткие модели принятия решений: дедукция, индукция, аналогия: Монография. – Таганрог: Изд-во ТРТУ, 2001.

33. Шапорев С.Д. Дискретная математика: Курс лекций и практических занятий. – СПб.: БХВ-Петербург, 2006.

34. Капитонова Ю.В. и др. Лекции по дискретной математике. – СПб.: БХВ – Петербург, 2004.

35. Макконелл Дж. Анализ алгоритмов: Краткий курс. – М.: Техносфера, 2002.

36. Непейвода Н.Н. Прикладная логика. – Новосибирск: Изд-во Новосибирского университета, 2000.

37. Клини С.К. Математическая логика. – М.: Мир, 1973.

38. Ершов Ю.Л., Палютин Е.А. Математическая логика. – М.: Наука, 1979.

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

40. Судоплатов С.В., Овчинникова Е.В. Дискретная математика: Учебник. – М.: ИНФРА-М, 2005.

41. Акимов О.Е. Дискретная математика: логика, группы, графы, фракталы. – М.: Издатель АКИМОВА, 2005.

42. Сигорский В.П. Математический аппарат инженера – Киев: Техника, 1997.

43. Курейчик В.М. Учебное пособие по дискретной математике. Часть 1. – Таганрог: Изд-во ТРТУ, 1997.

44. Курейчик В.М., Гладков Л.А., Лисяк Н.К., Курейчик В.В. Учебное пособие для практических и лекционных занятий по курсу «Математические основы дискретной техники». Часть 1. – Таганрог: Изд-во ТРТУ, 1997.

45. Панадимитриу Х., Стайниц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир,1983.

46. Довгий П.С., Поляков В.И. Синтез комбинационных схем. – СПб.: Изд-во ИТМО, 2006.

47. Редькин Н.П. Дискретная математика: Курс лекций для студентов-механиков. – СПб.: Издательство «Лань», 2003.

48. Зыков А.А. Основы теории графов. – М.: Вузовская книга, 2004.

49. Френк Г., Фриш И. Сети, связи и потоки. – М.: Связь, 1978.

50. Емеличев В.А. и др. Лекции по теории графов: Учеб. пос. – М.: Книжный дом «ЛИБРОКОМ», 2009.

51. Белов В.В. и др. Теория графов: Учеб. пос. для ВТУЗов. – М.: Высшая школа, 1976.

52. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. – СПб.: БХВ – Петербург, 2003.

53. Харари Ф., Палмер Э. Перечисление графов. – М.: Мир, 1977.

54. Оре О. Теория графов. – М.: Книжный дом «ЛИБРОКОМ»/URSS, 2009.

55. Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1973.

56. Асеев Г.Г., Абрамов О.М., Ситников Д.Э. Дискретная математика: Учеб. пос. – Ростов-на-Дону: Феникс, 2003.

57. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учеб. пос. для вузов. – М.: изд-во МГТУ им. Баумана, 2004.

58. Татт У. Теория графов. – М.: Мир, 1988.

59. Евами М., Тхуласкрами К. Графы, сети и алгоритмы. – М.: Мир, 1984.

60. Абондо-Бодино Д. Применение в экономике теории графов. – М: Прогресс, 1966.

61. Берштейн Л.С., Боженюк А.В. Введение в теорию нечетких графов. – Таганрог: Изд-во ТРТУ, 1995.

62. Галкина В.А. Дискретная математика: комбинаторные методы оптимизации. – М.: Гелиос АРВ, 2003.

63. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982.

64. Кирсанов М.Н. Графы в MAPLE. Задачи, алгоритмы, программы. – М.: Физматлит, 2007.

65. Костюкова Н.И. Графы и их применение. Комбинаторные алгоритмы для программистов: Учеб. пос. – М.: Интернет-университет информационных технологий; БИНОМ, Лаборатория знаний, 2007.

66. Кофман А. Введение в прикладную комбинаторику. – М.: Наука, 1975.

67. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978.

68. Курейчик В.М. Математическое обеспечение КТП с применением САПР. – М.: Радио и связь, 1990.

69. Курейчик В.М. Дискретная математика: Учеб. пос. Ч. 2. Элементы теории графов. – Таганрог: Изд-во ТРТУ, 1998.

70. Курейчик В.М., Гладков Л.А., Лисяк Н.К., Курейчик В.В. Учебное пособие для практических и лекционных занятий по курсу «Математические основы дискретной техники». Ч. 2. – Таганрог: Изд-во ТРТУ, 1998.

71. Мелихов А.Н., Берштейн Л.С., Курейчик В. М. Применение графов для проектирования дискретных устройств. - М.: Наука, 1974.

72. Мелихов А.Н., Карелин В.П. Методы распознавания изоморфизма и изоморфного вложения четких и нечетких графов. – Таганрог: Изд-во ТРТУ, 1995.

73. Микони С.В. Элементы дискретной математики. – СПб.: Изд-во ПГУПС, 1999.

74. Палий И.А. Дискретная математика: Курс лекций. – М.: ЭКСМО, 2008.

75. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.

В любой науке столько истины, сколько в ней математики.

И. Кант

ЗАКЛЮЧЕНИЕ

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

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

Решение задачи минимизации булевых функций позволяет решать задачи синтеза комбинационных устройств и логических схем, проблемы представления булевых функций в виде логических элементов.

Теория графов и гиперграфов является основой моделирования и разработки современной цифровой вычислительной техники и информационных систем.

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

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

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

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

ПРИЛОЖЕНИЕ 1

оСНОВНЫЕ ПОЛОЖЕНИЯ гост 19.701-90 (исо 5807-85) «сХЕМЫ АЛГОРИТМОВ, ПРОГРАММ, ДАННЫХ И СИСТЕМ. уСЛОВНЫЕ ОБОЗНАЧЕНИЯ И ПРАВИЛА ВЫПОЛНЕНИЯ»

1. Введение

Схема программы отображает последовательность операций в программе и состоит:

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

2) линейных символов, указывающих поток управления;

3) специальных символов, используемых для облегчения написания и чтения схемы.

2. Символы

2.1. Процесс

Символ отображает функцию обработки данных любого вида.

2.2. Предопределенный процесс

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

2.3. Ручная операция

Символ отображает любой процесс, выполняемый человеком.

2.4. Подготовка

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

2.5. Решение

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

2.6. Линия

Символ отображает поток данных или управления.

2.7. Соединитель

Символ используется для обрыва ЛИНИИ и продолжения ее в другом месте. Соответствующие символы-соединители должны содержать одно и тоже уникальное обозначение.

2.8. Терминатор

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

2.9. Комментарий

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

3. Правила применения символов

3.1. Символ предназначен для графической идентификации функции, которую он обозначает, независимо от текста внутри этого символа.

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

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

4. Правила выполнения соединений

4.1. Направление потока слева направо и сверху вниз считается стандартным.

4.2. В схемах следует избегать пересечения линий. Изменение направления в точках пересечения не допускается.

4.3. Линии в схемах должны подходить к символу либо слева, либо сверху, а исходить либо справа, либо снизу. Линии должны быть направлены к центру символа.

4.4. При необходимости линии в схемах следует разрывать для избежания излишних пересечений или слишком длинных линий, а также, если схема состоит их нескольких страниц. Соединитель в начале разрыва называется внешним соединителем, а соединитель в конце разрыва - внутренним соединителем.

Ссылки к страницам могут быть приведены совместно с символом комментария для их соединителей.

5. Специальные условные обозначения

Несколько выходов из символа следует показывать:

1) несколькими линиями от данного символа к другим символам;

2) одной линией от данного символа, которая затем разветвляется в соответствующее число линий.

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

ДЛЯ ЗАМЕТОК

Дата добавления: 2015-10-26