Вопросы к экзамену по курсу «Дискретная математика» (все 3 потока) Лекторы: В. Б. Алексеев, С. С. Марченков, Д. С. Романов; весна 200 8 года. В билете 2 вопроса (один из части а и один из части В) и задача. Часть а ответ без




Скачать 27.66 Kb.
НазваниеВопросы к экзамену по курсу «Дискретная математика» (все 3 потока) Лекторы: В. Б. Алексеев, С. С. Марченков, Д. С. Романов; весна 200 8 года. В билете 2 вопроса (один из части а и один из части В) и задача. Часть а ответ без
Дата публикации03.06.2013
Размер27.66 Kb.
ТипВопросы к экзамену
skachate.ru > Математика > Вопросы к экзамену
Вопросы к экзамену по курсу «Дискретная математика» (все 3 потока)

Лекторы: В. Б. Алексеев, С. С. Марченков, Д. С. Романов;

весна 2008 года.
В билете 2 вопроса (один из части А и один из части В) и задача.
Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определение и формулировки – без конспектов.


  1. Двойственность. Класс самодвойственных функций, его замкнутость.

  2. Лемма о нелинейной функции.

  3. Теорема Поста о полноте системы функций алгебры логики.

  4. Теорема о предполных классах.

  5. Деревья. Свойства деревьев.

  6. Теорема о раскраске планарных графов в 5 цветов.

  7. Алфавитное кодирование. Теорема Маркова о взаимной однозначности алфавитного кодирования.

  8. Неравенство Макмиллана.

  9. Существование префиксного кода с заданными длинами кодовых слов.

  10. Теорема редукции.

  11. Коды с исправлением r ошибок. Оценка функции .

  12. Коды Хэмминга. Оценка функции .

  13. Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.

  14. Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.

  15. Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.

  16. Теорема Мура.


Часть В – ответ без конспектов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).


  1. Функции алгебры логики. Равенство функций. Тождества для элементарных функций.

  2. Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.

  3. Полные системы. Примеры полных систем (с доказательством полноты).

  4. Теорема Жегалкина о представимости функции алгебры логики полиномом.

  5. Понятие замкнутого класса. Замкнутость классов

  6. Класс монотонных функций, его замкнутость.

  7. Лемма о несамодвойственной функции.

  8. Лемма о немонотонной функции.

  9. Теорема о максимальном числе функций в базисе в алгебре логики.

  10. Основные понятия теории графов. Изоморфизм графов. Связность.

  11. Корневые деревья. Верхняя оценка их числа.

  12. Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.

  13. Планарные (плоские) графы. Формула Эйлера.

  14. Доказательство непланарности графов K5 и K3,3 Теорема Понтрягина-Куратовского (доказательство в одну сторону).

  15. Оптимальные коды, их свойства.

  16. Схемы из функциональных элементов. Реализация функций алгебры логики схемами.

  17. Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.

  18. Сумматор. Верхняя оценка сложности сумматора. Вычитатель.


По результатам контрольных работ по каждой из четырех тем (алгебра логики, графы, коды, автоматы) у каждого студента должна стоять одна из трех оценок — 0, 1/2 или 1. Оценка 0 означает, что на экзамене студент должен решить дополнительную задачу по данной теме, оценка 1/2, — что студент решает задачу по данной теме только в случае, если она выпадает в билете. Оценка 1 означает, что на экзамене студент не должен решать по данной теме как дополнительные задачи, так и задачу из билета. Дополнительные задачи решаются до выбора билета. Студенты, не решившие достаточное количество дополнительных задач, удаляются с экзамена с оценкой «неудовлетворительно», количество решенных задач может ограничить сверху оценку, получаемую на экзамене.
Задачи решаются без конспектов.
После ответа на билет возможна прогонка по всему материалу (определения, формулировки, идеи доказательств) и добавочные задачи на любые темы (не путать с дополнительными!).

Похожие:

