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



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

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


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

(осенний семестр 2008-2009 уч. г., группы 318, 319,

лектор – доцент С. Н. Селезнева)


  1. Конечнозначные логики




    1. Функции k-значной логики. Формулы, I-я и II-я формы. Полные системы. Полнота системы Поста. Функция Вебба.

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

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

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

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

    6. Особенности k-значных логик. Теорема Ю. И. Янова. Теорема А. А. Мучника.

    7. Теорема о полноте системы полиномов в Pk.




  1. Ограниченно-детерминированные функции




    1. Детерминированные функции (д. функции). Задание д. функций нагруженными деревьями. Вес д. функции.

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

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

    4. Полнота систем о.-д. функций. Существование аналога функции Шеффера

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




  1. Вычислимые функции




    1. Машины Тьюринга (МТ). Машинные коды: основной, l-кратный, решетчатый и квазиосновной. Задача поиска левой единицы в основном коде.

    2. Лемма о моделировании на решетке.

    3. Лемма о преобразовании основного кода в l-кратный.

    4. Лемма о преобразовании решетчатого кода в основной.

    5. Вычислимые функции. Лемма о существовании МТ, правильно вычисляющей вычислимую функцию.

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

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

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

    9. Класс примитивно рекурсивных функций. Некоторые примитивно-рекурсивные функции.




    1. Пеановская функция, ее примитивная рекурсивность. Схема одновременной примитивной рекурсии.

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





  1. Конечные поля




    1. Алгебраическая операция, нейтральный элемент, симметричный элемент. Группа, абелева группа. Циклическая группа, образующий элемент группы. Конечная группа, порядок группы, таблица Кэли. Примеры.

    2. Подгруппа. Теорема об отношении эквивалентности по подгруппе. Смежные классы по подгруппе, разложение группы по подгруппе. Индекс подгруппы в группе, теорема о порядке конечной группы.

    3. Нормальная подгруппа. Фактор-группа группы по нормальной подргуппе.

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

    5. Двусторонний идеал кольца, главный идеал кольца. Фактор-кольцо кольца по модулю идеала. Теорема о фактор-кольце Z/(p) (число p – простое).

    6. Характеристика кольца. Теорема характеристике конечного поля.

    7. Максимальный идеал кольца. Теорема о максимальном идеале.

    8. Простой идеал кольца. Теорема о простом идеале.

    9. Обратимые, ассоциированные, простые элементы кольца. Кольцо главных идеалов. Теорема о кольце главных идеалов.

    10. Многочлен над кольцом, степень многочлена. Сумма, произведение двух многочленов. Кольцо многочленов.

    11. Деление многочленов. Теорема о кольце многочленов как о кольце главных идеалов.

    12. Неприводимые многочлены. Описание фактор-кольца кольца многочленов по модулю главного идеала, порожденного неприводимым многочленом. Приведение по модулю многочлена. Примеры.

    13. Значение многочлена в точке. Корень многочлена, критерий корня. Критерий неприводимости многочлена степени 2 или 3.




  1. Комбинаторика



    1. Симметрическая группа перестановок. Теорема Кэли об изоморфизме конечной группы подходящей подгруппе Sn. Теорема Лагранжа о порядке подгруппы конечной группы.

    2. Отношение эквивалентности по подгруппе Sn. Орбита элемента, стабилизатор элемента. Лемма об индексе стабилизатора элемента в группе.

Лемма Бернсайда о числе орбит по группе.

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

    2. Частично-упорядоченные множества (ЧУМ). Сравнимые и несравнимые элементы, линейный порядок. Минимальный (максимальный), наименьший (наибольший) элементы. Диаграмма Хассе. Цепь, антицепь. Длина и ширина ЧУМ. Покрытие ЧУМ. Теорема Дилуорса о мощности минимального покрытия конечного ЧУМ.

    3. Ранжированные ЧУМ. Куб Bn. Теорема о ширине куба Bn.

    4. Теорема Ж. Анселя о покрытии куба Bn цепями.

    5. Монотонные булевы функции. Нижняя и верхняя оценки числа монотонных булевых функций от n переменных.


Литература





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

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

  3. Айгнер М. Комбинаторная теория. М., Мир, 1982.

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

  5. Холл М. Комбинаторика. М., Мир, 1970.

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

Похожие:

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


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