Ответы: Программа курса

Распознанный текст из изображения:

11,112004

ПРОГРАММА

(предварительная)

курса "Днскретнаи математика", механико-математический факультет МГУ, 4-й курс

7-й семестр, 2-й поток, 2004/2005 учебный год

(лектор — А.Б.Угольников)

1. Выборки, перестановки, сочетания, перестановки с повторениями, сочетания с повторениями.

Биномиальные коэффициенты, их свойства, биномиальная теорема, полиномиальные коэффициенты,

полиномиальная теорема.

2. Формулы обращения. Метод включений и исключений. Верхняя и нижняя оценки для числа элементов, не

обладающих ни одним из свойств, Функция Мебиуса. Формула обращения Мебиуса. Перечисление

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

.' 'ваатлшиь'упэорлдочевныа-множества, алгебра: иицюилгпгегти'-'-А(Р)'-"миойеетва---Р г-иеобхошвиьгеег'зг ':

достаточные условия существования обратных функций в А(Р) . Дзета-функция множества Р, функция

Мсбиуса множества Р . Формула обращения Мебиуса для частично-упорядоченных множеств. Примеры:

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

множества всех подмножеств конечного множества, упорядоченных по включению.

3. Формальные степенные ряды, операции нал степенными рядами и их свойства, кольцо формальных

степенных рядов. Конечные поля. Порядок и характеристика поля. Свойства конечных полей. Поле Сг)" (р), р — простое. Неприводимые многочлены. Нумератор мнвкества всех нормированных многочленов с коэффициентами из 61' (р), р — простое. Формула для числа 1ьг неприводимых нормированных многочленов с коэффициентами из 6г (р) степени 1г. Существование неприводимых многочленов заданной степени. Асимптотическал формула для 1'. Поле 6Р(р" ) - поле миогочлеиов степени не вьппе и — 1 с коэффициентами из 4ээр(р), р — простое. Построение поля ОР(р ) .

4. Производящие функции. Примеры применения метода пронзводюцих функций для решения

комбииаторных задач. Линейные рекуррентиые соотношения с постоянными коэффициентами. Решение

линейных рекурреитных соотношений.

5. Теорема Рамсея (двуцветная раскраска). Верхние оценки для чисел эг'(р, <1,2) . Теорема Эрдеша о нижней

оценке для чисел У(р, р,2), Теорема Рамсея (мнопщветиая раскраска). Теорема Шура об одноцветном решении уравнения; х + у = я . Теорема (Ферма для конечных полей) о существовании решения уравнения х + у = г (итог р),р — простое.

б. Двудольные графы. Паросочетаиия в двудольиых графах. Максимальное паросочегаиие. Совершенное

паросочегаиие. Теорема Холла о свадьбах (о паросочетании в двудольном графе). Задача о разделе

имущества. Множеспю Е "т всех двоичных наборов длины п. Разбиение множества Е г всех двоичных

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

булевых функций. Рассеканлцие множества. Теорема Кенига-Эгервари о рассекающих множествах в

двудольном графе.

7. Побуквенное (алфавитное) кодирование. Разделимые коды. Префиксные коды. Неравенство КрафтаМакмил~ииа для разделимых кодов. Условие существования разделимого кода с заданными длинами кодовых слов. Критерий взаимной однозначности алфавитного кодирования. Полные коды. Необходимые и достаточные условия для полных кодов. Построение по заданному префиксному коду полного кода.

Распознанный текст из изображения:

Оптимальные коды. Свойства оптимальных двоичных кодов. Полнота префиксного оптимального двоичного кода. Оптимальность заданного полного префиксного кода для некоторого множества Р, Верхняя и нижняя оценки для стоимости оптимального кода. Методы построения оптимальных кодов: метод Фана, метод Шеннона. Теорема редукции. Алгоритм Хаффмена построения оптимальных двоичных кодов

Коды, исправляющие ошибки. Граница сферической упаковки (верхняя оценка мощности максимального

кода). Построение кодов, исправляющих 1 ошибок. Коды Хэммннга, их свойства. Алгоритм декодирования

для кодов Хэмминга. Совершенные коды.

10. Линейные коды. Проверочные и порвкдающие матрицы линейных кодов. Параметры линейных кодов

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

Граница Синглтона. Алгоритм построения линейного кода, с заданным минималъным расстоянием. Граница

Варшамова — Гилберта, Декодирование линейных кодов. Смежные классы, лидеры смежных классов,

синдром, стандартное расположение. Алгоритм декодирования по максимуму правдоподобна.

Двоичные коды БЧХ (коды Боуза-Чоудхури-Хоквингема). Построение кодов БЧХ, исправляющих 1 ошибок для любого натурального, 1, параметры кодов БЧХ. Алгоритм декодирования для кодов БЧХ, исправляющих двойные ошибки. Нормальные базисы. Решение квадратньгх уравнений вида х +ю~1ц'+с = О в поле

г

6Е(2 ). Симметрические функции, элементарные симметрические функции, степенные функции. Решение системы уравнений, связывающих степенные и элементарные симметрические функции. Алгоритм декодирования для кодов БЧХ„исправляющих 1 ошибок для любого натурального 1 . Тождества Ньютона. Алгоритм декодирования 1Питерсона) для кодов БЧХ, исправляющих тройные ошибки.

)3. Конечные автоматы. Автоматные функции. Способы задания автоматных функций. Состояния автомата

эквивалентность состояний. Теорема Мура об эквивалентных состояниях автомата. Эквивалентность автоматов. Теорема об эквивалентности состояний автоматов. Сокращенный автомат. Метод построения сокращенного автомата.

14. События. Операции над событиями. Регулярные события. Представимые события. Теорема о событиях

представимых конечными автоматами. Обобщенные источники. Представление регулярных событий обобщенными источниками. Теорема о представимости регулярных событий автоматами. Теорема Клини. Пример нерегулярного события. Источники. Представление регуларных событий источниками. Равенство регулярных событий.

Функции алгебры логики. Существенные и несущественные переменные. Равенство функций. Формулы, представление функций формулами. Полные системы, примеры полнъзх систем. Полиномы Жегалкина. Теорема о представлении функций полиномами. Замкнутые классы. Линейные функции, лемма о нелинейной функции. Монотонные функции, лемма о немонотонной функции. Конъюнкции, дизъюнкции, лемма о порождении функций хи у и у Й г. Теорема о конечной порожденности замкнутых классов, содержащих константы О н 1. Замкнутые классы, содержащие константы 0 и 1.

15.

Функции, удовлетворяющие условию <О >, их свойства. свойства функций хна, а1 (х„...,х ), р ~ 2. Леммы о порождении монотонных функций. Теорема о конечной порожденности замкнутых классов монотонных функций, содержащих константу 1. Лемма о порождении импликации. Лемма о немонотоиных функциях. Теорема о конечной порожденности замкнутых классов, содержащих константу 1.

1б.

Самодвойственные функции, принцип двойственности. Функции, сохраняющие константы. Теорема о конечной порожденностн замкнутых классов, не содержащих констант. Теорема Пост» о конечной порожденности замкнутых классов булевых функций.

17.

12. Детерминированные функции. Задание детерминированных функций при помощи деревьев. Вес функций. Ограниченно-детерминированные функции (о.д.-функции). Способы задания о.д.-функций.

Файл скачан с сайта StudIzba.com

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