Факультет математики Рабочая программа дисциплины «Дискретная математика и теория алгоритмов» icon

Факультет математики Рабочая программа дисциплины «Дискретная математика и теория алгоритмов»



НазваниеФакультет математики Рабочая программа дисциплины «Дискретная математика и теория алгоритмов»
Дата конвертации28.07.2012
Размер175.25 Kb.
ТипРабочая программа
скачать >>>

Правительство Российской Федерации

Государственное образовательное бюджетное учреждение

высшего профессионального образования

Государственный университет – Высшая школа экономики
Факультет математики



Рабочая программа дисциплины


«Дискретная математика и теория алгоритмов»



Направление:

010100.62 «Математика»

Подготовка:

бакалавр

Форма обучения:

очная




Авторы программы:

проф. Артамкин И.В.,




проф. Ландо С.К.




Рекомендована секцией УМС




Одобрена на заседании

по математике




кафедры дискретной математики

Председатель




Зав.кафедрой, проф.


___________________________С.К.Ландо





_________________________С.К. Ландо

«_____» ______________________2009 г.




«___» ______________________2009 г.










Утверждена УС







факультета математики







Ученый секретарь доцент








_________________________Ю.М.Бурман







«___» ________________________2009 г.









Москва

2009

Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И.В., Ландо С.К.; ГУ-ВШЭ.–Москва.–2009.–11 с.


Рабочая программа составлена на основе государственных требований к минимуму содержания и уровню подготовки бакалавров Государственного образовательного стандарта высшего профессионального образования по направлению 010100 «Математика».


Рабочая программа предназначена для методического обеспечения дисциплины основной образовательной программы по направлению 010100 «Математика».


Составители: д.ф.-м.н. И.В. Артамкин (artamkin@hse.ru)

д. ф.-м. н. С.К.Ландо (lando@hse.ru)



©

Артамкин И.В., Ландо С.К. 2009.

©

Государственный университет–Высшая школа экономики, 2009.


Пояснительная записка


Авторы программы: доктор физико-математических наук И.В. Артамкин, доктор физико-математических наук С.К.Ландо.


Требования к студентам: дисциплина изучается на первом курсе, так что требуется только владение алгеброй и геометрией в объеме школьной программы; для материала третьего модуля требуется курс алгебры 1 и 2 модулей.


Аннотация: Дисциплина «Дискретная математика и теория алгоритмов» предназначена для подготовки бакалавров по направлению 010100.62.


Цели и задачи изучения дисциплины, ее место в учебном процессе


1.1. Цель изучения дисциплины.

Получение:

– представления об основных методах и результатах дискретной математики;

– знания об основных результатах и алгоритмах комбинаторики, теории чисел, теории графов, теории кодирования и других разделов дискретной математики;

– умения решать различные дискретные задачи средствами комбинаторики и теории графов;

– опыта использования, применения изучаемых методов к исследованию и решению конкретных задач.


1.2. Задачи изучения дисциплины: овладение основными средствами дискретной математики – применение комбинаторики, теории чисел, теории графов к решению различных задач.


1.3. Перечень дисциплин и разделов, знание которых требуется для изучения данной дисциплины: материал школьной программы по математике; для второго семестра – курс алгебры первого семестра.


Тематический план учебной дисциплины





Название темы


Всего часов по дисциплине

В том числе аудиторных

Самостоятельная работа

Всего

Лекции

Семинары




3 модуль

80

28

14

14

52



Комбинаторика: выборки, перестановки, сочетания, перестановки с повторениями; сочетания с повторениями; биномиальные коэффициенты, их свойства; биномиальная теорема; полиномиальная теорема; формула включения и исключения.

12

4

2

2

10



Производящие функции. Вычисления с формальными степенными рядами. Рациональные производящие функции и линейные рекуррентные соотношения с постоянными коэффициентами.

8

2

2

2

8



