Чиспияков Сергей Валентинович лекция

Вид материала

Лекция

Подобный материал:

• Чиспияков Сергей Валентинович лекция, 46.08kb.
• Внастоящей работе проведен анализ зависимостей затухающих акустических колебаний отливок, 47.5kb.
• Азар'єв Віктор Валентинович, 138.15kb.
• Сидоров Сергей Владимирович Планы лекций Введение в профессионально-педагогическую, 19.81kb.
• Петр Валентинович Турчин один из сильнейших специалистов в мире по популяционной динамике,, 156.73kb.
• Владимир Валентинович «Заслуженный учитель Республики Татарстан», 630.73kb.
• Градобоев Валерий Валентинович Москва 2008 программа курса, 1080.91kb.
• Вялкина Светлана Семеновна (г. Хабаровск) > Лясковская Наталья Станиславовна (г. Южно-Сахалинск), 284.16kb.
• Контактная информация: Рохин Валерий Валентинович, 236.5kb.
• Родионов Алексей Владимирович Начальник цикла №52 («Ракетно-космическая оборона») п/п-к, 38.06kb.

Утверждаю

зав. кафедрой алгебры

___________________

«___»_________2009г.


Брянский государственный университет им. Академика И.Г. Петровского

Учебная программа

По курсу «Основы дискретной математики», для студентов ФМФ (2 курс 3 семестр, 2009-2010 учебный год).

Общий объем курса 104 часа, из них 52 часа лекций, 52 часа практических занятий.

Программу разработал Чиспияков Сергей Валентинович.

Лекция 1.	Множество. Операции над множествами. Равные множества. Подмножество. Свойства операций над множествами. Метод встречных включений.	Практическое занятие 1.	Множества. Метод встречных включений. Свойства операций над множествами.
Лекция 2.	Перестановки. Размещения. Сочетания. Свойства. Перестановки с повторением. Размещения с повторением. Сочетания с повторением. Свойства.	Практическое занятие 2.	Комбинаторные конфигурации без повторений и с повторениями.
Лекция 3.	Событие. Вероятность события. Произведение и сумма событий. Формула Бернулли. Формула Байеса.	Практическое занятие 3.	Вероятность события. Вероятность произведения и суммы событий. Формула Бернулли. Формула Байеса.
Лекция 4.	Дискретная случайная величина. Закон распределения ДСВ. Числовые характеристики ДСВ.	Практическое занятие 4.	ДСВ. Закон ДСВ. Числовые характеристики ДСВ.
Лекция 5.	Прямое произведение множеств. Бинарное отношение. Свойства. Отношение эквивалентности. Отношение порядка.	Практическое занятие 5.	Свойства бинарных отношений. Отношение порядка. Отношение эквивалентности.
Лекция 6.	Граф. Виды графов. Изоморфизм графов. Представление графов. Матрицы графов. Обходы графов. Операции над графами.	Практическое занятие 6.	Изоморфизм графов. Представление графов. Поиск в глубину и ширину.
Лекция 7.	Функциональное отношение. Область и кообласть. Отображение. Инъективное и сурьективное отображения. Биекция.	Практическое занятие 7.	Функция. Свойства.
Лекция 8.	Композиция функций. Тождественное отображение. Обратное отображение. Теорема об обратной функции.	Практическое занятие 8.	Композиция функций. Обратная функция.
Лекция 9.	Булева алгебра. Изоморфизм булевых алгебр. Двойственная булева алгебра.	Практическое занятие 9.	Алгебраическая операция. Группа.
Лекция 10.	Алгебраическая операция. Группоид, полугруппа, моноид, группа.	Практическое занятие 10.	Метод математической индукции.
Лекция 11.	Полукольцо. Аксиомы Пеано. Полукольцо натуральных чисел. Метод математической индукции.	Практическое занятие 11.	Контрольная работа № 1.
Лекция 12.	Кольцо. Подкольцо. Критерий подкольца. Свойства колец.	Практическое занятие 12.	Кольцо. Подкольцо. Критерий паодкольца.
Лекция 13.	Кольцо целых чисел. Отношение делимости. Свойства. НОД. НОК. Алгоритм евклида.	Практическое занятие 13.	Отношение делимости. НОД. НОК. Алгоритм Евклида.
Лекция 14.	Линейное представление НОД. Сравнения. Свойства сравнений.	Практическое занятие 14.	Линейное представление НОД.
Лекция 15.	Решения сравнений первой степени. Классы вычетов.	Практическое занятие 15.	Решения сравнений первой степени. Классы вычетов.
Лекция 16.	Поле. Подполе. Критерий подполя. Свойства полей. Поле {0,1}.	Практическое занятие 16.	Поле. Подполе. Критерий подполя.
Лекция 17.	Высказывание. Операции над высказываниями. Формулы АВ. Булевы функции. Нормальные формы формул АВ.	Практическое занятие 17.	Формулы АВ. Булевы функции. Нормальные формулы.
Лекция 18.	СДНФ, СКНФ. Полиномы Жегалкина. Представление булевой функции полиномом Жегалкина.	Практическое занятие 18.	СДНФ. СКНФ. Полиномы Жегалкина.
Лекция 19.	Классы булевых функций. Полные системы булевых функций. Теорема Поста. k-значные логики.	Практическое занятие 19.	Полные системы булевых функций. Теорема Поста.
Лекция 20.	Предикаты. Операции. Кванторы. Предикатные формулы.	Практическое занятие 20.	Предикаты. Кванторы. Предикатные формулы.
Лекция 21.	Числа Фибоначчи. Рекуррентные соотношение. Решение рекуррентных соотношений первого порядка.	Практическое занятие 21.	Решения рекуррентных соотношений первого порядка.
Лекция 22.	Деревья. Характеристическая теорема о деревьях. Код Прюфера.	Практическое занятие 22.	Деревья. Код Прюфера.
Лекция 23.	Сети. Поток. Максимальный поток. Теорема Форда-Фалкерсона.	Практическое занятие 23.	Сети. Поток. Алгоритм нахождения максимального потока.
Лекция 24.	Алфавитное кодирование. Разделимые схемы. Неравенство Макмиллана.	Практическое занятие 24.	Разделимые схемы алфавитного кодирования. Неравенство Макмиллана.
Лекция 25.	Самокорректирующиеся коды. Код Хемминга. БЧХ-коды.	Практическое занятие 25.	Код Хемминга.
Лекция 26.	Оптимальное кодирование. Алгоритм Хаффмана. Адаптивное кодирование. Алгоритм LZW.	Практическое занятие 26.	Контрольная работа № 2.

Рекомендованная литература:

1. 
   Куликов Л.Я. Алгебра и теория чисел. М.: Высшая школа, 1979. -559 с.
   
2. Шнеперман Л.Б. Сборник задач по алгебре и теории чисел. Мн.: Высшая школа, 1982. -223 с.
   
3. Фадеев Д.К., Соминский И.С. Задачи по высшей алгебре. СПб.: Изд. «Лань», 2005. -288с.
   
4. Анищенко А.Г. Методические рекомендации для студентов заочников 4 курса физико-математического факультета. Брянск 1989 г.
   
5. Горбачев В.И., Иноземцева Т.М. Методические рекомендации для студентов заочников 1 курса ФМФ. Брянск 1991.
   
6. Горбачев В.И. Методические рекомендации для студентов заочников 3 курса ФМФ. Брянск 1988.