Программа дисциплины «Дискретная математика и теория алгоритмов» - umotnas.ru o_O
Программа дисциплины «Дискретная математика и теория алгоритмов» - umotnas.ru o_O
|
страница 1
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Похожие работы
|
Программа дисциплины «Дискретная математика и теория алгоритмов» - страница №1/1
Правительство Российской Федерации Государственное образовательное бюджетное учреждение высшего профессионального образования Государственный университет – Высшая школа экономики Факультет математикиРабочая программа дисциплины «Дискретная математика и теория алгоритмов»
Москва 2009 Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И.В., Ландо С.К.; ГУ-ВШЭ.–Москва.–2009.–11 с. Рабочая программа составлена на основе государственных требований к минимуму содержания и уровню подготовки бакалавров Государственного образовательного стандарта высшего профессионального образования по направлению 010100 «Математика». Рабочая программа предназначена для методического обеспечения дисциплины основной образовательной программы по направлению 010100 «Математика». Составители: д.ф.-м.н. И.В. Артамкин (artamkin@hse.ru) д. ф.-м. н. С.К.Ландо (lando@hse.ru)
Пояснительная записка Авторы программы: доктор физико-математических наук И.В. Артамкин, доктор физико-математических наук С.К.Ландо. Требования к студентам: дисциплина изучается на первом курсе, так что требуется только владение алгеброй и геометрией в объеме школьной программы; для материала третьего модуля требуется курс алгебры 1 и 2 модулей. Аннотация: Дисциплина «Дискретная математика и теория алгоритмов» предназначена для подготовки бакалавров по направлению 010100.62. Цели и задачи изучения дисциплины, ее место в учебном процессе 1.1. Цель изучения дисциплины. Получение: – представления об основных методах и результатах дискретной математики; – знания об основных результатах и алгоритмах комбинаторики, теории чисел, теории графов, теории кодирования и других разделов дискретной математики; – умения решать различные дискретные задачи средствами комбинаторики и теории графов; – опыта использования, применения изучаемых методов к исследованию и решению конкретных задач. 1.2. Задачи изучения дисциплины: овладение основными средствами дискретной математики – применение комбинаторики, теории чисел, теории графов к решению различных задач. 1.3. Перечень дисциплин и разделов, знание которых требуется для изучения данной дисциплины: материал школьной программы по математике; для второго семестра – курс алгебры первого семестра. Тематический план учебной дисциплины
Базовые учебники 1. Стенли Р. Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции. Перев. с англ.–М.: Мир, 2005. 2. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике: Учеб. пособие для вузов –М.: Физматлит, 2006. 3. Виноградов И.М. Основы теории чисел.– Изд.11–е, стер.–Спб.:Лань, 2006. 4. Ландо С.К. Лекции о производящих функциях. – Изд. 3–е.– М.: МЦНМО, 2007. 5. Харари Ф. Теория графов.–М.: УРСС, 2003. 6. Вильямс Дж. Дискретная математика и комбинаторика. – Вильямс, 2006. 7. Дональд Кнут, Роналд Грэхем, Орен Паташник. Конкретная математика. Основания информатики.–М.:Мир; Бином. Лаборатория знаний, 2006. Промежуточный контроль: 2 контрольные работы. Итоговый контроль: экзамен (4-й модуль). Выборки, перестановки, сочетания, перестановки с повторениями; сочетания с повторениями; биномиальные коэффициенты, их свойства; биномиальная теорема; полиномиальная теорема; формула включения и исключения. Тема 2. Производящие функции. Вычисления с формальными степенными рядами. Рациональные производящие функции и линейные рекуррентные соотношения с постоянными коэффициентами. Тема 3. Свойства делимости целых чисел. Простые числа.Решето Эратосфена. Теорема Евклида о бесконечности множества простых чисел. Основная теорема арифметики о разложении целых чисел на простые сомножители. Наибольший общий делитель и наименьшее общее кратное. Некоторые частные случаи теоремы Дирихле о бесконечности множества простых чисел в арифметической прогрессии. Тема 4. Арифметические функции. Целая и дробная часть числа; разложение числа n! на простые множители; суммы, распространенные на делители числа; мультипликативные функции; функция Эйлера и ее свойства; сумма делителей и число делителей; оценки Чебышева для функции числа простых чисел, не превосходящих x. Тема 5. Цепные дроби; конечные цепные дроби; подходящие дроби и их свойства; нахождение наибольшего общего делителя с помощью цепных дробей; бесконечные цепные дроби; разложение действительных чисел в цепные дроби; приближение действительных чисел рациональными числами; подходящие дроби как наилучшие приближения; признак иррациональности числа; иррациональность числа «е»; теорема Лагранжа о разложении квадратичных иррациональностей в цепные дроби. Сравнения и их основные свойства; вычеты и классы вычетов по модулю m; кольца классов вычетов; полная система вычетов; приведенная система вычетов; теорема Эйлера и Ферма; сравнения первой степени: сравнения с одним неизвестным; равносильные сравнения; решения сравнения; сравнения первой степени; теорема о существовании решений; простейшие приемы решений; решение сравнений с помощью цепных дробей; системы сравнений, их решения; теоремы о решении систем сравнений первой степени; сравнения n-й степени: сравнения n-й степени по простому модулю; теоремы о равносильности сравнений; теорема о числе решений сравнения; теорема Вильсона; сравнения n-ой степени по составному модулю; сведение сравнения по составному модулю к системе сравнений по простому модулю; сравнения второй степени: сведение сравнений второй степени к двучленному сравнению; двучленные сравнения по простому модулю. Тема 7. Графы. Основные понятия; способы представления графов. Изоморфизм, гомеоморфизм и гомотопия графов; основные инварианты графов. Деревья и их свойства. Остовное поддерево. Простейшие алгоритмы теории графов. Эйлеровы и гамильтоновы графы. Перечислительные задачи теории графов. Теорема Кэли. Формула Эйлера для плоских графов. Тема 8. Циклы и разрезы. Граничный и кограничный оператор. Гомологии и когомологии графа. Двойственность. Циклы и разрезы по модулю два. Базисы циклов и разрезов, связанные с остовным поддеревом. Матрицы циклов и разрезов. Теорема Коши-Бине. Теорема Кирхгофа о числе остовных поддеревьев. Остовные поддеревья полного графа и теорема Кэли. Элементы теории матроидов. Понятие матроида. Двойственность. Графические и кографические матроиды. Линейные матроиды. Представимость. Матроид Фано. Тема 9. Планарные графы. Теорема Эйлера. Раскраски планарных графов. Проблема четырех красок. Критерии планарности. Теорема Понтрягина-Куратовского. Укладки графов и род графа. Тема 10. Потоки в сетях. Теорема Форда – Фалкерсона; алгоритм Форда – Фалкерсона. Связность и маршруты на графах. Числа связности графа. Разделяющие множества. Реберная и вершинная теоремы Менгера. Двудольные графы; паросочетания. Совершенное паросочетание. Теорема Холла. Венгерский алгоритм построения совершенного паросочетания. Задача об оптимальном назначении. Ленточные графы. Вычисление рода поверхности. Двойственный граф. Примеры. Дискретный оператор Лапласа. Представление классов гомологий гармоническими циклами. Тема 12. Производящие функции в комбинаторике и теории графов. Числа Каталана. Явное вычисление производящих функций для различных типов графов. Образцы заданий по различным формам контроля Цикл 1. Комбинаторика. Выборки, перестановки, сочетания, перестановки с повторениями; сочетания с повторениями; биномиальные коэффициенты, их свойства; биномиальная теорема; полиномиальная теорема; формула включения и исключения. Цикл 2. Производящие функции. Вычисления с формальными степенными рядами. Рациональные производящие функции и линейные рекуррентные соотношения с постоянными коэффициентами. Цикл 3. Свойства делимости целых чисел. Простые числа.Решето Эратосфена. Теорема Евклида о бесконечности множества простых чисел. Основная теорема арифметики о разложении целых чисел на простые сомножители. Наибольший общий делитель и наименьшее общее кратное. Некоторые частные случаи теоремы Дирихле о бесконечности множества простых чисел в арифметической прогрессии. Цикл 4. Арифметические функции. Целая и дробная часть числа; разложение числа n! на простые множители; суммы, распространенные на делители числа; мультипликативные функции; функция Эйлера и ее свойства; сумма делителей и число делителей; оценки Чебышева для функции числа простых чисел, не превосходящих x. Цикл 5. Цепные дроби; конечные цепные дроби; подходящие дроби и их свойства; нахождение наибольшего общего делителя с помощью цепных дробей; бесконечные цепные дроби; разложение действительных чисел в цепные дроби; приближение действительных чисел рациональными числами; подходящие дроби как наилучшие приближения; признак иррациональности числа; иррациональность числа «е»; теорема Лагранжа о разложении квадратичных иррациональностей в цепные дроби. Цикл 6. Числовые сравнения. Сравнения и их основные свойства; вычеты и классы вычетов по модулю m; кольца классов вычетов; полная система вычетов; приведенная система вычетов; теорема Эйлера и Ферма; сравнения первой степени: сравнения с одним неизвестным; равносильные сравнения; решения сравнения; сравнения первой степени; теорема о существовании решений; простейшие приемы решений; решение сравнений с помощью цепных дробей; системы сравнений, их решения; теоремы о решении систем сравнений первой степени; сравнения n-й степени: сравнения n-й степени по простому модулю; теоремы о равносильности сравнений; теорема о числе решений сравнения; теорема Вильсона; сравнения n-ой степени по составному модулю; сведение сравнения по составному модулю к системе сравнений по простому модулю; сравнения второй степени: сведение сравнений второй степени к двучленному сравнению; двучленные сравнения по простому модулю. Цикл 7. Графы. Основные понятия; способы представления графов. Изоморфизм, гомеоморфизм и гомотопия графов; основные инварианты графов. Деревья и их свойства. Остовное поддерево. Простейшие алгоритмы теории графов. Эйлеровы и гамильтоновы графы. Перечислительные задачи теории графов. Теорема Кэли. Формула Эйлера для плоских графов. Цикл 8. Циклы и разрезы. Граничный и кограничный оператор. Гомологии и когомологии графа. Двойственность. Циклы и разрезы по модулю два. Базисы циклов и разрезов, связанные с остовным поддеревом. Матрицы циклов и разрезов. Теорема Коши-Бине. Теорема Кирхгофа о числе остовных поддеревьев. Остовные поддеревья полного графа и теорема Кэли. Элементы теории матроидов. Понятие матроида. Двойственность. Графические и кографические матроиды. Линейные матроиды. Представимость. Матроид Фано. Цикл 9. Планарные графы. Теорема Эйлера. Раскраски планарных графов. Проблема четырех красок. Критерии планарности. Теорема Понтрягина-Куратовского. Укладки графов и род графа. Цикл 10. Потоки в сетях. Теорема Форда – Фалкерсона; алгоритм Форда – Фалкерсона. Связность и маршруты на графах. Числа связности графа. Разделяющие множества. Реберная и вершинная теоремы Менгера. Двудольные графы; паросочетания. Совершенное паросочетание. Теорема Холла. Венгерский алгоритм построения совершенного паросочетания. Задача об оптимальном назначении. Ленточные графы. Вычисление рода поверхности. Двойственный граф. Примеры. Дискретный оператор Лапласа. Представление классов гомологий гармоническими циклами. Цикл 12. Производящие функции в комбинаторике и теории графов. Числа Каталана. Явное вычисление производящих функций для различных типов графов. Темы контрольных работ:
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|