Свойства делимости целых чисел. Простые числа. Решето Эратосфена. Теорема Евклида о бесконечности множества простых чисел. Основная теорема арифметики о разложении целых чисел на простые сомножители. Наибольший общий делитель и наименьшее общее кратное. Некоторые частные случаи теоремы Дирихле о бесконечности множества простых чисел в арифметической прогрессии.

8

4

2

2

6



Арифметические функции; целая и дробная часть числа; разложение числа n! на простые множители; суммы, распространенные на делители числа; мультипликативные функции; функция Эйлера и ее свойства; сумма делителей и число делителей; оценки Чебышева для функции числа простых чисел, не превосходящих x.

8

2

2

2

8



Цепные дроби; конечные цепные дроби; подходящие дроби и их свойства; нахождение наибольшего общего делителя с помощью цепных дробей; бесконечные цепные дроби; разложение действительных чисел в цепные дроби; приближение действительных чисел рациональными числами; подходящие дроби как наилучшие приближения; признак иррациональности числа; иррациональность числа «е»; теорема Лагранжа о разложении квадратичных иррациональностей в цепные дроби.

14

6

3

3

10



Числовые сравнения: сравнения и их основные свойства; вычеты и классы вычетов по модулю m; кольца классов вычетов; полная система вычетов; приведенная система вычетов; теорема Эйлера и Ферма; сравнения первой степени: сравнения с одним неизвестным; равносильные сравнения; решения сравнения; сравнения первой степени; теорема о существовании решений; простейшие приемы решений; решение сравнений с помощью цепных дробей; системы сравнений, их решения; теоремы о решении систем сравнений первой степени; сравнения n-й степени: сравнения n-й степени по простому модулю; теоремы о равносильности сравнений; теорема о числе решений сравнения; теорема Вильсона; сравнения n-ой степени по составному модулю; сведение сравнения по составному модулю к системе сравнений по простому модулю; сравнения второй степени: сведение сравнений второй степени к двучленному сравнению; двучленные сравнения по простому модулю.

14

6

3

3

10




4 модуль

82

28

14

14

54



Графы: основные понятия; способы представления графов. Изоморфизм, гомеоморфизм и гомотопия графов; основные инварианты графов. Деревья и их свойства. Остовное поддерево. Простейшие алгоритмы теории графов. Эйлеровы и гамильтоновы графы. Перечислительные задачи теории графов. Теорема Кэли. Формула Эйлера для плоских графов.

20

6

3

3

12



Циклы и разрезы. Граничный и кограничный оператор. Гомологии и когомологии графа. Двойственность. Циклы и разрезы по модулю два. Базисы циклов и разрезов, связанные с остовным поддеревом. Матрицы циклов и разрезов. Теорема Коши-Бине. Теорема Кирхгофа о числе остовных поддеревьев. Остовные поддеревья полного графа и теорема Кэли. Элементы теории матроидов. Понятие матроида. Двойственность. Графические и кографические матроиды. Линейные матроиды. Представимость. Матроид Фано.

22

8

3

3

10



Планарные графы. Теорема Эйлера. Раскраски планарных графов. Проблема четырех красок. Критерии планарности. Теорема Понтрягина-Куратовского. Укладки графов и род графа.

10

4

2

2

8



Потоки в сетях: теорема Форда – Фалкерсона; алгоритм Форда – Фалкерсона.

Связность и маршруты на графах. Числа связности графа. Разделяющие множества. Реберная и вершинная теоремы Менгера. Двудольные графы; паросочетания. Совершенное паросочетание. Теорема Холла. Венгерский алгоритм построения совершенного паросочетания. Задача об оптимальном назначении.

20

6

2

2

8



Вложение графа в поверхность. Ленточные графы. Вычисление рода поверхности. Двойственный граф. Примеры. Дискретный оператор Лапласа. Представление классов гомологий гармоническими циклами.

14

4

2

2

8



Производящие функции в комбинаторике и теории графов. Числа Каталана. Явное вычисление производящих функций для различных типов графов.

12

4

2

2

8




Итого:

162

56

30

26

106


Базовые учебники


1. Стенли Р. Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции. Перев. с англ.–М.: Мир, 2005.

2. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике: Учеб. пособие для вузов –М.: Физматлит, 2006.

3. Виноградов И.М. Основы теории чисел.– Изд.11–е, стер.–Спб.:Лань, 2006.

4. Ландо С.К. Лекции о производящих функциях. – Изд. 3–е.– М.: МЦНМО, 2007.

5. Харари Ф. Теория графов.–М.: УРСС, 2003.

6. Вильямс Дж. Дискретная математика и комбинаторика. – Вильямс, 2006.

7. Дональд Кнут, Роналд Грэхем, Орен Паташник. Конкретная математика. Основания информатики.–М.:Мир; Бином. Лаборатория знаний, 2006.


Дополнительная литература


1. Lando S.K., Zvonkin A.K. Graphs on Surfaces and Their Applications.– Berlin:Springer, 2004.


Формы контроля


Текущий контроль – решение задач на семинарских занятиях.

Промежуточный контроль: 2 контрольные работы.

Итоговый контроль: экзамен (4-й модуль).


Формула для вычисления итоговой оценки


30% оценки за домашние задания + 30% оценки за контрольную работу + 40% оценки за экзамен.


Содержание программы


Тема 1. Комбинаторика.

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


Тема 2. Производящие функции.

Вычисления с формальными степенными рядами. Рациональные производящие функции и линейные рекуррентные соотношения с постоянными коэффициентами.


Тема 3. Свойства делимости целых чисел.

Простые числа.Решето Эратосфена. Теорема Евклида о бесконечности множества простых чисел. Основная теорема арифметики о разложении целых чисел на простые сомножители. Наибольший общий делитель и наименьшее общее кратное. Некоторые частные случаи теоремы Дирихле о бесконечности множества простых чисел в арифметической прогрессии.


Тема 4. Арифметические функции.

Целая и дробная часть числа; разложение числа n! на простые множители; суммы, распространенные на делители числа; мультипликативные функции; функция Эйлера и ее свойства; сумма делителей и число делителей; оценки Чебышева для функции числа простых чисел, не превосходящих x.

Тема 5. Цепные дроби; конечные цепные дроби; подходящие дроби и их свойства; нахождение наибольшего общего делителя с помощью цепных дробей; бесконечные цепные дроби; разложение действительных чисел в цепные дроби; приближение действительных чисел рациональными числами; подходящие дроби как наилучшие приближения; признак иррациональности числа; иррациональность числа «е»; теорема Лагранжа о разложении квадратичных иррациональностей в цепные дроби.


Тема 6. Числовые сравнения.

Сравнения и их основные свойства; вычеты и классы вычетов по модулю m; кольца классов вычетов; полная система вычетов; приведенная система вычетов; теорема Эйлера и Ферма; сравнения первой степени: сравнения с одним неизвестным; равносильные сравнения; решения сравнения; сравнения первой степени; теорема о существовании решений; простейшие приемы решений; решение сравнений с помощью цепных дробей; системы сравнений, их решения; теоремы о решении систем сравнений первой степени; сравнения n-й степени: сравнения n-й степени по простому модулю; теоремы о равносильности сравнений; теорема о числе решений сравнения; теорема Вильсона; сравнения n-ой степени по составному модулю; сведение сравнения по составному модулю к системе сравнений по простому модулю; сравнения второй степени: сведение сравнений второй степени к двучленному сравнению; двучленные сравнения по простому модулю.


Тема 7. Графы.

Основные понятия; способы представления графов. Изоморфизм, гомеоморфизм и гомотопия графов; основные инварианты графов. Деревья и их свойства. Остовное поддерево. Простейшие алгоритмы теории графов. Эйлеровы и гамильтоновы графы. Перечислительные задачи теории графов. Теорема Кэли. Формула Эйлера для плоских графов.


Тема 8. Циклы и разрезы.

