Вопросы/задания: Билеты 7-й семестр

Распознанный текст из изображения:

ПЛОХ'РАИИА ЖУРСА ДИСКРЖТЕОК ИЖТЖИВТИИИ (4-й ж~~с, 3-й поток, осенщий семестр, 2ОО$ - 2ООб уч.год, аевгор - щюф. Е.П. Редькин ) 1. Элем~н~ы Графа» С~ос~бы заданиЯ Графов. 1'еометрическаЯ реализациЯ Графов Пути Цепи контуры и Циклы В Графах. ВерхнЯЯ Оценка числа неизОмОфорных графов с п1 ребрами 2. ДеревьЯ. Характеристические СВОЙства деревьев. ВерхнЯЯ оценка числа неизОМОфОрных корнеВых Деревьев с п1 ребрами Теорема Кэли О числе деревьев с занумерованными Вершинами

ДВУДОльные графы ПарОсочетаниЯ и трансверсали Критерий существОвания трансверсали (теОрема Холла).

4. Сети. П~токи В СетЯХ. СечениЯ сети. Теорема Форда — Фалкерсона О максимальнОЙ Величине пОтОка в сети.

'~* Булевы функции. Табличные заданиЯ булевых функциЙ. Формулы.

Простейшие зквивалентности. Разложение булевых функций по переменным," дизьюнктивные ~~рмальн~~ ф~рм~. Полнота ~и~~~~ бу~ев~х фунций. Примеры полных систем. Представление булевых функций пОлинОмами Жегалкина. ФункЦии 1-значнОЙ лОГики.

б. ВысказываниЯ» предикаты» квантор ОбЩнОсти и квантор суЩествованиЯ 1еометриче~ кий смысл кванторов МОДель» сигнатура модели» формулы В моДели СвобОДные и свЯзанные переменные Значение фОрмулы В мОДели. ИстиннОсть формулы на мОДели; на мнОжестве» тождественно истинные (ОбЩезначимые) фОрмулы 7. ЭквивалентнОсть формул. Правила переноса квантОра через ОтриЦа.— ние» Выноса квантора за скОбки и переименованиЯ свЯзанных переменных ПривеДенные фОрмулы» теОрема О приВеДенных фОрмулах. Нормальные фОрмулы; теорема О нОрмальных фОрмулах.

8.Схемы из функциональных злементов В базисе (Ч»й»-~. Синте~ схем с испо~ьзованием Д.Н.Ф. Метод Шеннона и асимптотически Оптимальный метод Синт~за схем. МОЩностноЙ Метод получениЯ ниж~ей Оценки ДлЯ слОжнОсти схем.

9. Ограниченно-детерминированные функции и автоматы. способы заданиЯ ОграниченнО детерминированных функЦий« Схемы автоматов иэ функиональных элементов и элементОВ задержки

Литература

1* Гаврилов Г.П., Сапоженко А.А. Задачи и упражнениЯ по курсу дискретной математики. Издание второе. К., "Наука", 1992.

2 Дискре".:~аЯ математика и математические ВОпрОсы кибернетики /ПОД реда~ци~Й С.В.Яблонского и О.Б.Лупанова. М., "Наука" » 1974.

3. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И.

Лекции по теории графов. М., "Наука", 1990 (стр.87-88,124-126).

4. Клини С. МатематическаЯ логика. М.." Мир.1973.

5. ЛупаНОВ О.Б. ЛекцИИ ПО МатЕМатИЧЕСКОй ЛОГИКЕ.Чс1стЬ 1 И Ча ть 2. М.: Изд-Во МГУ» 1970.

6. Лупанов О.Б. Асимптотические Оценки сложности управлЯюЩих систем. Изд-во МГУ, 1964.

7. Мендельсон Э. Введение В математическую логику. М.." Мир. 1973.

8. Нигматуллин Р.Г. Сложность булевых функций. М., "Наука", 1991.

9. Н~~иков П.С. Элементы математической логики. М.: Наука. Физматлит. 1973.

10.Редькин Н.П. ДискретнаЯ математика. Санкт-Петербург — Москва Краснодар: Изд-во "Лань", 2003.

11.Редькин Н.П. ДискретнаЯ математика. 11 М.: Изд-во ЦПИ при механико-математическом факультете МГУ, 2005.

12.ЯблОнский С.В. ВвеДение в Дискретную математику. Издание ВтОрОе. М., "Наука", 1986.

Файл скачан с сайта StudIzba.com

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