Математическая логика и теория алгоритмов

Ведение ИНФОРМАЦИОННО-ЛОГИЧЕСКИЕ СТРУКТУРЫ 1. ЭЛЕМЕНТАРНОЕ ВВЕДЕНИЕ В ТЕОРИЮ МНОЖЕСТВ Теоретико-множественная символика и терминология Операции над множествами и их основные свойства Декартово произведение множеств и отношения на множествах Элементы теории отображений Отношение эквивалентности и разбиение множества на классы Отношения порядка Базовые алгебраические системыВопросы и упражнения для самопроверки АЛГЕБРА ВЫСКАЗЫВАНИЙ И ЛОГИКА ПРЕДИКАТОВ Алгебраические операции над высказываниями и их свойства Формулы и функции алгебры логики. Закон двойственности Совершенные дизъюнктивные и конъюнктивные нормальные формы булевых функций Полнота и замкнутость системы булевых функций. Представление о классах Поста Логика предикатовВопросы и упражнения для самопроверки ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ Алфавит, формулы и подформулы исчисления высказываний Аксиомы исчисления высказываний Основные правила вывода Определение доказуемой (выводимой) формулы Производные правила вывода. Теорема дедукции Связь алгебры высказываний с исчислением высказыванийВопросы и упражнения для самопроверки ИСЧИСЛЕНИЕ ПРЕДИКАТОВ Определение формулы исчисления предикатов Аксиомы исчисления предикатов и основные правила вывода Общезначимость и выполнимость формул исчисления предикатов Предваренная, скулемовская и клаузальная формы представления формул исчисления предикатовВопросы и упражнения для самопроверки ОСНОВНЫЕ ПОНЯТИЯ АКСИОМАТИЧЕСКИХ ТЕОРИЙ ПЕРВОГО ПОРЯДКА Формальные аксиоматические теории Логические и специальные аксиомы Правила вывода и понятие доказательства в теории первого порядка Понятия интерпретации и модели теории. Изоморфизм интерпретаций Примеры аксиоматических теорий первого порядка со специальными аксиомамиВопросы и упражнения для самопроверки ПРОБЛЕМЫ АКСИОМАТИЧЕСКОГО ПОСТРОЕНИЯ ТЕОРИИ ПЕРВОГО ПОРЯДКА Проблема непротиворечивости Проблема независимости системы аксиом Формализуемость и разрешимость теории Категоричность теории Проблема полноты теорииЛИТЕРАТУРА К ГЛАВЕ IП. НЕТРАДИЦИОННЫЕ ЛОГИКИ 1. ОСНОВНЫЕ НАПРАВЛЕНИЯ ИССЛЕДОВАНИЙ В ОБЛАСТИ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА Естественный и искусственный интеллект Некоторые философские аспекты проблем искусственного интеллекта Примеры систем искусственного интеллектаВопросы и упражнения для самопроверки ОСНОВНЫЕ ПРИНЦИПЫ ПОСТРОЕНИЯ СИСТЕМ АВТОМАТИЗАЦИИ ДОКАЗАТЕЛЬСТВ Постановка задачи автоматического доказательства теорем Унификация Метод резолюций Алгоритм поиска опровержения методом резолюций Доказательство истинности логических клауз методом резолюцийВопросы и упражнения для самопроверки ОСНОВНЫЕ ПРИНЦИПЫ ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ Использование формализмов логики для алгоритмических вычислений. Факты, правила, запросы Общие правила выполнения запросов логическими программами Методика составления логических программВопросы и упражнения для самопроверки СИСТЕМЫ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА, ОСНОВАНННЫЕ НА ЗНАНИЯХ Представление и использование нечетких знаний Нечеткая, вероятностная и монотонная логики Нечеткие множества и нечеткие выводы Многозначная логика Модальные логики Продукционные системы О механизмах вывода в экспертных системахВопросы и упражнения для самопроверкиЛИТЕРАТУРА К ГЛАВЕ ПШ. ТЕОРИЯ АЛГОРИТМОВ 1. УТОЧНЕНИЕ ПОНЯТИЯ АЛГОРИТМА НА ОСНОВЕ ЧАСТИЧНО РЕКУРСИВНЫХ ФУНКЦИЙ Интуитивное понятие алгоритма. Общие свойства алгоритмов Эффективно вычислимые и примитивно рекурсивные функции Оператор минимизации и частично рекурсивные функции. Тезис ЧерчаВопросы и упражнения для самопроверки УТОЧНЕНИЕ ПОНЯТИЯ АЛГОРИТМА НА ОСНОВЕ МАШИН ТЬЮРИНГА .Модель одноленточной машины Тьюринга Композиция, итерация и разветвление машин Тьюринга Методологическое значение моделей машин ТьюрингаВопросы и упражнения для самопроверки НОРМАЛЬНЫЕ АЛГОРИТМЫ МАРКОВА Основные понятия Композиция, итерация и разветвление нормальных алгоритмов. Эквивалентность тезиса Черча и принципа нормализации МарковаВопросы и упражнения для самопроверки АНАЛИЗ СЛОЖНОСТИ АЛГОРИТМОВ Подходы к оценке сложности алгоритмов. Асимптотика Меры и оценки сложности Анализ сложности генерирования перестановок Класс задач, детерминировано решаемых с полиномиальной Сложностью NP-полные и NP-трудные задачи Понятие алгоритмически неразрешимых проблем Примеры алгоритмически неразрешимых проблемВопросы и упражнения для самопроверкиЛИТЕРАТУРА К ГЛАВЕ IIIЗАКЛЮЧЕНИЕ
 
РЕЗЮМЕ След >