|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Избранные главы дискретной математикикнига
- Автор: Марченков С.С.
- Год издания: 2023
- Место издания: Физматлит Москва
- Объём: 192 страниц (12,2 печатных листов)
- ISBN: 978-5-9221-1969-6
- Тираж: 300 экз.
- Учебное пособие без грифа
- Аннотация: Пособие написано на основе курсов «Дополнительные главы дискретной математики» и «Функциональные системы», которые автор на протяжении ряда лет читал на факультете вычислительной математики и кибернетики МГУ. Пособие состоит из шести глав. Глава 1 «Множества, отношения, функции» служит теоретико-множественной и алгебраической основой при изучении последующих глав книги. Глава 2 «Замкнутые классы булевых функций» содержит общие факты по булевым функциям, а также современное изложение классических результатов Э. Поста по перечислению всех замкнутых классов булевых функций. Глава 3 «Функции многозначной логики» представляет собой введение в теорию функций многозначной логики. Главы 4 и 5 посвящены конечным автоматам: в главе 4 рассматриваются автоматы-распознаватели, а в главе 5 – автоматы-преобразователи. В главе 6 «Машины Тьюринга и вычислимые функции» определяются машины Тьюринга и функции, вычислимые на машинах Тьюринга. Устанавливается совпадение класса вычислимых функций с классом частично-рекурсивных функций. Вводятся понятия Р-сводимости и NP-полноты. Устанавливается существование NP-полных проблем. Каждая глава содержит задачи и упражнения. Для студентов, аспирантов и научных сотрудников, специализирующихся в области дискретной математики и кибернетики.
- Добавил в систему: Марченков Сергей Серафимович