Темы индивидуальных заданий
(срок сдачи - с 22 мая по 27 мая 2017 года)
1) Математическая логика. Логика и интуиция. Логика традиционная и математическая логика. Понятие высказывания. Логические операции. Формулы логики высказываний. Таблицы истинности. Приоритет логических операций. Тавтология, противоречие, выполнимая формула. Проблема разрешимости. Равносильные формулы. Критерий равносильности. Основные равносильности логики высказываний. Математическая логика и современные ЭВМ. Примеры использования.
2) Нормальные формы формул логики высказываний. Понятие элементарной дизъюнкции, элементарной конъюнкции. Дизъюнктивная и конъюнктивная нормальные формы. Совершенные дизъюнктивные и конъюнктивные нормальные формы (СДНФ, СКНФ). Единственность представления в СКНФ (СДНФ). Приложение алгебры высказываний к логико-математической практике. Примеры использования.
3) Понятие логического следования, критерий логического следования. Схема логического рассуждения и правильность логического рассуждения. Способы проверки правильности логических рассуждений. Прямые и косвенные виды доказательств. Примеры использования.
4) Булевы функции. Понятие булевой функции. Число булевых функций. Булевы функции формулы логики высказываний. Полные системы булевых функций. Специальные классы булевых функций. Теорема Поста о полноте системы булевых функций. Применение булевых функций к релейно-контактным схемам. Примеры использования.
5) Логика предикатов. Понятие предиката. Классификация предикатов. Множество истинности предиката. Логические операции над предикатами. Кванторные операции. Синтаксис и семантика языка логики предикатов. Формулы логики предикатов. Равносильные формулы логики предикатов. Предваренная нормальная форма. Формализация в логике предикатов. Примеры использования.
6) Теория алгоритмов. Определение алгоритма. Характерные черты алгоритма. Необходимость уточнения алгоритма. Подход Геделя - Клини к формализации понятия алгоритма. Примеры использования.
7) Определение машины Тьюринга. Тезис Тьюринга. Машины Тьюринга и современные электронно-вычислительные машины. Композиция машин Тьюринга. Примеры использования.
8) Происхождение рекурсивных функций. Основные понятия теории рекурсивных функций и тезис Чёрча. Примитивно рекурсивные функции. Примитивная рекурсивность предикатов. Вычислимость по Тьюрингу примитивно рекурсивных функций. Функции Аккермана. Оператор минимизации. Общерекурсивные и частично рекурсивные функции. Вычислимость по Тьюрингу частично рекурсивных функций. Частичная рекурсивность функций, вычислимых по Тьюрингу. Примеры использования.
9) Марковские подстановки. Нормальные алгоритмы и их применение к словам. Нормально вычислимые функции. Примеры использования.
10) Алгоритмически неразрешимые проблемы. Сложность алгоритмов: в наихудшем случае и поведения в среднем. Сложность задачи. Классификация задач по сложности: класс Р и класс Е. Класс NP. NP-трудные и NP-полные задачи. Теорема Кука. Примеры использования.
11) Неклассические логики. Пропозициональные логики. Предикатные логики. Предикатные логики и их приложения к программированию. Алгоритмические логики. Примеры использования.
12) Алгоритмическая логика Хоара. Примеры использования.
13) Алгоритмы на графах. Алгоритмы обхода графа. Примеры использования.
14) Понятие и применение алгебры Жегалкина. Построение полинома Жегалкина. Примеры использования.
Примечание: К индивидуальному заданию должно обязательно прилагаться электронное издание, выполненное студентом в любой среде по собственному усмотрению и содержащее краткое изложение темы, тезаурус, библиографические записи и выводы.
Краткая справка:
Тезаурус (греч. thesaurus - сокровище, клад, запас, множество) - полный систематизированный набор терминов, слов, данных, семантических понятий в какой-либо области знаний с указанием на их значение.
Термины в тезаурусе должны быть связаны между собой, т.е. если внутрь определения одного термина входит один или несколько других терминов, то должна быть использована гиперссылка для перехода на указанные термины. Один из возможных вариантов приведен на рисунке 1.
Рисунок 1 – Пример одной из страниц гипертекстового тезауруса
Срок сдачи индивидуального задания, установленный преподавателем, должен быть обязательно соблюден.
Срок представления окончательного варианта задания на проверку с 22 мая 2017 года по 27 мая 2017 года (20 баллов max).
Промежуточная проверка – с 27 марта 2017 года по 1 апреля 2017 года (max 10 баллов). При отсутствии задания в указанные для промежуточной проверки сроки эти баллы снимаются с итоговой оценки полностью и без возможности их восстановления.
При сдаче задания на итоговую проверку не в указанные сроки - оценка снижается на 50%.