Граничный и кограничный оператор. Гомологии и когомологии графа. Двойственность. Циклы и разрезы по модулю два. Базисы циклов и разрезов, связанные с остовным поддеревом. Матрицы циклов и разрезов. Теорема Коши-Бине. Теорема Кирхгофа о числе остовных поддеревьев. Остовные поддеревья полного графа и теорема Кэли. Элементы теории матроидов. Понятие матроида. Двойственность. Графические и кографические матроиды. Линейные матроиды. Представимость. Матроид Фано.


Тема 9. Планарные графы.

Теорема Эйлера. Раскраски планарных графов. Проблема четырех красок. Критерии планарности. Теорема Понтрягина-Куратовского. Укладки графов и род графа.


Тема 10. Потоки в сетях.

Теорема Форда – Фалкерсона; алгоритм Форда – Фалкерсона.

Связность и маршруты на графах. Числа связности графа. Разделяющие множества. Реберная и вершинная теоремы Менгера. Двудольные графы; паросочетания. Совершенное паросочетание. Теорема Холла. Венгерский алгоритм построения совершенного паросочетания. Задача об оптимальном назначении.


Тема 11. Вложение графа в поверхность.

Ленточные графы. Вычисление рода поверхности. Двойственный граф. Примеры. Дискретный оператор Лапласа. Представление классов гомологий гармоническими циклами.


Тема 12. Производящие функции в комбинаторике и теории графов.

Числа Каталана. Явное вычисление производящих функций для различных типов графов.


Образцы заданий по различным формам контроля


Цикл 1. Комбинаторика.

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


Цикл 2. Производящие функции.

Вычисления с формальными степенными рядами. Рациональные производящие функции и линейные рекуррентные соотношения с постоянными коэффициентами.


Цикл 3. Свойства делимости целых чисел.

Простые числа.Решето Эратосфена. Теорема Евклида о бесконечности множества простых чисел. Основная теорема арифметики о разложении целых чисел на простые сомножители. Наибольший общий делитель и наименьшее общее кратное. Некоторые частные случаи теоремы Дирихле о бесконечности множества простых чисел в арифметической прогрессии.


Цикл 4. Арифметические функции.

Целая и дробная часть числа; разложение числа n! на простые множители; суммы, распространенные на делители числа; мультипликативные функции; функция Эйлера и ее свойства; сумма делителей и число делителей; оценки Чебышева для функции числа простых чисел, не превосходящих x.


Цикл 5. Цепные дроби; конечные цепные дроби; подходящие дроби и их свойства; нахождение наибольшего общего делителя с помощью цепных дробей; бесконечные цепные дроби; разложение действительных чисел в цепные дроби; приближение действительных чисел рациональными числами; подходящие дроби как наилучшие приближения; признак иррациональности числа; иррациональность числа «е»; теорема Лагранжа о разложении квадратичных иррациональностей в цепные дроби.


Цикл 6. Числовые сравнения.

Сравнения и их основные свойства; вычеты и классы вычетов по модулю m; кольца классов вычетов; полная система вычетов; приведенная система вычетов; теорема Эйлера и Ферма; сравнения первой степени: сравнения с одним неизвестным; равносильные сравнения; решения сравнения; сравнения первой степени; теорема о существовании решений; простейшие приемы решений; решение сравнений с помощью цепных дробей; системы сравнений, их решения; теоремы о решении систем сравнений первой степени; сравнения n-й степени: сравнения n-й степени по простому модулю; теоремы о равносильности сравнений; теорема о числе решений сравнения; теорема Вильсона; сравнения n-ой степени по составному модулю; сведение сравнения по составному модулю к системе сравнений по простому модулю; сравнения второй степени: сведение сравнений второй степени к двучленному сравнению; двучленные сравнения по простому модулю.


Цикл 7. Графы.

Основные понятия; способы представления графов. Изоморфизм, гомеоморфизм и гомотопия графов; основные инварианты графов. Деревья и их свойства. Остовное поддерево. Простейшие алгоритмы теории графов. Эйлеровы и гамильтоновы графы. Перечислительные задачи теории графов. Теорема Кэли. Формула Эйлера для плоских графов.


Цикл 8. Циклы и разрезы.

