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




Скачать 38.86 Kb.
НазваниеВопросы к экзамену по курсу «Дополнительные главы дискретной математики»
Дата публикации04.04.2013
Размер38.86 Kb.
ТипВопросы к экзамену
litcey.ru > Информатика > Вопросы к экзамену
Вопросы к экзамену по курсу

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

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

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


  1. Теорема о существовании алгоритма распознавания полноты конечных систем функций k-значной логики.

  2. Теорема Кузнецова о функциональной полноте систем функций k-значной логики.

  3. Лемма о трех наборах для функций k-значной логики.

  4. Критерий Яблонского о полноте систем функций k-значной логики.

  5. Теорема Янова. Теорема Мучника. Следствия из них.

  6. Леммы о преобразовании периодической последовательности о.-д. функцией в периодическую последовательность. Теорема о несуществовании конечных полных систем в классе о.-д. функций с операцией суперпозиции.

  7. Теорема о конечной полной системе и теорема об аналоге шефферовой функции в классе k-значных о.-д. функций с операциями суперпозиции и обратной связи. Теорема о несводимости операции обратной связи к операции суперпозиции.

  8. Операция суперпозиции для функций счетнозначной частичной логики. Замкнутость класса вычислимых функций относительно операции суперпозиции.

  9. Операция примитивной рекурсии для функций счетнозначной частичной логики. Замкнутость класса вычислимых функций относительно операции примитивной рекурсии.

  10. Операция минимизации для функций счетнозначной частичной логики. Замкнутость класса вычислимых функций относительно операции минимизации.

  11. Функция Пеано и ее обобщения, их примитивная рекурсивность. Теорема о схеме одновременной примитивной рекурсии.

  12. Теорема Клини. Теорема о совпадении классов вычислимых и частично рекурсивных функций.

  13. Эквивалентность элементов по подгруппе симметрической группы перестановок Sn. Орбита и стабилизатор элемента. Теорема о мощности орбиты. Лемма Бернсайда.

  14. Раскраски элементов. Эквивалентность раскрасок относительно подгруппы симметрической группы перестановок Sn. Теорема Пойа.

  15. Кольцо многочленов над конечным полем. Теорема о делении двух многочленов, теорема о наибольшем общем делителе двух многочленов (алгоритм Евклида). Теорема о целостности кольца многочленов над конечным полем.

  16. Теорема о разбиении булева куба на цепи Анселя. Оценки количества монотонных булевых функций от n переменных. Сложность расшифровки монотонной булевой функции от n переменных.


Часть В. Вопросы почти без подготовки и без конспектов.


  1. Функция k-значной логики. Элементарные функции k-значной логики. Теорема о числе функций k-значной логики, зависящих от n переменных.

  2. Теоремы о 1-й и 2-й формах записи функций k-значной логики.

  3. Теорема о полноте системы Поста функций k-значной логики. Функция Вебба.

  4. Основная лемма для функций k-значной логики.

  5. Лемма о квадрате для функций k-значной логики.

  6. Критерий шефферовой функции k-значной логики.

  7. Теорема о задании функций k-значной логики полиномами по модулю k.

  8. Детерминированная функция (д. функция). Мощность класса д. функций. Операции суперпозиции и обратной связи для д. функций. Замкнутость класса д. функций относительно операций суперпозиции и обратной связи.

  9. Ограниченно-детерминированная функция (о.-д. функция). Мощность класса о.-д. функций. Операции суперпозиции и обратной связи для о.-д. функций. Замкнутость класса о.-д. функций относительно операций суперпозиции и обратной связи.

  10. Функция счетнозначной частичной логики, вычислимая по Тьюрингу. Мощность класса вычислимых функций. Машина Тьюринга, правильно вычисляющая вычислимую функцию. Теорема о существовании машины Тьюринга, правильно вычисляющей вычислимую функцию.

  11. Примитивно рекурсивная функция. Примеры примитивно рекурсивных функций (с доказательствами).

  12. Группы, конечные группы, порядок группы. Подгруппа, нормальная подгруппа. Отношение эквивалентности по подгруппе, смежные классы, разложение группы по подгруппе, фактор-группа, индекс подгруппы в конечной группе. Теорема Лагранжа о порядке подгруппы конечной группы.

  13. Симметрическая группа перестановок Sn. Теорема Кэли.

  14. Кольца, коммутативные, ассоциативные кольца, кольца с единицей, целостные кольца, поля. Теорема о конечном целостном кольце.

  15. Конечные поля. Теорема о характеристике конечного поля.

  16. Идеалы кольца, главные идеалы коммутативных колец с единицей. Фактор-кольцо по модулю идеала.

  17. Теорема о фактор-кольце кольца целых чисел по модулю главного идеала (m). Поле вычетов по модулю p.

  18. Неприводимый элемент кольца многочленов. Главный идеал по модулю многочлена, приведение многочлена по модулю многочлена. Теорема о фактор-кольце кольца многочленов над конечным полем по модулю многочлена.

  19. Конечное поле как фактор-кольцо кольца многочленов над конечным полем по модулю неприводимого многочлена. Операции сложения и умножения, алгоритм нахождения обратного элемента.

  20. Частично упорядоченные множества. Длина и ширина конечных частично упорядоченных множеств. Булев куб, его длина и ширина.



