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



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

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


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

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

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


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

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

  3. Существенные функции. Леммы о существенных функциях: о трех наборах, основная и о квадрате.

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

  5. Операции над о.-д. функциями. Замкнутость класса о.-д. функций относительно операций суперпозиции и обратной связи.

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

  7. Леммы о преобразовании машинных кодов: основного в l-кратный, решетчатого в основной и квазиосновного в основной.

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

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

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

  11. Класс примитивно-рекурсивных функций. Примитивная рекурсивность функции Пеано и ее обобщений. Классы частично-рекурсивных и общерекурсивных функций.

  12. Теорема о схеме одновременной примитивной рекурсии.

  13. Формула Клини. Теорема о соотношении классов частично-рекурсивных и вычислимых функций.

  14. Кольцо многочленов над полем. Теорема о делении многочленов с остатком. Делимость многочленов. Теорема о наибольшем общем делителе двух многочленов.

  15. Неприводимость многочленов над полем. Теорема о неприводимом делителе произведения многочленов. Теорема о каноническом разложении многочлена на неприводимые сомножители.

  16. Теорема о фактор-кольце кольца целых чисел.

  17. Теорема о фактор-кольце кольца многочленов над простым полем.

  18. Теорема Анселя о разбиении куба Bn на цепи. Теорема об оценках числа монотонных булевых функций.


Часть B. Вопросы, при ответе на которые пользоваться конспектами не предполагается. Ответ почти без подготовки.


  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.

Похожие:

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


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