Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
А. Реализация принципа плюрализма в развитии образования осуществляется через унификацию учебных программ и документов об их прохождении и успешности ...полностью>>
'Методические рекомендации'
В ОБРАЗОВАТЕЛЬНЫХ УЧРЕЖДЕНИЯХ ЗАПАДНОГО ОКРУЖНОГО УПРАВЛЕНИЯ ОБРАЗОВАНИЯ ДЕПАРТАМЕНТА ОБРАЗОВАНИЯ ГОРОДА МОСКВЫ, ПОСВЯЩЁННЫХ ПРАЗДНОВАНИЮ 200-ЛЕТИЯ ПО...полностью>>
'Документ'
Когда я начал писать юмористические стихи, взял себе псевдоним. Сначала перевел имена – «Чарльз Лютвидж» - на латинский язык, получилось – «Каролюс Лю...полностью>>
'Конкурс'
Настоящее Положение определяет порядок и организацию проведения республиканского конкурса профессионального мастерства обучающихся учреждений начально...полностью>>

Главная > Программа курса

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

Программа курса "Дискретная математика"

Теория дискретных множеств

Множества. Операции над множествами. Булеан. Свойства операций над подмножествами. Представление множеств и реализация операций над ними в ЭВМ. Отображения, функции. Представление функций в ЭВМ. Операции. Отношения и их свойства. Представление отношений в ЭВМ. Отношения эквивалентности. Отношения порядка. Замыкание отношений.

Функции алгебры логики

Алгебры, подалгебры, морфизмы. Основные определения и свойства. Определение и основные свойства булевых алгебр. Нормированные булевы алгебры. Алгебра логики. Элементарные булевы функции (функции алгебры логики). Формулы. Реализация функций формулами. Принцип двойственности. Нормальные формы. Представление булевых функций полиномом Жигалкина И.И. Замкнутые классы булевых функций. Полнота множества булевых функций. Минимизация булевых функций. Упрощение дизъюнктивной нормальной формы (ДНФ). Тупиковые ДНФ. Синтез схем из функциональных элементов. Оптимальный по порядку метод синтеза схем из функциональных элементов (метод К. Шеннона). Асимптотически наилучший метод синтеза схем из функциональных элементов (метод О.Б.Лупанова).

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

Графы. Виды графов. Изоморфизм графов. Подграфы, маршруты, цепи, циклы. Представление графов в ЭВМ. Матрицы смежностей, инциденций. Связность графов. Компоненты связности. Операции над графами. Планарные графы. Критерии планарности. Сети. Потоки в сетях. Теорема Форда и Фалкерсона. Алгоритм нахождения максимального потока, основанный на теореме Форда и Фалкерсона. Деревья. Ориентированные, упорядоченные и бинарные деревья. Свойства деревьев. Представления деревьев в ЭВМ. Нахождение кратчайшего пути в графе. Фундаментальные циклы и разрезы. Эйлеровы циклы. Гамильтоновы циклы.

Теория кодирования

Алфавитное кодирование. Неравенство Макмиллана. Кодирование с минимальной избыточностью. Помехоустойчивое кодирование. Код Хемминга для исправления одного замещения. Сжатие данных. Алгоритм Лемпела-Зива.

Экзаменационные вопросы к учебному курсу "Дискретная математика"

