Факультет математики icon

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



НазваниеФакультет математики
Дата конвертации12.08.2012
Размер188 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 модуль

87

40

22

18

47

1.                   

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

16

6

3

3

10

2.                   

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

11

5

3

2

6

3.                   

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

11

6

3

3

5

4.                   

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

11

5

3

2

6

5.                   

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

19

9

5

4

10

6.                   

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

19

9

5

4

10

 

4 модуль

129

40

18

22

89

7.                   

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

27

8

4

4

19

8.                   

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

28

9

3

6

19

9.                   

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

13

6

3

3

7

10.               

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

26

8

3

5

18

11.               

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

19

5

3

2

14

12.               

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

16

4

2

2

12

 

Итого:

216

80

40

40

136



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


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 контрольные работы, 1 коллоквиум.

Экзамен (4-й модуль), зачет (3-й модуль).


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

Оценка за текущий, промежуточный и итоговый контроль выставляется по 10-балльной системе.


Результирующая оценка за текущий контроль учитывает результаты студента по текущему контролю следующим образом:

Отекущий = n1* Ок/р + n2* Окол + n3* Осам. работа

Преподаватель оценивает самостоятельную работу студентов: правильность выполнения домашних работ, задания для которых выдаются на семинарских занятиях, правильность решения задач на семинаре. Оценки за самостоятельную работу студента преподаватель выставляет в рабочую ведомость. Накопленная оценка - Осам. работа определяется перед промежуточным (итоговым) контролем.

Сумма удельных весов должна быть равна единице: ?ni = 1 Способ округления накопленной оценки текущего контроля в пользу студента.


Результирующая оценка за промежуточный (итоговый) контроль складывается из результатов накопленной результирующей оценки за текущий контроль, удельный вес которой составляет k1 = 0,5 и оценки за экзамен/зачет, удельный вес k2 = 0,5.

Опромежуточный/итоговый = 0,5 * Отекущий + 0,5 * Озачет/экзамен

Способ округления накопленной оценки промежуточного (итогового) контроля в форме зачета/экзамена в пользу студента.


Студент может получить возможность пересдать низкие результаты за текущий контроль.


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


Тема 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Факультет математики
Ландо Сергей Константинович – доктор физико-математических наук, профессор, декан факультета математики
Факультет математики iconФакультет математики
Ландо Сергей Константинович – доктор физико-математических наук, профессор, декан факультета математики
Факультет математики iconМосковский государственный институт электроники и математики Факультет прикладной математики утверждаю
Наименование дисциплины Математический анализ
Факультет математики iconПерваковой Елены Евгеньевны
Московский государственный институт электроники и математики (Технический университет), факультет прикладной математики, диплом с...
Факультет математики iconФакультет математики, физики и информатики
«Математика вокруг нас» направлен на развитие интереса обучающихся к изучению математики, повышение уровня их информационной культуры,...
Факультет математики iconФакультет математики Рабочая программа научно-исследовательского семинара «Основные понятия математики»
Рабочая программа научно-исследовательского семинара «Основные понятия математики» [Текст]/Сост. Бурман Ю. М.; Гу-вшэ.–Москва.–2009.–4...
Факультет математики iconФакультет математики Рабочая программа научно-исследовательского семинара «Основные понятия математики»
Рабочая программа научно-исследовательского семинара «Основные понятия математики» [Текст]/Сост. Бурман Ю. М.; Гу-вшэ.–Москва.–2009.–4...
Факультет математики iconФакультет Бизнес-информатика отделение прикладной математики

Факультет математики iconИстратов Анатолий Юрьевич, 1957 года рождения, русский, в 1981 году окончил факультет Прикладной математики миэм по специальности Автоматизированные системы управления
Профессор кафедры Кибернетики Московского института электроники и математики научно-исследовательского университета Высшая школа...
Факультет математики iconФакультет математики Рабочая программа научно-исследовательского семинара кафедры дискретной математики «Теория представлений»
Рабочая программа научно-исследовательского семинара кафедры дискретной математики
Факультет математики iconФакультет математики Рабочая программа научно-исследовательского семинара кафедры дискретной математики «Теория представлений»
Рабочая программа научно-исследовательского семинара кафедры дискретной математики
Разместите кнопку на своём сайте:
Документы


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