Программа дисциплины Комбинаторика (Combinatorics)  для направления 010100. 68 «Математика» подготовки магистра



Скачать 100.91 Kb.
Дата08.10.2012
Размер100.91 Kb.
ТипПрограмма дисциплины



Правительство Российской Федерации
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
"Национальный исследовательский университет
"Высшая школа экономики"


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

Программа дисциплины Комбинаторика (Combinatorics)


для направления 010100.68 «Математика» подготовки магистра

Автор программы: Ю.М.Бурман, к.ф.-м.н., burman@mccme.ru

Рекомендована секцией УМС по математике «___»____________ 2012 г.

Председатель С.М. Хорошкин

Утверждена УС факультета математики «___»_____________2012 г.

Ученый секретарь Ю.М. Бурман_____________________

Москва, 2012

Настоящая программа не может быть использована другими подразделениями университета и другими вузами без разрешения кафедры-разработчика программы.

1Область применения и нормативные ссылки


Настоящая программа учебной дисциплины устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности.

Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010100.68 «Математика» подготовки магистра.

Программа разработана в соответствии с:

  • Стандартом НИУ для направления 010100.68 «Математика» подготовки магистра;

  • Рабочим учебным планом университета по направлению 010100.68 «Математика» подготовки магистра, специализации Математика, утвержденным в 2011 г.


2Цели освоения дисциплины


Познакомить студентов с основными понятиями комбинаторики и некоторых ее приложений, подготовить их к освоению других курсов, использующих комбинаторные понятия и методы, а также к самостоятельным исследованиям в области комбинаторики.

3Компетенции обучающегося, формируемые в результате освоения дисциплины


В результате освоения дисциплины студент должен:

  • Знать формулировки и доказательства основных теорем курса.

  • Уметь решать комбинаторные задачи, аналогичные разобранным в курсе.

  • Иметь навыки анализа комбинаторной ситуации и выбора инструментов, наиболее подходящих для ее разбора.



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

Компетенция

Код по ФГОС/ НИУ

Дескрипторы – основные признаки освоения (показатели достижения результата)

Формы и методы обучения, способствующие формированию и развитию компетенции

способность к интенсивной научно-исследовательской и научно-изыскательской

деятельности, анализу связей между математическими задачами и задачами естествознания,

а также связей между задачами из различных областей математики, самостоятельное построение целостной картины дисциплины

ПК-2

Демонстрирует умение разбираться в новой задаче с применением методов, изученных на примере других задач (часто нескольких, не связанных между собой).

Регулярные домашние задания, развивающие темы, изученные в аудитории.


4Место дисциплины в структуре образовательной программы


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

  • Линейная алгебра, основы алгебры

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

  • Владеть методами линейной и общей алгебры: решать системы линейных уравнений, приводить матрицы к стандартному виду, проводить вычисления в группе перестановок.

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

  • Математическая физика, теория представлений.


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




Название раздела

Всего часов

Аудиторные часы

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

Лекции

Семинары

Практические занятия

1

Производящие функции

38

4

4




30

2

Линейная рекурсия

38

4

4




30

3

Симметрическая группа

40

4

4




32

4

Разбиения и композиции

38

4

4




30

5

Деревья

38

4

4




30




Итого:

162

20

20




122



6Формы контроля знаний студентов


Тип контроля

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

1 год

Параметры **

1

2

3

4

Текущий

(неделя)

Домашнее задание

*







8

От 2 до 5 задач, сдаются письменно на каждом занятии – за прошедшую неделю.

Промежу­точный

Зачет







V




Письменный зачет 180 минут

Итоговый

Экзамен











V

Письменный экзамен 180 минут



6.1Критерии оценки знаний, навыков


В процессе выполнения домашнего задания студент должен решать задачи, аналогичные разобранным на соответствующем аудиторном занятии. В некоторые домашние задания вставляются серии задач, в процессе решения которых студент осваивает новые результаты.