Литература





  1. Яблонский С. В. Введение в дискретную математику. М., Высшая школа, 2001.

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

  3. Ансель Ж. О числе монотонных булевых функций от n переменных. В кн. Кибернетический сборник. Новая серия. Вып. 5. М., Мир, 1968, с. 53-57.

  4. Де Брейн Н. Дж. Теория перечисления Пойа. В сб. ст. Прикладная комбинаторная математика, под ред. Э. Бакенбаха. М., Мир, 1966, с. 61-107.

Похожие:

Вопросы к экзамену по курсу «Дополнительные главы дискретной математики» iconВопросы к экзамену по курсу «Дополнительные главы дискретной математики»
Функции k-значной логики. Формулы, i-я и ii-я формы. Полные системы. Полнота системы Поста. Функция Вебба
Вопросы к экзамену по курсу «Дополнительные главы дискретной математики» iconВопросы к экзамену по курсу «Дополнительные главы дискретной математики»
A. Вопросы, при ответе на которые, можно пользоваться конспектами (некоторое время, при этом ответ не состоит в чтении конспекта)....
Вопросы к экзамену по курсу «Дополнительные главы дискретной математики» iconВопросы к экзамену по курсу «Дополнительные главы дискретной математики»
В билете два теоретических вопроса: первый из части А, второй из части В. Задач в билете нет. Задачи могут быть предложены экзаменатором...
Вопросы к экзамену по курсу «Дополнительные главы дискретной математики» iconВопросы к экзамену по курсу «Дополнительные главы дискретной математики»
В билете два теоретических вопроса: первый из части А, второй из части В. Задач в билете нет. Задачи могут быть предложены экзаменатором...
Вопросы к экзамену по курсу «Дополнительные главы дискретной математики» iconПрограмма курса Дополнительные главы дискретной математики для групп...
«Дополнительные главы дискретной математики» (для студентов 3-го курса 2-го потока). В нее включены разделы, относящиеся к конечнозначным...
Вопросы к экзамену по курсу «Дополнительные главы дискретной математики» iconВопросы к экзамену по курсу "Основы дискретной математики"
Сочетания, их число и рекуррентные формулы для них. Биномиальные коэффициенты, некоторые тождества, связанные с ними
Вопросы к экзамену по курсу «Дополнительные главы дискретной математики» iconВопросы к экзамену по курсу «Основы дискретной математики»
А – ответ без подготовки по любым материалам (конспекты, книжки, распечатки лекций и т д.), проверяется понимание доказательств;...
Вопросы к экзамену по курсу «Дополнительные главы дискретной математики» iconВопросы к коллоквиуму по курсу "Основы дискретной математики"
Граф (псевдограф, мультиграф). Формула Эйлера о сумме степеней вершин в графе. Изоморфизм графов
Вопросы к экзамену по курсу «Дополнительные главы дискретной математики» iconВопросы к экзамену по дискретной математике 2007/2008
Бинарные отношения. Рефлексивность, симметричность, антисимметричность, транзитивность
Вопросы к экзамену по курсу «Дополнительные главы дискретной математики» iconПрограмма дополнительного образования «Дополнительные главы курса математики»
Бражникова Ирина Митрофановна, методист Центра моудпо оценки качества образования
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
litcey.ru
Главная страница