Кривий С. Л.

До навчального посібника ввійшли розділи, які використовують основні поняття теорії множин та відношень, загальної алгебри, математичної логіки і теорії алгоритмів. Наступний розділ присвячений основним алгоритмічним системам — частково рекурсивним функціям, машинам Поста, машинам ьюрінга і алгоритмам Маркова. Ці системи застосовуються для уточнення поняття алгоритму, означення алгоритмічної розв’язуваності та встановлення алгоритмічної повноти мов програмування. Розглянуто основні поняття та методи теорії графів.

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

Одним з найбільших розділів даного посібника є розділ з теорії складності оочислень за Тьюрінгом. Машини Тьюрінга, як одна з найбільш уживаних алгоритмічних систем, служать еталоном виміру складності обчислень що дає змогу якісно оцінювати алгоритми розв’язку однієї і тієї самої задачі. У цьо-му розділі розглянуто найважливіші модифікації машин Тьюрінга. До цих модифікацій, зокрема, відносяться односторонні, недетерміновані та багатостріч-кові машини Тьюрінга, а також описані такі моделі обчислень, як RAM і PRAM (для оцінки послідовних та паралельних алгоритмів).

Для студентів вищих навчальних закладів та аспірантів, які навчаються за напрямом «Комп’ютерні науки».