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



Скачать 17.13 Kb.
Дата08.10.2012
Размер17.13 Kb.
ТипПрограмма курса
ПРОГРАММА КУРСА "ДИСКРЕТНАЯ МАТЕМАТИКА".

лектор - Даугавет А. И.

(36 часов)

1. ДИСКРЕТНЫЕ МНОЖЕСТВА. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ. (4 ч)

Дискретные множества. Характеристический век­тор множества и операции над множествами. Мощность прямого произведения множеств. Число размещений, пе­рестановок и сочетаний, число разбиений на множества заданной мощ­ности.
2. ОСНОВНЫЕ ПОНЯТИЯ БУЛЕВОЙ АЛГЕБРЫ. (4 ч)

Булевские переменные и функции. Операции Булевой алгебры и их связь с теорети­ко-множественными операциями. Эквивалентные формулы, основные эквивалентности. Дизъюнктивная и конъюнктивная нормальные формы формул и их построение по таблично заданной функции.

3. ТЕОРИЯ ИНФОРМАЦИИ И МЕТОДЫ КОДИРОВАНИЯ. (8 ч)

Основные понятия дискретной теории вероятностей. Понятие "ко­личество информации". Энтропия случайного опыта, случай максималь­ной энтропии. Задача кодирования информации, равномерный и нерав­номерный код, организация блоков. Коды Шеннона-Фано и Хафмана. Методы выявления ошибок при передаче информации, код Хэминга.
4. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ. (6 ч)

Граф, частичный граф и подграф. Матрицы инциденций и смежнос­ти. Путь и цепь, контур и цикл, понятие связности графа. Дерево. Опорное дерево связного графа. Эквивалентные определения дерева. Вполне связный граф и иерархическое дерево. Эйле­ровы и Гамильтоновы цепи и циклы.
5. НЕКОТОРЫЕ АЛГОРИТМЫ ОПТИМИЗАЦИИ. (6 ч)

Понятия алгоритма и сложности алгоритма. Дерево кратчайших путей. Кратчайшее опорное дерево. Метод ветвей и границ: задачи о коммивояжере и о наилучшем раскрое.
6. МЕТОДЫ ПОИСКА И СОРТИРОВКИ. (8 ч)

Постановка задачи поиска и оценка сложности. После­довательный и бинарный поиск. Поиск по двоичному дереву. Выравненное и сбалансированное дерево. Постановка задачи сортировки и оценка сложности. Сорти­ровка вставками: метод простых вставок и метод Шелла. Быстрая сор­тировка. Пирамидальная сортировка.
ЛИТЕРАТУРА

1. Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику. – М.: Мир, 1963.

2. Феллер В. Введение в теорию вероятностей и ее приложения. – Т.1 – М.: Мир, 1984.

3. Яглом А. М., Яглом И. М. Вероятность и информация – М.: Наука, 1973.

4. Романовский И. В. Алгоритмы решения экстремальных задач. – М.: Наука, 1977.

5. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.

6. Кнут Д. Искусство программирования для ЭВМ. T.3 – М., Наука, 1971.

Похожие:

Программа курса \"дискретная математика\" iconПрограмма дисциплины Дискретная математика для социологов для направления 040200. 62 Социология подготовки бакалавра
Требования к студентам: Учебная дисциплина “Дискретная математика для социологов” (4-й и 5-й модули учебного плана 1-го курса факультета...
Программа курса \"дискретная математика\" iconПрограмма дисциплины «Дискретная математика»
...
Программа курса \"дискретная математика\" iconПрограмма дисциплины Дискретная математика для социологов для направления 040200. 62 «Социология» подготовки бакалавра Автор: Дагаев Д. А
Курс «Дискретная математика для социологов» предназначен для студентов 1-го курса бакалавриата факультета социологии. Он является...
Программа курса \"дискретная математика\" iconПрограмма дисциплины «Дискретная математика и теория алгоритмов»
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Программа курса \"дискретная математика\" iconПрограмма дисциплины «Дискретная математика и теория алгоритмов»
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Программа курса \"дискретная математика\" iconПрограмма дисциплины «Дискретная математика и теория алгоритмов»
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Программа курса \"дискретная математика\" iconРабочей программы дисциплины дискретная математика
Дискретная математика и математическая логика входят в цикл профессиональных дисциплин в базовой части. Для их успешного изучения...
Программа курса \"дискретная математика\" iconРабочая программа дисциплины дискретная математика направление подготовки 230700 Прикладная информатика Квалификация выпускника
Целями освоения дисциплины «Дискретная математика» являются получение теоретических знаний по основам дискретной математики
Программа курса \"дискретная математика\" iconУчебная программа Дисциплины б2 «Дискретная математика» по направлению 010300 «Фундаментальная информатика и информационные технологии»
Целью преподавания дисциплины «Дискретная математика» является подготовка специалистов к деятельности в сфере разработки, исследования...
Программа курса \"дискретная математика\" iconУчебная программа Дисциплины б4 «Дискретная математика» по специальности 090302 «Информационная безопасность телекоммуникационных систем»
Целью преподавания дисциплины «Дискретная математика» является подготовка специалистов к деятельности в сфере разработки, исследования...
Разместите кнопку на своём сайте:
ru.convdocs.org


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