Учебное пособие написано на основе курсов "Дополнительные главы дискретной математики" и "Функциональные системы", которые автор на протяжении ряда лет читал на факультете вычислительной математики и кибернетики МГУ.
Пособие состоит из 6 глав, дополненных задачами и упражнениями.
Глава 1 "Множества, отношения, функции" служит теоретико-множественной и алгебраической основой при изучении последующих глав книги.
Глава 2 "Замкнутые классы булевых функций" содержит общие факты по булевым функциям, а также современное изложение классических результатов Э. Поста по перечислению всех замкнутых классов булевых функций. Глава 3 "Функции многозначной логики" представляет собой введение в теорию функций многозначной логики. Главы 4 и 5 посвящены конечным автоматам: в главе 4 рассматриваются автоматы-распознаватели, а в главе 5 - автоматы- преобразователи. В главе 6 "Машины Тьюринга и вычислимые функции" определяются машины Тьюринга и функции, вычислимые на них. Устанавливается совпадение класса вычислимых функций с классом частично-рекурсивных функций. Вводятся понятия Р-сводимости и NP-полноты. Устанавливается существование NP-полных проблем. Студентам, аспирантам и научным сотрудникам, специализирующимся в области дискретной математики и кибернетики.
Как правильно задавать вопросы?
Будьте вежливы и спрашивайте о товаре, на карточке которого вы находитесь
Если вы обнаружили ошибку в описанием товара, воспользуйтесь функцией
Как отвечать на вопросы?
Отвечать на вопросы могут клиенты, купившие товар, и официальные представители.
Выбрать «Лучший ответ» может только автор вопроса, если именно этот ответ ему помог.