Вопросы к экзамену по курсу «Дискретная математика» (все 3 потока) Лекторы: В. Б. Алексеев, С. С. Марченков, Д. С. Романов; весна 200 8 года. В билете 2 вопроса (один из части а и один из части В) и задача. Часть а ответ без iconВопросы к экзамену по курсу «Дискретная математика» в билете 2 вопроса...
А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т д.). Проверяется насколько осознаны все доказательства...
Вопросы к экзамену по курсу «Дискретная математика» (все 3 потока) Лекторы: В. Б. Алексеев, С. С. Марченков, Д. С. Романов; весна 200 8 года. В билете 2 вопроса (один из части а и один из части В) и задача. Часть а ответ без iconВопросы к экзамену по курсу "Дискретная математика", 2 семестр, группа зп21
В билете вопросы могут быть разбиты на более мелкие или, наоборот, объединены. Ответ на любой вопрос должен включать все необходимые...
Вопросы к экзамену по курсу «Дискретная математика» (все 3 потока) Лекторы: В. Б. Алексеев, С. С. Марченков, Д. С. Романов; весна 200 8 года. В билете 2 вопроса (один из части а и один из части В) и задача. Часть а ответ без iconЭкзаменационные материалы Экзаменационные вопросы Пояснительная записка...
Они устно отвечают по билетам. Билеты к экзамену за 1 семестр содержат два вопроса: один – по истории первобытного общества, другой...
Вопросы к экзамену по курсу «Дискретная математика» (все 3 потока) Лекторы: В. Б. Алексеев, С. С. Марченков, Д. С. Романов; весна 200 8 года. В билете 2 вопроса (один из части а и один из части В) и задача. Часть а ответ без icon8. Павлович (5 8) Что надо сделать. Найти ответ на свои вопросы....
...
Вопросы к экзамену по курсу «Дискретная математика» (все 3 потока) Лекторы: В. Б. Алексеев, С. С. Марченков, Д. С. Романов; весна 200 8 года. В билете 2 вопроса (один из части а и один из части В) и задача. Часть а ответ без iconОформление сносок, ссылок на литературные источники и нормативные акты
Ответ на каждый вопрос домашнего задания состоит из введения, основной части и заключения. Все части ответа на вопрос должны быть...
Вопросы к экзамену по курсу «Дискретная математика» (все 3 потока) Лекторы: В. Б. Алексеев, С. С. Марченков, Д. С. Романов; весна 200 8 года. В билете 2 вопроса (один из части а и один из части В) и задача. Часть а ответ без iconУчебно-методический комплекс по дисциплине «Дискретная математика и математическая логика»
Рабочей учебной программы по курсу «Дискретная математика и математическая логика», утверждённой деканом факультета непрерывного...
Вопросы к экзамену по курсу «Дискретная математика» (все 3 потока) Лекторы: В. Б. Алексеев, С. С. Марченков, Д. С. Романов; весна 200 8 года. В билете 2 вопроса (один из части а и один из части В) и задача. Часть а ответ без iconОсновы государственного и муниципального управления
Вопросы в письменном контрольном задании сгруппированы по темам пяти тем. Тема 2 разбита на 2 части. Вам необходимо дать ответ на...
Вопросы к экзамену по курсу «Дискретная математика» (все 3 потока) Лекторы: В. Б. Алексеев, С. С. Марченков, Д. С. Романов; весна 200 8 года. В билете 2 вопроса (один из части а и один из части В) и задача. Часть а ответ без iconЛибо из общей части вопрос 18, либо из особенной части вопрос 23...
Вариант курсового проекта выбирается по общим правилам либо из Общей части, либо из Особенной части
Вопросы к экзамену по курсу «Дискретная математика» (все 3 потока) Лекторы: В. Б. Алексеев, С. С. Марченков, Д. С. Романов; весна 200 8 года. В билете 2 вопроса (один из части а и один из части В) и задача. Часть а ответ без iconВ. П. Некрасов дискретная математика
Методические указания предназначены для выполнения домашней контрольной работы (дкр) по дисциплине «Дискретная математика»
Вопросы к экзамену по курсу «Дискретная математика» (все 3 потока) Лекторы: В. Б. Алексеев, С. С. Марченков, Д. С. Романов; весна 200 8 года. В билете 2 вопроса (один из части а и один из части В) и задача. Часть а ответ без iconВ. П. Некрасов дискретная математика
Методические указания предназначены для выполнения домашней контрольной работы (дкр) по дисциплине «Дискретная математика»

Вы можете разместить ссылку на наш сайт:
Школьные материалы


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