Промежуточный и итоговый контроль аналогичны по форме и представляют собой письменные работы, по форме и объему близкие к домашним заданиям.

Оценки по всем формам текущего контроля выставляются по 10-ти балльной шкале. Также применяется «американская» шкала (A,B,C,D), соответствующая 10-балльной шкале следующим образом: 10 баллов – A+. 9 баллов – A, 8 баллов – А-, 7 баллов – B+, 6 баллов – B, 5 баллов – C, 4 балла – С-. В исключительных случаях применяется оценка D, она соответствует 4 баллам.

7Содержание дисциплины


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

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

    Тема 1: основные операции с производящими функциями (2 часа лекций, 2 часа упражнений, 14 часов самостоятельной работы – решение задач из домашнего задания).

    Тема 2: алгебра формальных рядов (2 часа лекций, 2 часа упражнений, 16 часов самостоятельной работы – решение задач из домашнего задания).

    Литература: [1, раздел 2]

    2. Линейная рекурсия.

    Тема 1: Линейная рекурсия в полупростом случае (2 часа лекций, 2 часа упражнений, 14 часов самостоятельной работы – решение задач из домашнего задания).

    Тема 2: Линейная рекурсия при наличии кратных корней (2 часа лекций, 2 часа упражнений, 16 часов самостоятельной работы – решение задач из домашнего задания).

    Литература: [1, раздел 3]

    3. Симметрическая группа.

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

    Тема 2: инверсии (2 часа лекций, 2 часа упражнений, 16 часов самостоятельной работы – решение задач из домашнего задания).

    Литература: [2]

    4. Разбиения и композиции.

    Тема 1: производящая функция для числа разбиений (2 часа лекций, 2 часа упражнений, 14 часов самостоятельной работы – решение задач из домашнего задания).

    Тема 2: пентагональная теорема Эйлера (2 часа лекций, 2 часа упражнений, 16 часов самостоятельной работы – решение задач из домашнего задания).

    Литература: [2], [3].

    5. Деревья

    Тема 1: формула для общего числа деревьев (2 часа лекций, 2 часа упражнений, 14 часов самостоятельной работы – решение задач из домашнего задания).

    Тема 2: бесконфликтные очереди и соответствие Московичи (2 часа лекций, 2 часа упражнений, 16 часов самостоятельной работы – решение задач из домашнего задания).

8Оценочные средства для текущего контроля и аттестации студента

8.1Тематика заданий текущего контроля


Примерные вопросы/ задания для домашнего задания

  1. Пусть $x_1=1, x_2=1, \dots$ - последовательность чисел Фибоначчи. Докажите, что

    а) x_1 + x_2 +… + x_n = x_{n+2}-1; б) x_1^2 + x_2^2 + … + x_n^2 = x_n x_{n+1}; в) НОК(x_m,x_n) = x_{НОК(m,n)}.

    2. Пусть $x_n$ be – количество слов длины $n$ из букв a и b, не содержащих а) двух «а» подряд. б) «б» после «а»; в) трех «а» подряд. Докажите, что $x_n$ - последовательность с линейной рекурсией, и найдите для нее явную формулу.

8.2Вопросы для оценки качества освоения дисциплины


1. Производящие функции: Пусть (1+t)^a = \sum_{n=0}^\infty \frac{a(a-1) \dots (a-n+1)}{n!} t^n. а) Докажите, что (1+t)^a (1+t)^b = (1+t)^{a+b}. б) Докажите, что

(1+x)^a (1+y)^a = (1+x+y+xy)^a.

2. Линейная рекурсия: Пьяница стоит в точке n на прямой. Каждую секунду он с равной вероятностью делает шаг на единицу вправо или шаг на единицу влево. В точке 0 расположена яма. Найдите вероятность того, что рано или поздно пьяница упадет в яму.

3. Симметрическая группа: Пусть x = [142563]. а) Вычислите x^n для всех n = 1, 2, ... б) Найдите все перестановки y, для которых xy = yx.

