Вопросы к экзамену по дискретной математике для направлений подготовки 01020062 "Фундаментальная информатика и информационные технологии"



Дата03.12.2012
Размер27.9 Kb.
ТипВопросы к экзамену
ВОПРОСЫ К ЭКЗАМЕНУ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ

для направлений подготовки 01020062 "Фундаментальная информатика и информационные технологии"

(1 курс, 101 - 102 группы )

  1. Множества и операции над ними. Булеан. Реализация множеств и операции в ЭВМ. Отношения и их представления в ЭВМ.



  1. Выборки, перестановки, сочетания, перестановки с повторениями, сочетания с повторениями. Биномиальные коэффициенты, их свойства. Биномиальная теорема.



  1. Полиномиальная формула. Числа Стирлинга первого и второго рода.



  1. Генерация комбинаторных объектов: перестановок, размещений, подмножеств, композиций и разбиений.



  1. Формула включений и исключений. Оценки для числа элементов, не обладающих ни одним из свойств. Формула для числа элементов, обладающих в точности r свойствами.



  1. Производящие функции. Примеры применения метода производящих функций для решения комбинаторных задач. Линейные рекуррентные соотношения с постоянными коэффициентами. Решение линейных рекуррентных соотношений. Числа Фибоначчи.



  1. Логика высказываний. Операции логики. Система аксиом и некоторые теоремы L–теории.



  1. Логика предикатов. Операции над предикатами и кванторами.



  1. Булева алгебра. Функции алгебры логики. Равенство функций. Тождества для элементарных функций.



  1. Разложение функции алгебры логики по переменным. Нормальные формы. Теорема о совершенной дизъюнктивной нормальной форме. Полные системы. Примеры полных систем (с доказательством полноты).



  1. Теорема Жегалкина о представимости функции алгебры логики полиномом. Понятие замкнутого класса. Замкнутые классы. Двойственность. Класс самодвойственных функций, его замкнутость. Класс монотонных функций, его замкнутость. Лемма о несамодвойственной функции.



  1. Лемма о немонотонной функции. Лемма о нелинейной функции. Теорема Поста о полноте системы функций алгебры логики. Теорема о максимальном числе функций в базисе в алгебре логики.



  1. Минимизация ДНФ. Метод минимизирующих карт. Контактные схемы. Минимизация ДНФ методом Квайна - Мак-Класски.



  1. Элементы теории графов. Основные определения. Изоморфизм, гомеоморфизм. Пути и циклы. Деревья. Цикломатическое число и фундаментальные циклы. Представления графов и деревьев в ЭВМ.



  1. Планарные графы. Формула Эйлера. Доказательство непланарности графов К5 и К3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону). Раскраски графов. Графы с атрибутами.
    Независимые множества и покрытия.



  1. Задачи и алгоритмы на графах. Кратчайшие пути. Кратчайшее остовное дерево. Алгоритмы Прима и Крускала построения остовного дерева.



  1. . Эйлеровы пути и циклы. Задача почтальона. Гамильтоновы циклы. Задача коммивояжера.



  1. Путь минимальной суммарной длины во взвешенном графе. Алгоритм Дейкстры. Алгоритм Флойда построения кратчайших путей в орграфе.



  1. Потоки в селях. Теорема Форда и Фалкерсона. Алгоритм Форда-Фалкерсона построения максимального потока сети.



  1. Кодирование. Алфавитное кодирование. Разделимые коды. Критерий однозначности декодирования. Неравенство Макмиллана. Условие существования разделимого кода с заданными длинами кодовых слов.



  1. Оптимальные коды и их свойства. Лемма о редукции. Алгоритм Хаффмана построения оптимальных кодов.



  1. Самокорректирующие коды. Коды с исправлением одной ошибки. Верхняя и нижняя оценки мощности максимального кода. Коды Хэмминга, их свойства. Алгоритм декодирования для кодов Хэмминга.

10. 05.2012 Доцент кафедры алгебры и геометрии

Кочугаев П. Н..

