Программа курса Дополнительные главы дискретной математики для групп 318, 319 кафедры математической кибернетики

Вид материала

Программа курса

Содержание Конечнозначные логики Ограниченно-детерминированные функции Вычислимые функции Конечные поля

Подобный материал:

• Рабочая программа спецкурса, 57.84kb.
• Войта Елена Александровна, магистрант факультета математики, механики и компьютерных, 129.35kb.
• М. В. Ломоносова Факультет вычислительной математики и кибернетики Кафедра математической, 6.81kb.
• Элементы математической логики, 189.46kb.
• Программа дисциплины «Дискретная математика» Индекс дисциплины по учебному плану ен., 194.02kb.
• Программа элективного курса для обучающихся 9 класса основной школы Тип элективного, 53.13kb.
• Программа по дисциплине математическая логика, 31.64kb.
• А. М. Горького Институт по переподготовке и повышению квалификации программа курса, 53.14kb.
• Факультет прикладной математики и кибернетики, 180.69kb.
• Задачи на графах программа, 81.89kb.

Программа курса

Дополнительные главы дискретной математики

для групп 318, 319 кафедры математической кибернетики

(Лектор 2007-2008 уч. г. – доцент Селезнева С. Н,)


Аннотация


Курс является продолжением обязательного курса «Дискретная математика» (для студентов 1-го курса). Он содержит в себе всю программу потокового курса «Дополнительные главы дискретной математики» (для студентов 3-го курса 2-го потока). В нее включены разделы, относящиеся к конечнозначным функциям, ограниченно-детерминированным функциям, вычислимым функциям. Курс содержит также дополнительные части, касающиеся конечных полей и комбинаторики.


Тематический план курса

N	Название темы	Лекции	Семинары	Самостоятельная работа студента
1.	Конечнозначные логики	10 ч	6 ч	16 ч
2.	Ограниченно-детерминированные функции	6 ч	4 ч	10 ч
3.	Вычислимые функции	12 ч	6 ч	18 ч
4.	Конечные поля	10 ч	2 ч	12 ч
5.	Комбинаторика	10 ч	6 ч	16 ч
	Итого:	48 ч	24 ч	72 ч
	Всего: (аудиторные занятия и самостоятельная работа студентов)	144 ч

Содержание курса

Лекции

1. Конечнозначные логики
   

Функции k-значной логики. Формулы, I-я и II-я формы. Полные системы. Полнота системы Поста. Функция Вебба. Алгоритм распознавания полноты конечных систем функций k-значной логики. Теорема А. В. Кузнецова о функциональной полноте. Существенные функции. Леммы о существенных функциях: лемма о трех наборах, основная лемма, лемма о квадрате. Критерий С. В. Яблонского полноты систем функций k-значной логики. Шефферовы функции. Критерий шефферовости. Особенности k-значных логик. Теорема Ю. И. Янова. Теорема А. А. Мучника. Теорема о полноте системы полиномов в Pk.

2. Ограниченно-детерминированные функции
   

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

3. Вычислимые функции
   

Машины Тьюринга (МТ). Машинные коды: основной, l-кратный, решетчатый и квазиосновной. Задача поиска левой единицы в основном коде. Лемма о моделировании на решетке. Лемма о преобразовании основного кода в l-кратный. Лемма о преобразовании решетчатого кода в основной. Вычислимые функции. Лемма о существовании МТ, правильно вычисляющей вычислимую функцию. Операция суперпозиции. Теорема о замкнутости класса вычислимых функций относительно операции суперпозиции. Операция примитивной рекурсии. Теорема о замкнутости класса вычислимых функций относительно операции примитивной рекурсии. Операция минимизации. Теорема о замкнутости класса вычислимых функций относительно операции минимизации. Класс примитивно рекурсивных функций. Некоторые примитивно-рекурсивные функции. Пеановская функция, ее примитивная рекурсивность. Схема одновременной примитивной рекурсии. Частично-рекурсивные функции. Формула Клини. Теорема о соотношении классов частично-рекурсивных и вычислимых функций.

4. Конечные поля
   

Алгебраическая операция, нейтральный элемент, симметричный элемент. Группа, абелева группа. Циклическая группа, образующий элемент группы. Конечная группа, порядок группы, таблица Кэли. Примеры. Подгруппа. Теорема об отношении эквивалентности по подгруппе. Смежные классы по подгруппе, разложение группы по подгруппе. Индекс подгруппы в группе, теорема о порядке конечной группы. Нормальная подгруппа. Фактор-группа группы по нормальной подгруппе. Кольцо. Коммутативное кольцо, кольцо с единицей, целостное кольцо, тело, поле. Теорема о конечном целостном кольце.