Граничный и кограничный оператор. Гомологии и когомологии графа. Двойственность. Циклы и разрезы по модулю два. Базисы циклов и разрезов, связанные с остовным поддеревом. Матрицы циклов и разрезов. Теорема Коши-Бине. Теорема Кирхгофа о числе остовных поддеревьев. Остовные поддеревья полного графа и теорема Кэли. Элементы теории матроидов. Понятие матроида. Двойственность. Графические и кографические матроиды. Линейные матроиды. Представимость. Матроид Фано.


Цикл 9. Планарные графы.

Теорема Эйлера. Раскраски планарных графов. Проблема четырех красок. Критерии планарности. Теорема Понтрягина-Куратовского. Укладки графов и род графа.


Цикл 10. Потоки в сетях.

Теорема Форда – Фалкерсона; алгоритм Форда – Фалкерсона.

Связность и маршруты на графах. Числа связности графа. Разделяющие множества. Реберная и вершинная теоремы Менгера. Двудольные графы; паросочетания. Совершенное паросочетание. Теорема Холла. Венгерский алгоритм построения совершенного паросочетания. Задача об оптимальном назначении.


Цикл 11. Вложение графа в поверхность.

Ленточные графы. Вычисление рода поверхности. Двойственный граф. Примеры. Дискретный оператор Лапласа. Представление классов гомологий гармоническими циклами.


Цикл 12. Производящие функции в комбинаторике и теории графов.

Числа Каталана. Явное вычисление производящих функций для различных типов графов.


Темы контрольных работ:

  1. Комбинаторика и производящие функции.

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







Авторы программы:




И. В. Артамкин










С.К. Ландо




Нажми чтобы узнать.

Похожие:

Факультет математики Рабочая программа дисциплины «Дискретная математика и теория алгоритмов» iconФакультет математики Рабочая программа дисциплины «Дискретная математика и теория алгоритмов»
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Факультет математики Рабочая программа дисциплины «Дискретная математика и теория алгоритмов» iconРабочая программа дисциплины теория информационных процессов и систем
Пререквизиты: «Информатика», «Математика», «Математическая логика и теория алгоритмов», «Дискретная математика»
Факультет математики Рабочая программа дисциплины «Дискретная математика и теория алгоритмов» iconФакультет математики
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Факультет математики Рабочая программа дисциплины «Дискретная математика и теория алгоритмов» iconРабочая программа дисциплины математическая логика и теория алгоритмов
«Математическая логика и теория алгоритмов» (млта) заключается в формировании у студентов знаний, умений и навыков в области теории...
Факультет математики Рабочая программа дисциплины «Дискретная математика и теория алгоритмов» iconФакультет математики Рабочая программа дисциплины «Теория функций комплексного переменного (тфкп)»
Рабочая программа дисциплины «Теория функций комплексного переменного» [Текст]/Сост. Шварцман О. В.; Гу-вшэ. –Москва.– 2009. – 7...
Факультет математики Рабочая программа дисциплины «Дискретная математика и теория алгоритмов» iconРабочая программа дисциплины методы интеллектуальной обработки и анализа изображений
В для её успешного усвоения необходимы знания по дисциплинам: «Математика» – б3, «Теория вероятностей и математическая статистика»...
Факультет математики Рабочая программа дисциплины «Дискретная математика и теория алгоритмов» iconПрограмма дисциплины «Дискретная математика» для направления 010500. 62 «Прикладная математика и информатика» подготовки бакалавра
Одобрена на заседании кафедры высшей математики на факультете экономики 29. 08. 2011 г
Факультет математики Рабочая программа дисциплины «Дискретная математика и теория алгоритмов» iconРабочая программа дисциплины дискретная математика

Факультет математики Рабочая программа дисциплины «Дискретная математика и теория алгоритмов» iconРабочая программа дисциплины дискретная математика

Факультет математики Рабочая программа дисциплины «Дискретная математика и теория алгоритмов» iconДискретная математика
Дискретная (финитная, конечная) математика – направление математики, изучающее свойства дискретных структур. В этом плане классическая...
Разместите кнопку на своём сайте:
Документы


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