Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
Реферат может быть подготовлен по философским, методологическим или историческим проблемам диссертационной специальности (например физики, химии, соци...полностью>>
'Документ'
4. Вколотые в изделие булавки должны быть направлены острием в одну сторону. Ножницы во время работы должны лежать на столе под рукой с сомкнутыми лез...полностью>>
'Документ'
Артём 9А Фролова ТС 100 5 Призёр 1 Олехногвич Максим 7 Участник 13 Шатрова Анна 75 Победитель 14 Подойникова Яна 10 А Фролова ТС 100 80 Победитель 15 ...полностью>>
'Документ'
Об утверждении Положения о порядке проведения аттестации педагогических работников в целях подтверждения соответствия занимаемым ими должностям в МБДО...полностью>>

Главная > Программа

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

министерство образования и науки российской федерации

московский физико-технический институт

(государственный унивеситет)

УТВЕРЖДАЮ

Проректор по учебной работе

_____________Д.А. Зубцов

28 июня 2013 г.

ПРОГРАММА

по дисциплине: Алгебра логики, комбинаторика, теория графов

по направлению: 010900 «Прикладные математика и физика»

факультет: ФУПМ, ФРТК

кафедра: математических основ управления

курс: I

семестры: 1

Трудоёмкость: базовая часть – 3 зач. ед.

вариативная часть – 2 зач. ед.

по выбору студента – 1 зач. ед.

лекции – 34 часа Экзамен – нет

практические (семинарские)

занятия – 34 часа Диф. зачет – 1 семестр

лабораторные занятия – нет

Самостоятельная работа – 10 час

ВСЕГО ЧАСОВ – 68

Программу и задание составили:

член-корр. РАН Ю.А. Флеров, к.ф.-м.н. О.С. Федько,

ассистент А.В. Зухба, ассистент А.В. Романенко

Программа принята на заседании

кафедры математических основ управления

26 апреля 2013 года

Заведующий кафедрой С. А. Гуз

I. Элементы алгебры логики

1. Функции алгебры логики. Табличное задание функций. Элементарные функции, их свойства, таблица операций. Коммутативность, ассоциативность, дистрибутивность элементарных функций.

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

3. Функциональная полнота систем функций алгебры логики. Замкнутые классы. Пять предполных замкнутых классов Т0, T1, L, S, М. Теорема о функции, двойственной к суперпозиции. Критерий функциональной полноты систем функций алгебры логики (теорема Поста). Основная лемма. Лемма о несамодвойственной функции. Лемма о немонотонной функции. Лемма о нелинейной функции. Следствия из критерия полноты.

II. Комбинаторные методы дискретной математики

1. Предмет комбинаторики. Комбинаторные задачи о числе функций, слов в алфавите и размещений объектов по ячейкам при различных ограничениях (mn, [m]n, [m]n, [m]n/n!, Pn).

2. Числа Стирлинга первого рода, рекуррентное соотношение для них.

3. Биномиальные коэффициенты, производящая функция для них, основные комбинаторные тождества. Полиномиальные коэффициенты, производящая функция для них, основные комбинаторные тождества.

4. Число разбиений n объектов на m классов. Числа Стирлинга второго рода. Рекуррентное соотношение для S(n, k). Разложение степени xn в базисе {[x]k}. Числа Белла разбиений множества на непересекающиеся подмножества, рекуррентное соотношение для чисел Белла.

5. Логические методы комбинаторного анализа. Принцип включений-исключений. Задача о числе беспорядков, задача о числе сюръективных отображений конечных множеств. Системы представителей множеств. Системы различных представителей (с.р.п.). Необходимое и достаточное условие существования с.р.п. Алгоритм построения с.р.п. для заданной системы множеств. Системы одновременных представителей.

III. Элементы теории графов

1. Определение графа. Неориентированные и ориентированные графы. Изоморфные графы. Полные ориентированные и неориентированные графы. Локальные степени вершин. Число вершин нечетной степени в конечном графе. Машинное представление графов. Матрица инциденций. Матрица смежности (вершин). Список пар, список инцидентности.

2. Пути (маршруты, цепи) в графе, простые пути, циклы. Связность. Теорема о связности двух вершин, имеющих нечетную локальную степень. Максимальное число ребер в графе с n вершинами и k-связными компонентами.

3. Деревья. Связанность любых двух вершин дерева единственным простым путем. Изображение дерева. Концевые (висячие) вершины и концевые (висячие) ребра дерева. Теорема о числе различных деревьев с данными n вершинами.

4. Эйлеровы пути и циклы, теорема о существовании эйлеровых путей и циклов в графе. Алгоритм построения эйлеровых циклов. Гамильтоновы пути и циклы. Пути, имеющие тип цикла. Достаточное условие для того, чтобы полный простой путь имел тип цикла. Связь между наличием в связном графе гамильтоновых циклов и длиной максимальных простых путей в нем.

5. Нахождение кратчайших путей в ориентированном графе от фиксированной вершины до всех остальных вершин (случай неотрицательных весов ребер).

Литература

1. Журавлев Ю.И., Флеров Ю.А., Федько О.С. Дискретный анализ. Комбинаторика. Алгебра логики. Теория графов: Учеб. пособие / Ю.И.Журавлев, Ю.А.Флеров, О.С.Федько. – М.: МФТИ, 2012.

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

3. Харари Ф. Теория графов. Изд. 2-е. – М.: Эдиториал УРРС, 2003.

4. Андерсон Джеймс А. Дискретная математика и комбинаторика. – М.: Вильямс, 2003.

ЗАДАНИЕ

Номера задач указаны по сборнику «Сборник задач по дискретному анализу. Комбинаторика. Элементы алгебры логики. Теория графов» / Ю.И. Журавлев, Ю.А. Флеров, О.С. Федько, Т.М. Дадашев. – М.: МФТИ, 2000.

Глава 1

1.8, Т1, 2.9, 2.12(1,4,5), 2.17, 2.18*, 2.21, 2.35(1,2), 2.46(5,7,11,15), 3.5(2), 3.9(1,2), 3.10(1), 3.13(5,6*), 3.16, 3.48(а), 4.5, 4.6, 4.7, 4.11, 4.12, 4.23.

Т1. Сколько слов длины можно составить из букв алфавита если выполняются все указанные условия: 1) буква присутствует в слове и стоит на 2м месте; 2) буква обязательно присутствует в слове; 3) буквы и присутствуют в слове и стоят подряд в любом порядке; 4) буква встречается ровно 2 раза, а остальные буквы присутствуют не более 1 раза.