Двусторонний идеал кольца, главный идеал кольца. Фактор-кольцо кольца по модулю идеала. Теорема о фактор-кольце Z/(p) (число p – простое). Характеристика кольца. Теорема характеристике конечного поля. Максимальный идеал кольца. Теорема о максимальном идеале. Простой идеал кольца. Теорема о простом идеале. Обратимые, ассоциированные, простые элементы кольца. Кольцо главных идеалов. Теорема о кольце главных идеалов. Многочлен над кольцом, степень многочлена. Сумма, произведение двух многочленов. Кольцо многочленов. Деление многочленов. Теорема о кольце многочленов как о кольце главных идеалов. Наибольший общий делитель (НОД) нескольких многочленов. Теорема о НОД нескольких многочленов. Алгоритм Евклида нахождения НОД двух многочленов. Неприводимые многочлены. Лемма о неприводимом делителе произведения многочленов. Теорема о каноническом разложении многочлена. Описание фактор-кольца кольца многочленов по модулю главного идеала, порожденного неприводимым многочленом. Приведение по модулю многочлена. Примеры. Значение многочлена в точке. Корень многочлена, критерий корня. Кратный корень. Критерий кратности корня. Критерий неприводимости многочлена степени 2 или 3. Подполе. Простое поле. Простое расширение поля. Алгебраическое расширение поля. Теорема о простом алгебраическом расширении поля, полученном присоединением корня неприводимого многочлена. Теорема о мультипликативной группе конечного поля. Примитивный элемент конечного поля. Функция Мебиуса. Формула обращения Мебиуса. Теорема С. А. Степанова о числе нормированных неприводимых многочленов фиксированной степени над конечным полем.

5. Комбинаторика
   

Размещения, перестановки, сочетания, их число и рекуррентные формулы для

них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями.

Формула включений-исключений. Перестановки с ограничениями. Задача Монмора о числе беспорядков. Число разбиений. Числа Стирлинга II-го рода и числа Белла, рекуррентные формулы для них. Теорема о числах Стирлинга II-го рода как коэффициентах перехода от базиса убывающих факториалов к полиномиальному базису. Числа Стирлинга I-го рода. Рекуррентные формулы для них. Содержательный смысл модулей чисел Стирлинга I-го рода. Рекуррентные линейные уравнения (однородные и неоднородные). Общее решение рекуррентных линейных уравнений (однородных и неоднородных). Симметрическая группа перестановок. Теорема Кэли об изоморфизме конечной группы подходящей подгруппе Sn. Теорема Лагранжа о порядке подгруппы конечной группы. Отношение эквивалентности по подгруппе Sn. Орбита элемента, стабилизатор элемента. Лемма об индексе стабилизатора элемента в группе. Лемма Бернсайда о числе орбит по группе. Раскраски, эквивалентность раскрасок по подгруппе Sn. Тип перестановки, цикловой индекс группы перестановок. Теорема Пойа о числе орбит раскрасок по группе перестановок. Частично-упорядоченные множества (ЧУМ). Сравнимые и несравнимые элементы, линейный порядок. Минимальный (максимальный), наименьший (наибольший) элементы. Диаграмма Хассе. Цепь, антицепь. Длина и ширина ЧУМ. Покрытие ЧУМ. Теорема Дилуорса о мощности минимального покрытия конечного ЧУМ. Ранжированные ЧУМ. Куб Bn. Теорема о ширине куба Bn. Теорема Ж. Анселя о покрытии куба Bn цепями. Монотонные булевы функции. Нижняя и верхняя оценки числа монотонных булевых функций от n переменных.

Литература

1. Яблонский С. В. Введение в дискретную математику. М., Наука, 2001.
   
2. Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М., Мир, 1988.
   
3. Айгнер М. Комбинаторная теория. М., Мир, 1982.
   
4. Ансель Ж. О числе монотонных булевых функций от n переменных. В кн. Кибернетический сборник. Новая серия. Вып. 5. М., Мир, 1968, с. 53-57.
   
5. Степанов С. А. Арифметика алгебраических кривых. М., Наука, 1992.
   
6. Холл М. Комбинаторика. М., Мир, 1970.
   
7. Де Брейн Н. Дж. Теория перечисления Пойа. В сб. ст. Прикладная комбинаторная математика, под ред. Э. Бакенбаха. М., Мир, 1966, с. 61-107.
   

Семинары

Семинар 1. Функции k-значных логик. I-я и II-я формы.

Задачи: [1] Гл. III 1.1(1-4), 1.2(1, 2, 4, 12, 14), 1.11(1, 4, 8, 10).