4. Разбиения и композиции: Докажите, что количество разбиений числа n в сумму различных слагаемых равно количеству разбиений числа n в сумму нечетных слагаемых.

5. Деревья: Найдите количество деревьев с n вершинами и k инверсиями, где k = 0, 1, 2. Каким именно бесконфликтным очередям соответствуют такие деревья?

8.3Примеры заданий промежуточного /итогового контроля


1. Докажите, что функция f(x) = \sum_{n=1}^\infty x^n/n^2 не является рациональной (т.е. отношением двух многочленов).
2. Сколько существует способов разбить прямоугольник 2 x n на прямоугольники 1x2?
3. Число $k$ называется порядком перестановки x = [x(1), …, x(n)] если x^k = 1 k – наименьшее число с таким свойством. а) Каков наибольший порядок перестановки из 11 элементов? Сколько существует перестановок такого порядка?
4. Докажите, что число Каталана c_n равно количеству способов расположить числа 1, 2, …, 2n$ в прямоугольнике 2 x n так, чтобы числа в каждом столбце и в каждой строке шли в порядке возрастания.

9Порядок формирования оценок по дисциплине


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

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

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

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

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

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

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

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

10Учебно-методическое и информационное обеспечение дисциплины

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


1. С.К.Ландо. «Лекции по комбинаторике», М., МЦНМО, 1994.

10.2Основная литература


  1. G.Andrews, The theory of partitions, Cambridge mathematics library, CUP, 1984.

  2. Ю.М.Бурман, Б.Л.Фейгин, «Бесконечномерные алгебры Ли – 1», М., МЦНМО, 1996.




Похожие:

Программа дисциплины Комбинаторика (Combinatorics)  для направления 010100. 68 «Математика» подготовки магистра iconПрограмма дисциплины Спецкурс «Конфигурации гиперплоскостей: их комбинаторика, геометрия, алгебра и топология»
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010100. 62 «Математика»...
Программа дисциплины Комбинаторика (Combinatorics)  для направления 010100. 68 «Математика» подготовки магистра iconПрограмма дисциплины Спецкурс «Теория представлений в нецелых размерностях» для направления 010100. 62 «Математика»
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010100. 62 «Математика»...
Программа дисциплины Комбинаторика (Combinatorics)  для направления 010100. 68 «Математика» подготовки магистра iconПрограмма дисциплины нис «Геометрия и динамика» для направления 010100. 62 «Математика»
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010100. 62 «Математика»...
Программа дисциплины Комбинаторика (Combinatorics)  для направления 010100. 68 «Математика» подготовки магистра iconПрограмма дисциплины Дополнительные главы топологии для направления 010100. 68 «Математика» подготовки магистра
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010100. 68 «Математика»...
Программа дисциплины Комбинаторика (Combinatorics)  для направления 010100. 68 «Математика» подготовки магистра iconПрограмма дисциплины «Римановы поверхности»
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010100. 62 «Математика»...
Программа дисциплины Комбинаторика (Combinatorics)  для направления 010100. 68 «Математика» подготовки магистра iconПрограмма дисциплины нис «Спецфункции»
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010100. 62 «Математика»...
Программа дисциплины Комбинаторика (Combinatorics)  для направления 010100. 68 «Математика» подготовки магистра iconПрограмма дисциплины «Выпуклые многогранники»
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010100. 62 «Математика»...
Программа дисциплины Комбинаторика (Combinatorics)  для направления 010100. 68 «Математика» подготовки магистра iconПрограмма дисциплины «Римановы поверхности»
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010100. 62 «Математика»...
Программа дисциплины Комбинаторика (Combinatorics)  для направления 010100. 68 «Математика» подготовки магистра iconПрограмма дисциплины «Коммутативная алгебра»
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010100. 62 «Математика»...
Программа дисциплины Комбинаторика (Combinatorics)  для направления 010100. 68 «Математика» подготовки магистра iconПрограмма дисциплины «Теория чисел»
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010100. 62 «Математика»...
Разместите кнопку на своём сайте:
ru.convdocs.org


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