Темы творческих работ (эссе) СГА → Математическая логика и теория алгоритмов

Математическая логика и теория алгоритмов (1000) , модуль 2 - Темы творческих работ (эссе) СГА

  • алгоритмические проблемы в теории автоматов. Что могут и что не могут конечные автоматы
  • алгоритмические проблемы в теории грамматик
  • аналитический и табличный методы  приведения  пропозициональных формул к совершенным нормальным формам
  • булевы функции и способы их представления. Многочлены Жегалкина. Определение полноты систем булевых функций
  • высказывания и операции над ними.  Построение таблиц  истинности пропозициональных формул
  • замкнутые классы и их связь с функциональной полнотой. Монотонные функции и их свойства. Определение монотонной функции в терминах решеток
  • исчисление высказываний.  Использование аксиом и правил для организации логического вывода
  • исчисление предикатов. Организация логического вывода в исчислении предикатов
  • логические функции, логические схемы и бинарные программы
  • метод резолюций в логике предикатов
  • минимизация булевых функций с использованием алгоритма Квайна
  • минимизация булевых функций с использованием карт Карно
  • непротиворечивость и полнота логических исчислений. Семантическая и формальная непротиворечивость
  • общая схема доказательства эквивалентности машин Тьюринга и рекурсивных функций
  • основная идея доказательства существования универсальной машины Тьюринга и блок-схема ее построения
  • основные равносильности  логики  предикатов. 
  • понятие неоднозначности в теории грамматик. Привести примеры неоднозначных грамматик и неоднозначного вывода в них
  • понятие сложности вычислений. Схемы алгоритмов и потоков данных
  • предикаты. Использование кванторных предикатов для записи различных предложений.  Определение выполнимости и  общезначимости предикатных формул
  • приведение предикатных формул к клаузальной форме
  • приведение предикатных  формул  к  нормальной форме и сколемовской стандартной форме
  • приведение пропозициональных формул к дизъюнктивной и конъюнктивной нормальной формам
  • применение булевых функций для анализа и синтеза дискретных устройств. Анализ  и  синтез релейно-контактных схем. 
  • проверка логической правильности рассуждений.  Логическое следствие
  • связь формальных грамматик и конечных автоматов
  • сравнение сложности вычислений на одноленточной и многоленточной машинах Тьюринга на примере распознавания палиндромов в двухбуквенном алфавите
  • упрощение и преобразование логических схем
  • упрощение логических выражений с использованием  основных тождеств алгебры логики
  • формальные грамматики и их свойства
  • формальные грамматики. Классификация Хомского. Грамматики типа 2 и их использование при построении трансляторов

Данный список тем процитирован в учебных целях с сайта Современной Гуманитарной Академии, www.muh.ru