Вопросы по курсу «Введение в дискретную математику».
(Эти вопросы предварительные. Окончательный вариант сформируется ко времени зачета)
Понятие функции алгебры логики. Что есть формула? Реализация функций формулами. Понятия полноты и замкнутости. Важнейшие замкнутые классы. Теорема Поста. Функции к-значной логики. Особенности к-значных логик (в сравнении с двузначными). Автоматы, детерминированные и ограниченно-детерминированные функции. Операции над ограниченно-детерминированными функциями. Обратная связь. Структурные автоматы. Клеточные автоматы. Вычислимые функции и машина Тьюринга. Связь с формальными языками.Классификация Хомского.
Графы, реализация в евклидовом пространстве. Теорема Понтрягина-Куратовского для графов и связь с технологией производства чипов. Потоки в сетях и задачи в экономике. Теория кодирования. Алфавитное кодирование и понятия кодирования применительно к геному. Коды с исправлением ошибок. Криптография. Теория тестов и распознавание образов.