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



Скачать 47.63 Kb.
Дата24.11.2012
Размер47.63 Kb.
ТипВопросы к экзамену
Вопросы к экзамену по курсу

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

(318, 319 группы, осенний семестр 2011-2012 учебного года)

(лектор – доцент С.Н. Селезнева)
В билете два теоретических вопроса: первый из части А, второй из части В. Задач в билете нет. Задачи могут быть предложены экзаменатором в качестве дополнительных вопросов.
Часть А. Вопросы без подготовки, при ответе на которые можно пользоваться конспектами. Определения и формулировки теорем формулируются до открытия конспекта.


  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.

Похожие:

Вопросы к экзамену по курсу «Дополнительные главы дискретной математики» iconВопросы к экзамену по курсу «Дополнительные главы дискретной математики»
Функции k-значной логики. Формулы, i-я и ii-я формы. Полные системы. Полнота системы Поста. Функция Вебба
Вопросы к экзамену по курсу «Дополнительные главы дискретной математики» iconВопросы к экзамену по курсу «Дополнительные главы дискретной математики»
A. Вопросы, при ответе на которые, можно пользоваться конспектами (некоторое время, при этом ответ не состоит в чтении конспекта)....
Вопросы к экзамену по курсу «Дополнительные главы дискретной математики» iconВопросы к экзамену по курсу «Дополнительные главы дискретной математики»
В билете два теоретических вопроса: первый из части А, второй из части В. Задач в билете нет. Задачи могут быть предложены экзаменатором...
Вопросы к экзамену по курсу «Дополнительные главы дискретной математики» iconПрограмма курса Дополнительные главы дискретной математики для групп 318, 319 кафедры математической кибернетики
«Дополнительные главы дискретной математики» (для студентов 3-го курса 2-го потока). В нее включены разделы, относящиеся к конечнозначным...
Вопросы к экзамену по курсу «Дополнительные главы дискретной математики» iconМетодические указания к практическим занятиям и самостоятельной работе студентов по курсу математики для студентов всех специальностей
Дополнительные главы математики: теория функций комплексной переменной, операционное исчисление, уравнения в частных производных
Вопросы к экзамену по курсу «Дополнительные главы дискретной математики» iconВопросы к экзамену по курсу высшей математики для студентов 1-го курса географического факультета
Предмет высшей математики. Исторические сведения. Понятие о роли математики в географии. Математическое моделирование. Понятие о...
Вопросы к экзамену по курсу «Дополнительные главы дискретной математики» iconЭкзаменационные вопросы по курсу дискретной математики
Понятие множества (определение, кардинальное число, булеан, способы задания множеств, диаграммы Венна). Операции над множествами....
Вопросы к экзамену по курсу «Дополнительные главы дискретной математики» iconЭлементы дискретной математики
П. А. Корнилов, Н. И. Никулина, Семенова О. Г. Элементы дискретной математики. Учебное пособие. Ярославль: Изд-во ягпу им. К. Д....
Вопросы к экзамену по курсу «Дополнительные главы дискретной математики» iconДополнительные вопросы к экзамену по курсу "Оптические свойства молекул"
Вывести формулу закона Бугера-Ламберта-Бэра и указать условия ее применимости. Какие процессы приводят к уменьшению интенсивности...
Вопросы к экзамену по курсу «Дополнительные главы дискретной математики» iconВопросы к экзамену по курсу "Введение в языкознание"
Вопросы к экзамену по курсу "Введение в языкознание" для специальности «Переводчик в сфере профессиональной коммуникации»
Разместите кнопку на своём сайте:
ru.convdocs.org


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