Похожие:

Вопросы к экзамену по дискретной математике для направлений подготовки 01020062 \"Фундаментальная информатика и информационные технологии\" iconПрограмма вступительного испытания по предмету «Информационные технологии»
Фундаментальная информатика и информационные технологии (магистерские программы: Фундаментальная информатика и информационные технологии,...
Вопросы к экзамену по дискретной математике для направлений подготовки 01020062 \"Фундаментальная информатика и информационные технологии\" iconРабочей программы дисциплины Основы программирования Место дисциплины в структуре ооп принципы построения курса: Курс входит в профессиональный цикл ооп 010300 «Фундаментальная информатика и информационные технологии»
Курс входит в профессиональный цикл ооп 010300 «Фундаментальная информатика и информационные технологии»
Вопросы к экзамену по дискретной математике для направлений подготовки 01020062 \"Фундаментальная информатика и информационные технологии\" iconРабочей программы дисциплины Дискретная математика Место дисциплины в структуре ооп принципы построения курса: Курс входит в профессиональный цикл ооп 010300 «Фундаментальная информатика и информационные технологии»
Курс входит в профессиональный цикл ооп 010300 «Фундаментальная информатика и информационные технологии»
Вопросы к экзамену по дискретной математике для направлений подготовки 01020062 \"Фундаментальная информатика и информационные технологии\" iconМесто дисциплины в структуре ооп принципы построения курса: Курс входит в профессиональный цикл ооп 010300 «Фундаментальная информатика и информационные технологии»
Курс входит в профессиональный цикл ооп 010300 «Фундаментальная информатика и информационные технологии»
Вопросы к экзамену по дискретной математике для направлений подготовки 01020062 \"Фундаментальная информатика и информационные технологии\" iconМесто дисциплины в структуре ооп принципы построения курса: Курс входит в профессиональный цикл ооп 010300 «Фундаментальная информатика и информационные технологии»
Курс входит в профессиональный цикл ооп 010300 «Фундаментальная информатика и информационные технологии»
Вопросы к экзамену по дискретной математике для направлений подготовки 01020062 \"Фундаментальная информатика и информационные технологии\" iconМесто дисциплины в структуре ооп принципы построения курса: Курс входит в математический и естественнонаучный цикл ооп 010300 «Фундаментальная информатика и информационные технологии»
Курс входит в математический и естественнонаучный цикл ооп 010300 «Фундаментальная информатика и информационные технологии»
Вопросы к экзамену по дискретной математике для направлений подготовки 01020062 \"Фундаментальная информатика и информационные технологии\" iconМесто дисциплины в структуре ооп принципы построения курса: Курс входит в математический и естественнонаучный цикл ооп 010300 «Фундаментальная информатика и информационные технологии»
Курс входит в математический и естественнонаучный цикл ооп 010300 «Фундаментальная информатика и информационные технологии»
Вопросы к экзамену по дискретной математике для направлений подготовки 01020062 \"Фундаментальная информатика и информационные технологии\" iconРабочей программы дисциплины Логика Место дисциплины в структуре ооп принципы построения курса: Курс входит в математический и естественнонаучный цикл ооп 010300 «Фундаментальная информатика и информационные технологии»
Курс входит в математический и естественнонаучный цикл ооп 010300 «Фундаментальная информатика и информационные технологии»
Вопросы к экзамену по дискретной математике для направлений подготовки 01020062 \"Фундаментальная информатика и информационные технологии\" iconПрограмма вступительного экзамена для направления подготовки магистров 010300. 68 "Фундаментальная информатика и информационные технологии "
Рам и языке высокого уровня. Временная и емкостная сложность алгоритмов для разных представлений. Сложность в среднем и наихудшем....
Вопросы к экзамену по дискретной математике для направлений подготовки 01020062 \"Фундаментальная информатика и информационные технологии\" iconМетодическое обеспечение курса «Вычислительная математика» направления 010300. 68 «Фундаментальная информатика и информационные технологии»

Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org