На дом: [1] Гл. III 1.2(3, 5, 6, 13, 15), 1.3, 1.6, 1.8.


Семинар 2. Задание функций k-значной логики полиномами.

Задачи: [1] Гл. III 2.7(1, 3, 6, 9), 2.8(1), 2.11(1), 2.12(1, 3, 5), 2.22(1, 3), 2.23(2, 4).

На дом: [1] Гл. III 2.7(2, 4, 8, 10), 2.8(2, 3), 2.12(2, 4), 2.22(2, 4), 2.23(3, 5).


Семинар 3. Полнота систем функций k-значных логик.

Задачи: [1] Гл. Ш 2.1(1 а, б), 2.2(1), 2.3(1), 2.13(1, 2, 5, 6), 2.16(1, 3), 2.19(1, 2, 9, 11), 2.21(1, 2, 3, 9, 10).

На дом: [1] Гл. III 2.13(3, 4, 9, 10), 2.14, 2.15, 2.16(2, 4), 2.19(3, 4, 10, 12), 2.21(4, 5, 6, 11, 12).


Семинар 4. Ограниченно-детерминированные функции. Диаграммы Мура.

Задачи: [1] Гл. IV 1.1(1, 2, 3, 11, 12), 1.10(3, 5, 12, 16), 2.1(1, 2, 16, 24, 27).

На дом: [1] Гл. IV 1.10(7, 9, 13, 17), 2.1(4, 5, 14, 17, 25, 28).


Семинар 5. Полнота систем ограниченно-детерминированных функций.

Задачи: [1] Гл. IV 2.17(1, 2, 4, 6, 11, 14), 2.18(1, 3, 5).

На дом: [1] Гл. IV 2.17(3, 7, 8, 10, 15), 2.18(2, 4).


Семинар 6. Вычислимые функции.

Задачи: [1] Гл. V 1.2(1, 2, 3, 4), 1.4(1, 2), 1.5, 1.14(1, 3, 4, 7, 9, 10), 1.15(2, 3).

На дом: [1] Гл. V 1.2(4, 5), 1.4(3, 4), 1.6, 1.7, 1.14(2, 5, 12), 1.15(1, 7).


Семинар 7. Операция примитивной рекурсии. Примитивно-рекурсивные функции.

Задачи: [1] Гл. V 2.2(1, 2), 2.1(1, 3, 4, 7, 10), 2.4(1, 2, 5 а), 2.3(1, 2, 5, 7, 10).

На дом: [1] Гл. V 2.2(3, 4), 2.1(5, 6, 11), 2.3(6, 7, 11), 2.4(3, 5 б, 7 а, б).


Семинар 8. Операция минимизации. Частично-рекурсивные функции.

Задачи: [1] Гл. V 2.5(1, 2, 3, 4, 7, 8, 11, 15), 2.6(1, 3), 2.7(1, 3, 5), 2.8(1, 2).

На дом: [1] Гл. V 2.5(5, 6, 10, 13), 2.6(2, 4), 2.7(2, 4), 2.8(3, 4, 5).


Семинар 9. Построение конечных полей.

Задачи: [2] Гл. I 1.2, 1.3, 1.11, 1.19, 1.24(a, c), 1.31, 1.34, 1.40, 1.56.

На дом: [2] Гл. I 1.15, 1.16, 1.24(b, d), 1.32, 1.35, 1.36, 1.40, 1.41, 1.43.


Семинар 10. Простейшие комбинаторные числа.

Задачи: [1] Гл. VIII 1.1, 1.9, 1.13(3, 5), 1.18(3, 5, 6, 9), 2.4, 2.6(1, 2, 4).

На дом: [1] Гл. VIII 1.2, 1.12, 1.13(2, 8), 1.18(4, 7, 8, 12), 2.5, 2.6(3, 5).


Семинар 11. Рекуррентные уравнения.

Задачи: [1] Гл. VIII 3.2(1, 3, 4), 3.3(1, 2, 4), 3.5(1, 2, 4), 3.6(2), 3.21(1, 3, 5).

На дом: [1] Гл. VIII 3.2(2, 5, 6), 3.3(5, 6), 3.5(3, 5, 6), 3.6(1, 3), 3.21(2, 4, 6).


Семинар 12. Теорема Пойа.

Задачи: [1] Гл. VIII 4.1(1, 3), 4.3(1, 2, 4, 6, 8), 4.4(1), 4.9(1), 4.10(1, 3).

На дом: [1] Гл. VIII 4.1(2, 4), 4.3(3, 5, 7, 9), 4.4(2), 4.9(2), 4.10(2).

Литература

1. Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. М., Физматлит, 2004.

2. Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М., Мир, 1988.