| Главная | Предыд. | След. | Др. раздел |
Дискретная математика.
Предисловие.
Основной спецификой дискретной математики является дискретность, т.е. главный антипод непрерывности. В широком смысле дискретная математика включает в себя и такие сложившиеся разделы математики, как теория чисел, алгебра, математическая логика и ряд разделов, которые наиболее интенсивно стали развиваться в середине этого века в связи с внедрением ЭВМ и посвящённые изучению сложных управляющих систем. Дискретная математика является не только фундаментом математической кибернетики, но и важным звеном математического образования для специалистов в области прикладной математики. Главная задача курса - это обучение методам и мышлению, характерным для дискретной математики.
Введение.В курсе дискретной математики изучаются: теория функциональных систем, теория графов и сетей, теория кодирования, комбинаторный анализ, теория дискретных логических вычислительных устройств, формальные грамматики. В разделе "формальные грамматики" изучаются грамматики четырех видов и порождаемые ими языки. Рассматриваются соотношения между этими языками и проблема грамматического разбора. Излагаются свойства КС-грамматик и их применение к синтезу языков программирования.
Комбинаторный анализ.Предмет дискретной математики. Множества, покрытия и разбиения множеств. Операции над ними. Правила суммы. Правила произведения. Размещения с повторениями и без. Сочетания и сочетания с повторениями. Бином Ньютона.
Графы и сети.Графы. Способы задания графов. Изоморфизм и гомоморфизм графов. Оценка числа графов. Плоские графы. Деревья. Раскраска графа. Сети.
Функциональные системы с операциями.Понятие булевой функции. Элементарные булевы функции. Формулы. Принцип двойственности. Совершенная дизъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма. Полнота систем булевых функций. Замкнутость. Критерий функциональной полноты. Теорема о минимальном базисе. Проблема минимизации дизъюнктивной нормальной формы. Тривиальный алгоритм минимизации. Сокращённая дизъюнктивная нормальная форма. Тупиковая дизъюнктивная нормальная форма. Алгоритм построения всех тупиковых дизъюнктивных нормальных форм. Геометрическая интерпретация проблемы минимизации дизъюнктивной нормальной формы.
Синтез схемы из функциональных элементов.Понятие схемы из функциональных элементов и проблема синтеза схем. Функция Шеннона. Практические методы синтеза.
Алгоритмические модели.Машины Тьюринга и вычислимые функции. О понятии "алгоритм" и необходимости его уточнения. Понятие машины Тьюринга (одноленточная детерминированная). Классы числовых функций. Понятие вычислимой функции. Тезис Тьюринга. Проблема самоприменимости машин Тьюринга. Простейшие числовые функции и их вычислимость. Операции суперпозиции, примитивной рекурсии, минимизации. Классы рекурсивных функций, соотношение между нами и классом вычислимых функций.
Теория кодирования.Схема передачи информации, двоичное кодирование. Примеры кодовых систем. Критерий однозначности декодирования. Самокорректирующиеся коды (коды Хэмминга). Оптимальные коды (метод Хаффмена).
Функции k-значной логики.Основные равносильности. Замкнутые классы и полные системы. Особенности k-значных логик.
Конечные автоматы и регулярные выражения.Понятия недетерминированных конечных автоматов и k-ленточных машин Тьюринга. Проблема P=?NP. NP-полные проблемы. Выполнимость конъюнктивной нормальной формы, 3-вып., 2-вып. Покрытие таблиц. Задача о клике.
Формальные грамматики.Языки, порождаемые грамматиками. Проблема грамматического разбора. Свойства КС-грамматик. КС-грамматики и синтез языков программирования.
| Главная | Предыд. | След. | Др. раздел |