Вопросы к экзамену по курсу «Дополнительные главы дискретной математики»

1. 
   Теорема о существовании алгоритма распознавания полноты конечных систем функций k-значной логики.
   
2. 
   Теорема Кузнецова о функциональной полноте систем функций k-значной логики.
   
3. 
   Лемма о трех наборах для функций k-значной логики.
   
4. 
   Критерий Яблонского о полноте систем функций k-значной логики. Критерий Слупецкого.
   
5. 
   Теорема Янова. Теорема Мучника. Следствия из них.
   
6. 
   Детерминированная функция (д. функция). Мощность класса д. функций. Операции суперпозиции и обратной связи для д. функций. Замкнутость класса д. функций относительно операций суперпозиции и обратной связи.
   
7. 
   Ограниченно-детерминированная функция (о.-д. функция). Мощность класса о.-д. функций. Операции суперпозиции и обратной связи для о.-д. функций. Замкнутость класса о.-д. функций относительно операций суперпозиции и обратной связи.
   
8. 
   Теорема о конечной полной системе и теорема об аналоге шефферовой функции в классе k-значных о.-д. функций с операциями суперпозиции и обратной связи. Теорема о несводимости операции обратной связи к операции суперпозиции.
   
9. 
   Операция суперпозиции для функций счетнозначной частичной логики. Замкнутость класса вычислимых функций относительно операции суперпозиции.
   
10. 
    Операция примитивной рекурсии для функций счетнозначной частичной логики. Замкнутость класса вычислимых функций относительно операции примитивной рекурсии.
    
11. 
    Операция минимизации для функций счетнозначной частичной логики. Замкнутость класса вычислимых функций относительно операции минимизации.
    
12. 
    Теоремы о примитивной рекурсивности функции количества разрядов в записи числа в двоичной системе счисления и функции числа, соответствующего основному коду набора значений ее переменных. Функция Пеано и ее обобщения, их примитивная рекурсивность.
    
13. 
    Теорема о схеме одновременной примитивной рекурсии.
    
14. 
    Частично рекурсивные и общерекурсивные функции. Теорема Клини. Теорема о совпадении классов вычислимых и частично рекурсивных функций.
    
15. 
    Эквивалентность элементов по подгруппе симметрической группы перестановок Sn. Орбита и стабилизатор элемента. Теорема о мощности орбиты. Лемма Бернсайда.
    
16. 
    Раскраски элементов. Эквивалентность раскрасок относительно подгруппы симметрической группы перестановок Sn. Теорема Пойа.
    
    
17. 
    Идеалы кольца, главные идеалы коммутативных колец с единицей. Фактор-кольцо по модулю идеала. Кольцо главных идеалов. Теорема о фактор-кольце кольца главных идеалов.
    
18. 
    Кольцо многочленов над конечным полем. Теорема о кольце многочленов над конечным полем как кольце главных идеалов.
    
19. 
    Теорема о мультипликативной группе конечного поля. Примитивный элемент конечного поля.
    
20. 
    Теорема о разбиении булева куба на цепи Анселя. Оценки количества монотонных булевых функций от n переменных.
    

1. 
   Функция k-значной логики. Элементарные функции k-значной логики. Теорема о числе функций k-значной логики, зависящих от n переменных. Теоремы о 1-й и 2-й формах записи функций k-значной логики.
   
2. 
   Теорема о полноте системы Поста функций k-значной логики. Функция Вебба.
   
3. 
   Основная лемма для функций k-значной логики.
   
4. 
   Лемма о квадрате для функций k-значной логики.
   
5. 
   Критерий шефферовой функции k-значной логики.
   
6. 
   Теорема о задании функций k-значной логики полиномами по модулю k.
   
7. 
   Лемма о преобразовании периодической последовательности о.-д. функцией в периодическую последовательность. Теорема о несуществовании конечных полных систем в классе о.-д. функций с операцией суперпозиции.
   
8. 
   Машины Тьюринга (МТ). Конфигурации МТ, начальная, заключительная конфигурации. Вычисление МТ на слове, применимость и неприменимость МТ к слову. Решетка с шагом l. Лемма о моделировании МТ на решетке.
   
9. 
   Функция счетнозначной частичной логики, вычислимая по Тьюрингу. Мощность класса вычислимых функций. Машина Тьюринга, правильно вычисляющая вычислимую функцию. Теорема о существовании машины Тьюринга, правильно вычисляющей вычислимую функцию.
   
10. 
    Примитивно рекурсивные функции. Примеры примитивно рекурсивных функций (с доказательствами).
    
11. 
    Группы, конечные группы, порядок группы. Подгруппа, нормальная подгруппа. Отношение эквивалентности по подгруппе, смежные классы, разложение группы по подгруппе, фактор-группа, индекс подгруппы в конечной группе. Теорема Лагранжа о порядке подгруппы конечной группы.
    
12. 
    Симметрическая группа перестановок Sn. Теорема Кэли.
    
13. 
    Кольца, коммутативные, ассоциативные кольца, кольца с единицей, целостные кольца, поля. Теорема о конечном целостном кольце.
    
14. 
    Характеристика кольца. Теорема о характеристике конечного поля.
    
15. 
    Теорема о фактор-кольце кольца целых чисел по модулю главного идеала (p). Поле вычетов по модулю p.
    
16. 
    Кольцо многочленов над конечным полем. Теорема о целостности кольца многочленов над конечным полем. Теорема о делении двух многочленов, теорема о наибольшем общем делителе двух многочленов (алгоритм Евклида).
    
17. 
    Неприводимый элемент кольца многочленов. Значение многочлена в точке, корень многочлена. Критерий неприводимости многочленов степени 2 или 3. Теорема о числе неприводимых нормированных многочленов над конечным полем (формулировка).
    
18. 
    Теорема о фактор-кольце кольца многочленов над конечным полем по модулю главного идеала (f). Конечное поле как фактор-кольцо кольца многочленов над конечным полем по модулю неприводимого многочлена. Операции сложения и умножения, приведение по модулю многочлена, алгоритм Евклида нахождения обратного элемента.
    
19. 
    Простое поле. Простое алгебраическое расширение поля присоединением к нему корня неприводимого над ним многочлена. Примеры.
    
20. 
    Частично упорядоченные множества. Длина и ширина конечных частично упорядоченных множеств. Булев куб, его длина и ширина.
    

Литература

1. 
   http://mathcyb.cs.msu.su/courses/dgdm.html
   
2. 
   Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
   
3. 
   Лидл, Нидеррайтер. Конечные поля. Том 1. М.: Мир, 1988.
   
4. 
   Ансель Ж. О числе монотонных булевых функций от n переменных. В кн. Кибернетический сборник. Новая серия. Вып. 5. М.: Мир, 1968, с. 53-57.
   
5. 
   Де Брейн Н. Дж. Теория перечисления Пойа. В сб. ст. Прикладная комбинаторная математика, под ред. Э. Бакенбаха. М.: Мир, 1966, с. 61-107.