(2 семестр 2001 г.)

  1. Множества. Операции над множествами. Примеры [1,2,3].

  2. Булеан. Свойства операций над подмножествами. Примеры [1,2,3].

  3. Представление множеств и реализация операций над ними в ЭВМ [1,2,3].

  4. Отображения, функции. Представление функций в ЭВМ [1,2,3].

  5. Операции. Примеры [1,2,3].

  6. Отношения и их свойства. Примеры [1,2,3].

  7. Представление отношений в ЭВМ [1,2,3].

  8. Отношения эквивалентности. Примеры [1,2,3].

  9. Отношения порядка. Примеры [1,2,3].

  10. Замыкание отношений. Примеры [1,2,3].

  11. Алгебры, подалгебры, морфизмы. Основные определения и свойства Примеры [1,2,3].

  12. Определение и основные свойства булевых алгебр. Примеры [1,2,3].

  13. Нормированные булевы алгебры [1,2,3].

  14. Алгебра логики. Элементарные булевы функции (функции алгебры логики) [1,2,3,4].

  15. Формулы. Реализация функций формулами. Примеры [1,2,3,4].

  16. Принцип двойственности. Примеры применения принципа [1,2,3,4].

  17. Нормальные формы. Примеры [1,2,3,4].

  18. Представление булевых функций полиномом Жигалкина И.И. Примеры [1,2,3,4].

  19. Замкнутые классы булевых функций. Примеры [1,2,3,4].

  20. Полнота множества булевых функций. Примеры [1,2,3,4].

  21. Минимизация булевых функций. Примеры [1,2,3,4].

  22. Упрощение дизъюнктивной нормальной формы (ДНФ), тупиковые ДНФ. Примеры [1,2,3,4].

  23. Синтез схем из функциональных элементов. Примеры [1,4].

  24. Оптимальный по порядку метод синтеза схем из функциональных элементов (метод К. Шеннона). Пример [1,4].

  25. Асимптотически наилучший метод синтеза схем из функциональных элементов (метод О.Б.Лупанова). Пример [1,4].

  26. Графы. Виды графов. Изоморфизм графов. Примеры [1,3]

  27. Подграфы, маршруты, цепи, циклы. Примеры [1,3]

  28. Представление графов в ЭВМ. Матрицы смежностей, инциденций. Примеры [1,3]

  29. Связность графов. Компоненты связности. Примеры [1,3]

  30. Операции над графами. Примеры [1,3]

  31. Планарные графы. Критерии планарности. Примеры [1,3]

  32. Сети. Потоки в сетях. Теорема Форда и Фалкерсона. Примеры [1,3]

  33. Алгоритм нахождения максимального потока, основанный на теореме Форда и Фалкерсона. Пример [1,3]

  34. Деревья. Ориентированные, упорядоченные и бинарные деревья. Свойства деревьев. Примеры [1,3]

  35. Представления деревьев в ЭВМ. Примеры [1,3]

  36. Нахождение кратчайшего пути в графе. Примеры [1,3]

  37. Фундаментальные циклы и разрезы. Примеры [1,3]

  38. Эйлеровы циклы. Примеры [1,3]

  39. Гамильтоновы циклы. Примеры [1,3]

  40. Алфавитное кодирование. Неравенство Макмиллана. Примеры [1,3,4]

  41. Кодирование с минимальной избыточностью. Примеры [1,3,4]

  42. Помехоустойчивое кодирование. Примеры [1,3,4]

  43. Код Хемминга для исправления одного замещения. Пример [1,3,4]

  44. Сжатие данных. Алгоритм Лемпела-Зива. Примеры [1,3]

Литература

  1. Конспект лекций

  2. В.И. Городецкий "Прикладная алгебра и дискретная математика. ч.1 М., 1983 г.

  3. Новиков Ф.А. "Дискретная математика для программистов", СПб, 2000 г.

  4. C.В. Яблонский "Введение в дискретную математику" М., Наука, 1988 г.

Экзаменационные билеты к учебному курсу "Дискретная математика"

(2 семестр 2001 г.)

Билет № 1

1. Множества. Операции над множествами. Примеры.

2. Оптимальный по порядку метод синтеза схем из функциональных элементов (метод К. Шеннона). Пример.

Билет № 2

1. Булеан. Свойства операций над подмножествами. Примеры

2. Асимптотически наилучший метод синтеза схем из функциональных элементов (метод О.Б.Лупанова). Пример.

Билет № 3

1. Представление множеств и реализация операций над ними в ЭВМ. Пример.

2. Алфавитное кодирование. Неравенство Макмиллана. Примеры.

Билет № 4

1. Отображения, функции. Представление функций в ЭВМ. Примеры.

2. Кодирование с минимальной избыточностью. Примеры.

Билет № 5

1. Операции. Примеры.

2. Код Хемминга для исправления одного замещения. Пример.

Билет № 6

1. Отношения и их свойства. Примеры.

2. Сжатие данных. Алгоритм Лемпела-Зива. Примеры.

Билет № 7

