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

Вопросы к экзамену по курсу

1. 
   Алгоритм распознавания полноты конечных систем функций k-значной логики.
   
2. 
   Теорема Кузнецова о функциональной полноте.
   
3. 
   Существенные функции. Леммы о существенных функциях: о трех наборах, основная и о квадрате.
   
4. 
   Критерий полноты Яблонского систем функций k-значной логики.
   
5. 
   Операции над о.-д. функциями. Замкнутость класса о.-д. функций относительно операций суперпозиции и обратной связи.
   
6. 
   Леммы о преобразовании периодических последовательностей о.-д. функцией. Несводимость операции обратной связи к операции суперпозиции.
   
7. 
   Леммы о преобразовании машинных кодов: основного в l-кратный, решетчатого в основной и квазиосновного в основной.
   
8. 
   Операция суперпозиции. Теорема о замкнутости класса вычислимых функций относительно операции суперпозиции.
   
9. 
   Операция примитивной рекурсии. Теорема о замкнутости класса вычислимых функций относительно операции примитивной рекурсии.
   
10. 
    Операция минимизации. Теорема о замкнутости класса вычислимых функций относительно операции минимизации.
    
11. 
    Класс примитивно-рекурсивных функций. Примитивная рекурсивность функции Пеано и ее обобщений. Классы частично-рекурсивных и общерекурсивных функций.
    
12. 
    Теорема о схеме одновременной примитивной рекурсии.
    
13. 
    Формула Клини. Теорема о соотношении классов частично-рекурсивных и вычислимых функций.
    
14. 
    Кольцо многочленов над полем. Теорема о делении многочленов с остатком. Делимость многочленов. Теорема о наибольшем общем делителе двух многочленов.
    
15. 
    Неприводимость многочленов над полем. Теорема о неприводимом делителе произведения многочленов. Теорема о каноническом разложении многочлена на неприводимые сомножители.
    
16. 
    Теорема о фактор-кольце кольца целых чисел.
    
17. 
    Теорема о фактор-кольце кольца многочленов над простым полем.
    
18. 
    Теорема Анселя о разбиении куба Bn на цепи. Теорема об оценках числа монотонных булевых функций.
    

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

Литература

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

1. 
   Записать функцию k-значной логики в I-й или II-й форме, построить ее полином или доказать, что она не задается полиномом по mod k; исследовать систему функций k-значной логики на полноту.
   
2. 
   Построить диаграмму Мура о.-д. функции; доказать полноту системы о.-д. функций.
   
3. 
   Применить операцию примитивной рекурсии или операцию минимизации; доказать примитивную рекурсивность функции.
   
4. 
   Построить группу перестановок и найти ее цикловой индекс; найти число неэквивалентных раскрасок относительно группы перестановок.
   
5. 
   Исследовать многочлен на неприводимость; найти сумму, произведение элементов или обратный элемент в конечном поле.
   

Литература

1. 
   Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М., Физматлит, 2004. Гл. III 1.11, 2.7, 2.20, 2.21, 2.22, 2.23; гл. IV 2.1, 2.17, 2.18; гл. V 2.1, 2.2, 2.3, 2.4, 2.5; гл. VIII 4.1, 4.3, 4.4, 4.9, 4.10.
   
2. 
   Лидл Р. Нидеррайтер Г. Конечные поля. Том 1. М., Мир, 1988.