МЛиТА-2012

Программа экзамена МЛиТА-2012

 

1. Булевы функции.

Знать и уметь применять как определения и теоремы, так и приемы доказательства теорем:

задание функции таблицей и определение фиктивных переменных;

теоремы о задании булевых функций двоичными наборами, о числе булевых функций; свойства булевых функций;

понятие двойственности и теорема о построении двойственной для сложной функции;

теоремы об СДНФ, СКНФ, многочлене Жегалкина; минимизация СДНФ: три метода минимизации и доказательство корректности метода минимизирующих карт;

понятие классов замкнутости и классы замкнутости Поста, теорема Поста.

 

2. Исчисление высказываний.

Знать и уметь применять как определения и теоремы, так и приемы доказательства теорем:

Сигнатура формул исчисления высказываний, определение атомов и формул; интерпретация формул исчисления высказываний, тавтологические (всегда истинные) и противоречивые формулы;

понятие логического вывода, теоремы о логическом выводе в исчислении высказываний, использование интерпретаций для доказательства логических выводов;

силлогизмы, резольвента, теорема о резольвенте;

метод резолюций для исчисления высказываний.

 

3. Исчисление предикатов.

Знать и уметь применять как определения и теоремы, так и приемы доказательства теорем:

сигнатура формул исчисления предикатов, определение термов, атомов и формул;

кванторы и их свойства;

правила логического вывода в исчислении предикатов;

метод резолюций для исчисления предикатов, в том числе, предварённая форма, нормальная скулемовская форма, алгоритм унификации.

 

4. Конечные автоматы

Знать и уметь применять как определения и теоремы, так и приемы доказательства теорем:

определение конечного автомата, теорема о том, что конечный автомат не может рассматриваться как определение произвольного алгоритма;

определение распознающего автомата, регулярные множества и выражения, теорема Клини.

 

5. Языки и грамматики

Знать и уметь применять как определения и теоремы, так и приемы доказательства теорем:

операция конкатенация и её свойства, умножение множеств, определение языка, операции над языками;

определение КС-грамматики, определение LL(1) грамматики, определение автоматной грамматики;

теорема о связи автоматной грамматики с конечным распознающим автоматом;

алгоритм построения синтаксического анализатора для LL(1) грамматик;

теоремы о свойствах автоматных языков;

лемма о накачке, пример КС-языка, не являющегося автоматным.

6. Математическое понятие алгоритма.

Знать и уметь применять как определения и теоремы, так и приемы доказательства теорем:

определение алгоритма как машины Тьюринга – определение и примеры;

определение алгоритма как нормальной схемы алгорифма Маркова – определение и примеры;

определение алгоритма как частично-рекурсивной функции, примитивно-рекурсивные функции, обще-рекурсивные функции – определения и примеры.

 

7. Прикладная теория алгоритмов.

Знать и уметь применять как определения и теоремы, так и приемы доказательства теорем:

постфиксная запись формулы, теорема о том, что такая запись однозначно определяет дерево синтаксического разбора функции;

алгоритм вычисления выражения в постфиксной записи и его обоснование;

алгоритмы построения минимальных остовных деревьев (Краскала, Прима) и обоснование их корректности;

алгоритмы поиска кратчайших путей в графе (Форда-Беллмана, Дейкстры, Флойда), условия применения и доказательство корректности алгоритмов;

алгоритмы: поиска эйлеровых путей, максимального паросочетания и обоснование их корректности:

алгоритм Хаффмана и обоснование его корректности.

Экзамен будет проходить в письменной форме.

При подготовке следует воспользоваться материалами для подготовки прошлых лет:

1) задачи 2007 года

2) задачи 2008 года


Comments