1. Представление отношений в ЭВМ. Примеры.

2. Планарные графы. Критерии планарности. Примеры.

Билет № 8

1. Отношения эквивалентности. Примеры.

2. Помехоустойчивое кодирование. Примеры.

Билет № 9

1. Отношения порядка. Примеры.

2. Синтез схем из функциональных элементов. Примеры.

Билет № 10

1. Замыкание отношений. Примеры.

2. Представление графов в ЭВМ. Матрицы смежностей, инциденций. Примеры.

Билет № 11

1. Алгебры, подалгебры, морфизмы. Основные определения и свойства Примеры.

2. Представления деревьев в ЭВМ. Примеры.

Билет № 12

1. Определение и основные свойства булевых алгебр. Примеры.

2. Связность графов. Компоненты связности. Примеры.

Билет № 13

1. Нормированные булевы алгебры. Примеры.

2. Операции над графами. Примеры.

Билет № 14

1. Алгебра логики. Элементарные булевы функции (функции алгебры логики).

2. Сети. Потоки в сетях. Теорема Форда и Фалкерсона. Примеры.

Билет № 15

1. Формулы. Реализация функций формулами. Примеры.

2. Алгоритм нахождения максимального потока, основанный на теореме Форда и Фалкерсона. Пример.

Билет № 16

1. Принцип двойственности. Примеры применения принципа.

2. Деревья. Ориентированные, упорядоченные и бинарные деревья. Свойства деревьев. Примеры.

Билет № 17

1. Нормальные формы. Примеры.

2. Нахождение кратчайшего пути в графе. Примеры.

Билет № 18

1. Представление булевых функций полиномом Жигалкина И.И. Примеры.

2. Фундаментальные циклы и разрезы. Примеры.

Билет № 19

1. Замкнутые классы булевых функций. Примеры.

2. Гамильтоновы циклы. Примеры.

Билет № 20

1. Полнота множества булевых функций. Примеры.

2. Эйлеровы циклы. Примеры.

Билет № 21

1. Минимизация булевых функций. Примеры.

2. Подграфы, маршруты, цепи, циклы. Примеры.

Билет № 22

1. Упрощение дизъюнктивной нормальной формы (ДНФ), тупиковые ДНФ. Примеры.

2. Графы. Виды графов. Изоморфизм графов. Примеры.



Похожие документы:

  1. Программа курса лекций «дискретная математика»

    Программа курса
    Программа курса лекций «ДИСКРЕТНАЯ МАТЕМАТИКА» Лектор: ГАШКОВ С.Б. 1. Булевы функции и элементарная ... ЛИТЕРАТУРА: Яблонский С.В. Введение в дискретную математику (Начиная со второго издания). Дискретная математика и математические вопросы кибернетики ...
  2. Программа дисциплины «Дискретная математика» (1)

    Программа дисциплины
    ... Факультет прикладной математики и кибернетики Программа дисциплины «Дискретная математика» для ... Задачи и упражнения по курсу дискретной математики. – М.: Физматлит, 2005. Галкина В.А. Дискретная математика: комбинаторные методы оптимизации ...
  3. Программа дисциплины «Дискретная математика» (2)

    Программа дисциплины
    ... Факультет прикладной математики и кибернетики Программа дисциплины «Дискретная математика» для ... Задачи и упражнения по курсу дискретной математики. – М.: Физматлит, 2005. Галкина В.А. Дискретная математика: комбинаторные методы оптимизации ...
  4. Программа дисциплины "Дискретная математика" для направления 521600 Экономика

    Программа дисциплины
    ... 18/18 III. Содержание программы Раздел 1. Комбинаторные методы дискретной математики. Тема 1.1. История развития ... . 2. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. - М.: Наука, 1992. 3. Ежов И.И., Скороход А.В., ...
  5. Программа курса "Дифференциальные уравнения"

    Программа курса
    Программа курса "Дифференциальные уравнения" Направление Прикладная математика и информатика ЦЕЛИ И ЗАДАЧИ Цель курса – ... . Линейные неоднородные системы уравнений с дискретным временем и рекуррентные последовательности с неоднородностью ...

Другие похожие документы..