Дискретная математика. Алгоритмы: теория и практика.

М. : ДМК Пресс, 2019.

Авдошин С. М., Набебин А. А.

Книга содержит необходимые сведения из теории алгоритмов, теории графов, комбинаторики. Рассматриваются частично рекурсивные функции, машины Тьюринга, приводятся некоторые варианты алгоритмов (ассоциативные исчисления, системы подстановок, грамматики, продукции Поста, нормальные алгоритмы Маркова, операторные алгоритмы). Описываются основные типы графов (мультиграфы, псевдографы, эйлеровы графы, гамильтоновы графы, деревья, двудольные графы, паросочетания, сети Петри, планарные графы, транспортные сети). Приводятся некоторые часто используемые в практике алгоритмы на графах. Рассматриваются классические комбинаторные конфигурации и их производящие функции, рекуррентные последовательности. В основу книги положен многолетний опыт преподавания авторами дисциплины «Дискретная математика» на факультете бизнес-информатика, на факультете компьютерных наук Национального исследовательского университета Высшая школа экономики и на факультете автоматики и вычислительной техники Национального исследовательского университета  Московский энергетический институт. Книга предназначена для студентов бакалавриата, обучающихся по направлениям 09.03.01 «Информатика и вычислительная техника», 09.03.02 «Информационные системы и технологии», 09.03.03 «Прикладная информатика», 09.03.04 «Программная инженерия», а также для ИТ-специалистов и разработчиков программных продуктов.

Ключевые слова: производящие функции, комбинаторика, двудольные графы, сети Петри, grammar, combinatorics, graph, графы, matchings, Petri nets, машина Тьюринга, planar graphs, graph coloring, мультиграфы, теория алгоритмов, Turing machine, generating functions, multigraph, trees, algorithm theory, partial recursive functions and predicates, primitive recursive functions and predicates, general recursive functions and predicates, universal partial recursive function, Goedel numbering of Turing machines, recursively enumerable sets, частично рекурсивные функции и предикаты, примитивно рекурсивные функции и предикаты, общерекурсивные функции и предикаты, универсальная частично рекурсивная функция, Геделева нумерация машин Тьюринга, рекурсивно перечислимые множества, general recursive sets, algorithmically undecidable problems, associative calculus, общерекурсивные множества, алгоритмически неразрешимые проблемы, ассоциативные исчисления, system of substitutions, Post's productions, Marcov's normal algorithms, operator algorithms, Göedel's theorem, системы подстановок, грамматики, продукции Поста, нормальные алгоритмы Маркова, операторные алгоритмы, теоремы Геделя, pseudograph, псевдографы, circumventions of graphs, Eulerian graphs, Hamiltonian graphs, Gray codes, cycles in graphs, обходы графов, эйлеровы графы, гамильтоновы графы, коды Грея, деревья, циклы в графах, bipartite graphs, systems of various representatives, паросочетания, системы различных представителей, планарные графы, раскраска графов, flows in transport networks, Stirling numbers, Bell numbers, Catalan numbers, recurrent sequences, partially ordered sets, потоки в транспортных сетях, числа Стирлинга, числа Белла, числа Каталана, рекуррентные последовательности, частично упорядоченные множества