Глава 2

1.5, 1.8, 1.12, 1.20, 1.28, 2.4, 2.11, 2.12, 2.23, 2.26, 2.35

Глава 3

1.6, 1.17, 2.5, 3.24, 3.8, 4.6, 4.10(1), 4.19

Срок сдачи задания – первая неделя декабря.

Подписано в печать 28.06.2013. Формат 60 ´ 84.

Усл. печ. л. 1,0. Тираж 520 экз. Заказ №

Федеральное государственное автономное образовательное учреждение

высшего профессионального образования

«Московский физико-технический институт

(государственный университет)»

Отдел оперативной полиграфии «Физтех-полиграф»

141700, Московская обл., г. Долгопрудный, Институтский пер., 9

E-mail: rio@



Похожие документы:

  1. Цифровые образовательные ресурсы онлайн

    Реферат
    ... Логика и комбинаторика – 5 уроков; 3 класс: Алгоритмы – 5 уроков; Объекты – 5 уроков; Множества и графы ... Алгебра. 7 класс. Курс "Алгебра ... идеях, направлениях в ... дисциплин. Для начала, мы рекомендуем Вам посетить Экскурсию по интерактивной программе ...
  2. Программа дисциплины Математическая логика и теория алгоритмов  для направления 035800. 62 «Фундаментальная и прикладная лингвистика» подготовки бакалавра Автор программы

    Программа дисциплины
    ... Факультет гуманитарных наук Программа дисциплины Математическая логика и теория алгоритмов для направления 035800.62 « ... 2 1 6 2 Логика высказываний 4 4 10 3 Булева алгебра 1 1 4 4 Логика предикатов 5 5 10 5 Графы. Алгоритмы на графах 6 6 12 6 ...
  3. Аннотация к рабочей программе дисциплины «Математическая логика и теория алгоритмов» по направлению 230100. 62 Информатика и вычислительная техника

    Документ
    Аннотация к рабочей программе дисциплины «Математическая логика и теория алгоритмов» по направлению 230100.62 Информатика и ... Элементы комбинаторики. Основы теории множеств. Элементы теории графов. В результате изучения дисциплины бакалавр должен ...
  4. В. М. Батрак образовательная программа

    Образовательная программа
    ... ЭЛЕМЕНТЫ ЛОГИКИ, КОМБИНАТОРИКИ, СТАТИСТИКИ И ТЕОРИИ ВЕРОЯТНОСТЕЙ ... использованием аппарата алгебры; описания ... списки, деревья, графы. Восприятие, запоминание ... программ изучается в рамках одного из трех направлений ... работ по социальным дисциплинам. В ...
  5. Методические указания по выполнению контрольной работы по дисциплине «Математическая логика»

    Методические указания
    ... по выполнению контрольной работы по дисциплине «Математическая логика» Направление ... (5.2), P – программа (5.3). Пример ... комбинаторика. ... по теории графов / Емеличев В.А., Мельников О.И.- М.: Наука, 1990. -384 с. -ISBN 5-291-01658-5 Лекции по теории графов ...

Другие похожие документы..