Программа к экзамену по курсу Дискретная математика icon

Программа к экзамену по курсу Дискретная математика



НазваниеПрограмма к экзамену по курсу Дискретная математика
Дата конвертации27.08.2012
Размер23.43 Kb.
ТипПрограмма
1. /Программа к экзамену по курсу Дискретная математика.docПрограмма к экзамену по курсу Дискретная математика

Программа к экзамену по курсу Дискретная математика

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

1. Определение Б.Ф., способы задания Б.Ф.

2. Понятие формулы, определение СДНФ, СКНФ для Б.Ф.

3. Многочлен Жегалкина. теорема о представлении Б.Ф. многочленом Жегалкина.

4. Способы вычисления коэффициентов многочлена Жегалкина для Б.Ф.

5. Понятие веса Б.Ф., простейшие свойства весов, вес линейной функции.

6. Представление Б.Ф. рядом Фурье.

7. Смысл коэффициентов Фурье, быстрое преобразование Фурье.

8. Функциональная полнота, классы Поста, примеры.

9. Теорема Поста.

10. Проблема минимизации Б.Ф., основные определения.

11. Алгоритм Квайна-Мак-Класки построения минимальной ДНФ.

Теория графов

1 .Основные определения теории графов.

2. Цепи, пути, маршруты в графе. Теорема о числе путей.

3. Минимальный путь, алгоритм построения минимального пути.

4. Нагруженный граф, алгоритм Дейкстры построения кратчайшего пути. Пример.

5. Теорема о корректности работы алгоритма Дейкстры.

6. Понятие связности и сильной связности в графе. Примеры.

7. Оценка числа дуг в графе. Критерий сильной связности

8. Цикловой базис в графе, число векторов в цикловом базисе

9. Деревья, теорема о свойствах деревьев. Критерий связности графа.

10. Алгоритм построения остовного дерева графа, алгоритм построения циклового базиса графа.

11. Алгоритм Краскала построения минимального остовного дерева графа. Пример.

12. Теорема о корректности работы алгоритма Краскала.

13. Корневые деревья, теорема о свойствах корневых деревьев.

14. Необходимое и достаточное условие «быть корневым деревом» для ориентированного графа.

15. Теорема Татта.

16. Понятие Эйлерова графа. Критерий того, что граф Эйлеров для ориентированных и неориентированных графов.

17. Графы де Брейна. Существование Эйлерова контура в графе де Брейна. Понятие последовательности де Брейна.

18. Понятие Гамильтонова графа. Достаточное условие того, что граф Гамильтонов.

19. Центр и радиус графа, Оценка радиуса 1-графа без петель. Диаметр графа, связь радиуса и диаметра для неориентированного графа.

20. Понятие алгебры смежности графа, оценка диаметра графа.

Теория кодов

1. Основные определения теории кодов, примеры.

2. Корректирующие возможности кодов.

3. Граница Синглтона, МДР-коды, примеры.

4.
Граница Хемминга, совершенные коды, примеры.

5. Двоичный код Хемминга, его декодирование.

6. Линейные коды: основные определения, расстояние линейного кода.

7. Декодирование по синдрому.

8. Линейные циклические коды: основные определения, проверочная и порождающая матрица линейного циклического кода.

9. Двойственные коды: основные соотношения.

Комбинаторика

1. Понятие трансверсали, теорема Холла.

2. Перманенты и их свойства, формула Райзера

2. Латинские квадраты и прямоугольники.

3. Декомпозиция неотрицательных матриц. Теорема Биркгофа.

4. Метод включения-исключения. Примеры



Похожие:

Программа к экзамену по курсу Дискретная математика iconПрограмма к зачету по курсу Дискретная математика
Оценка числа дуг в графе. Критерий сильной связности Цикловой базис в графе, число векторов в цикловом базисе
Программа к экзамену по курсу Дискретная математика iconВопросы к экзамену по курсу: "Алгоритмы и процессоры цифровой обработки сигналов"
Линейная дискретная система с постоянными параметрами, импульсная характеристика лпп системы
Программа к экзамену по курсу Дискретная математика iconРабочая программа по математике в 5 классе, Петрунина Ивана Николаевича, учителя I квалификационной категории
Рабочая программа по курсу математики в 5-м классе составлена для умк виленкина Н. Я., Жохова В. И., Чеснокова А. С., Шварцбурда...
Программа к экзамену по курсу Дискретная математика iconПрограмма по курсу «Криминология» для студентов факультета истории и международных отношений по специальности «История» и«Юриспруденция»
Программа по курсу «Криминология» / Сост. Малаев С. С. – Брянск: Изд-во бгу, 2010. – 15 с
Программа к экзамену по курсу Дискретная математика iconПрограмма по курсу «Правоохранительные органы» для студентов факультета истории и международных отношений по специальности «История» и«Юриспруденция»
Программа по курсу «Правоохранительные органы» / Сост. Малаев С. С. – Брянск: Изд-во бгу, 2009. – 28 с
Программа к экзамену по курсу Дискретная математика iconДокументы
1. /Ф.А. Новиков - Дискретная Математика для Программистов.djvu
Программа к экзамену по курсу Дискретная математика iconДокументы
1. /Ф.А. Новиков - Дискретная Математика для Программистов.djvu
Программа к экзамену по курсу Дискретная математика iconВопросы к экзамену по курсу «Финансовая среда предпринимательства, предпринимательские риски»

Программа к экзамену по курсу Дискретная математика iconВопросы к экзамену по курсу «экономическая теория»
Утопический социализм в России (А. Н. Радищев, В. Г. Белинский, Н. Г. Чернышевский)
Программа к экзамену по курсу Дискретная математика iconДокументы
1. /Вопросы к экзамену по курсу РТЦиС.doc
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов