НОУ ИНТУИТ | Повышение квалификации

Опубликована: 05.04.2011 | Уровень: для всех | Стоимость: 490.00 руб. | Длительность: 14 дней

Темы: Алгоритмы и дискретные структуры, Дискретные структуры, Алгоритмы

Дискретный анализ содержит материал, излагаемый в первом семестре курса дискретного анализа: комбинаторика, элементы алгебры логики, начальные сведения теории графов. В курс включены как основополагающие понятия и результаты перечисленных разделов, так и материал повышенной трудности, часто в лекциях не излагаемый. Курс предназначен для изучения студентами соответствующих разделов программы основ дискретного анализа.

Математическая экспансия - вторжение математики в новые, ранее ею не контролируемые территории - привела к использованию математических методов представителями как естественнонаучных, так и гуманитарных областей знания. Все это сделало понимание путей использования математического аппарата важнейшим элементом общей культуры, а владение терминами «математическая структура» и «математическая модель» - необходимыми атрибутами образованного человека. Именно поэтому в курс включены три основных раздела дискретного анализа: алгебра логики, комбинаторика, теория графов. Дисциплина является необходимым языковым и методологическим основанием для формирования принципов и методов дискретного мышления. Дисциплина направлена на развитие навыков формализации и организации понятий, необходимых при изучении информатики и математического моделирования и при решении теоретических и прикладных задач. Дискретные математические объекты, теория и методы построения математических и прикладных дискретных моделей лежат в основе профессиональных навыков и умений грамотного специалиста в области прикладной информатики и составляют необходимую часть ремесла грамотного исследователя, аналитика, практика, формирует их профессиональную культуру.

Цель: Познакомить студента с основными определениями, задачами и методами этих разделов, подготовить каждого студента к пониманию смысла и к овладению техникой выполнения дискретных математических операций настолько же, насколько изучающие математический анализ подготовлены к применению непрерывных операций (типа дифференцирования и интегрирования).

Вам нравится?

| Поделиться |

Поддержать

Занятие	Заголовок <<	Дата изучения
	Экзамен экстерном	-
Лекция 1	Функции алгебры логики Предмет алгебры логики. Элементарные высказывания. Элементарные логические операции (дизъюнкция, конъюнкция, импликация, эквивалентность, булева сумма, штрих, стрелка). Коммутативность, ассоциативность, дистрибутивность операций.Основные соотношения. Оглавление Введение Учебные дисциплины направления: Дискретный анализ Элементы математической логики. Исторический и философский экскурс Функции алгебры логики (Ф.А.Л.) Высказывания. Алгебра высказываний Определение: функция алгебры логики Табличное задание функции алгебры логики Необходимость аналитической записи функции алгебры логики Элементарные функции алгебры логики Функции 1-й переменной. Константа, тождество, отрицание Функции 2-х переменных Дизъюнкция Конъюнкция Сумма, или булева сумма Эквивалентность Импликация Штрих Шеффера, стрелка Пирса Формулы Комбинирование элементарных функций и запись формул Формулы. Индуктивные правила их составления Связь формул и функций Равносильные формулы Простейшие равносильные формулы Доказательство равносильности некоторых формул Коммутативность, ассоциативность, дистрибутивность операций Свойства операций Коммутативность Ассоциативность Дистрибутивность О записи формул Старшинство операций Правило поглощения Формула для функции, заданной в табличной записи Теорема 1. О разложении функции алгебры логики в дизъюнктивную форму по одной переменной	-
Лекция 2	Выразимость произвольной функции алгебры логики с помощью операций дизъюнкции, конъюнкции и отрицания. Полнота, замкнутые классы Разложение произвольной функции алгебры логики в дизъюнктивную форму по одной и всем переменным. Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма. Полнота систем функций алгебры логики и замкнутые классы. Оглавление Введение Разложение произвольной функции алгебры логики в дизъюнктивную форму по одной, нескольким, и всем переменным Разложение по одной переменной. Пример Обобщение на случай k переменных, обозначения Теорема 2. Разложение функции в дизъюнктивную форму по k переменным Примеры: разложение функций по 2 переменным Теорема 2. Доказательство Разложение функции в дизъюнктивную форму по всем переменным Совершенная дизъюнктивная нормальная форма Совершенная конъюнктивная нормальная форма Примеры совершенной дизъюнктивной формы, совершенной конъюнктивной формы Теорема 3. О представлении произвольной функции алгебры логики через операции дизъюнкции, конъюнкции и отрицания Функциональная полнота систем функций алгебры логики. Замкнутые классы Введение о полноте и замкнутости Операции над функциями Замена переменной Суперпозиция функций Полные системы функций Важнейшие замкнутые классы функций Понятие замкнутого класса функций Т0 - класс функций, сохраняющих нуль Т1 - класс функций, сохраняющих единицу	-
Лекция 3	Замкнутые классы (окончание). Основная лемма критерия полноты Замкнутые классы линейных, самодвойственных и монотонных функций (L, S, M). Лемма о несамодвойственной функции. Лемма о немонотонной функции. Основная лемма критерия полноты (начало). Оглавление Введение Повторение о полноте, замкнутых классах Важнейшие замкнутые классы функций (окончание) Класс линейных функций Количество линейных функции от n переменных Замкнутость класса линейных функций Класс самодвойственных функций Двойственная функция Лемма о функции, двойственной к суперпозиции Пример внутри леммы Самодвойственная функция. Определение Примеры самодвойственных функций Несуществование самодвойственной функции от 2 переменных Значение самодвойственной функции на противоположных наборах Количество самодвойственных функций от n переменных Замкнутость класса самодвойственных функций Класс монотонных функций Частичный порядок на n-мерных векторах из 0 и 1 Монотонная функция, определение Примеры монотонных функций Количество монотонных функций от n переменных Замкнутость класса монотонных функций Основная лемма критерия полноты Содержание основной леммы Доказательство основной леммы Лемма о несамодвойственной функции Продолжение доказательства основной леммы	-
Тест 1 1 час 9 минут	23 задания	-
Лекция 4	Критерий полноты Лемма о нелинейной функции. Критерий полноты. Предполные классы функций алгебры логики. Следствия из критерия полноты. Представление о результатах Поста. Оглавление Введение Доказательство основной леммы критерия полноты (окончание) Повторение результатов предыдущей лекции Лемма о немонотонной функции Продолжение доказательства основной леммы Лемма о нелинейной функции Доказательство леммы о нелинейной функции Полином Жегалкина Пример Критерий полноты Критерий полноты, формулировка Примеры применения критерия полноты Доказательство критерия полноты Подведение итогов раздела	-
Лекция 5	Комбинаторика. Задачи о числе функции и размещений Предмет комбинаторики. Основные задачи комбинаторики. Два принципа комбинаторики (принцип произведения, принцип суммы). Число произвольных и инъективных отображений конечных множеств. Количество слов длины n в алфавите из m символов. Числа Стирлинга первого рода. Оглавление Введение Предмет комбинаторики Основные задачи комбинаторики Основные задачи комбинаторики Существование конфигураций Подсчет числа конфигураций Приближенный подсчет числа конфигураций Перечисление конфигураций Оптимизация Количество функций и размещений Подсчет числа функций и размещений Основные правила комбинаторики Два основных правила комбинаторики Правило произведения Правило суммы Роль двух основных правил комбинаторики Модельные задачи О формулировках в терминах модельных задач Задача 1: о числе функций (отображений) Задача 2: о размещении объектов по ящикам Взаимосвязь между задачами 1 и 2 Задача 3: о числе слов в алфавите Методы решения задач комбинаторики О разных простых утверждениях для решения задач Утверждение 1.1. О количестве отображений из Х в У Утверждение 1.1. О количестве размещений n объектов по m ящикам Утверждение 1.1. О количестве слов длины n в алфавите из m символов Понятие инъективной функции Понятие n факториал от x вниз Утверждение 1.2. О количестве инъективных отображений множества Х в множество У Возражение к Утверждению 1.2. о математической индукции Утверждение 1.2. О количестве размещений n различных объектов по m ящикам Утверждение 1.2. О количестве слов длины n (в которых все символы различны) в алфавите из m символов Понятие перестановки Утверждение 1.3. О количестве перестановок из n элементов Полиномы степени n и числа Стирлинга I рода Утверждение 1.4. О рекуррентном соотношении для чисел Стирлига I рода Выведение рекуррентного соотношения при отсутствии аналитического решения Замечания о числах Стирлинга. Равенство нулю и знакопеременность Упорядоченное размещение по ящикам	-
Тест 2 1 час 6 минут	22 задания	-
Лекция 6	Упорядоченные размещения и монотонные слова Число упорядоченных размещений n различных объектов по m различным ящикам. Число монотонных слов длины n в алфавите m символов. Задача Муавра. Оглавление Введение Упорядоченное размещение n различных объектов по m различным ящикам (окончание) Упорядоченное размещение n различных объектов по m различным ящикам Обозначение: х в верхней степени n Утверждение 1.5. О количестве упорядоченных размещений n различных объектов по m различным ящикам Алфавит, слово, монотонное слово Утверждение 1.6. О количестве монотонных слов длины n в алфавите из m символов Три результата о монотонных словах Замечание о делимости. Применение Утверждения 1.6 Пример: Задача Муавра Пример о банке и направлениях инвеастиций Сочетания Понятие сочетания Пример: сочетания Обозначения количества сочетаний Утверждение 1.7. О количестве сочетаний из n по k Свойства сочетаний из n по k. Ограничения для k Два важнейших свойства чисел сочетаний Комбинаторное доказательство второго свойства чисел сочетаний Биномиальные коэффициенты Биномиальные коэффициенты и производящие функции Примеры на производящие функции Свертка или произведение Коши	-
Лекция 7	Сочетания и биномиальные коэффициенты Определение сочетаний. Число сочетаний. Производящие функции. Бином и биномиальные коэффициенты. Важнейшие соотношения для биномиальных коэффициентов. Полиномиальные коэффициенты. Оглавление Введение Биномиальные коэффициенты (окончание) Бином и биномиальные коэффициенты Утверждение 1.8. О производящей функции последовательности из n по k Бином Ньютона Пример производящей функции Доказательство Утверждения 1.8 Соотношения для производящей функции Исходное соотношение для (1+х)^n Соотношение 1: случай х=1 Биномиальные коэффициенты Соотношение 2: случай х=1 и дифференцирование Соотношение 3: случай х=-1 и сумма половины ряда коэффициентов Примеры к Соотношению 3 для n=3, n=4 Соотношение 3 в общем случае Соотношение 4: произведение производящих функций Сумма квадратов числа сочетаний Размещения при фиксированном количестве объектов в ящике О характере задач Утверждение 1.9. О количестве размещений n различных объектов по p различным ящикам при фиксированном количестве объектов в ящике Доказательство Утверждения 1.9 Два замечания. Полиномиальные коэффициенты Утверждение 1.10. - Полиномиальная теорема Доказательство полиномиальной теоремы Соотношения из полиномиальной теоремы Разбиения Понятие разбиения множества Разбиение в терминах размещения объектов по ящикам Обозначение количества разбиений Пример разбиения множества на классы Числа Стирлинга II рода	-
Тест 3 1 час 6 минут	22 задания	-
Лекция 8	Разбиения Разбиения множества на классы. Число разбиений (числа Стирлинга второго рода). Число сюръективных отображений (число размещений n различных объектов по m неразличным ящикам). Основные комбинаторные соотношения для чисел Стирлинга второго рода. Оглавление Введение Разбиение множества из n элемкентов на k классов Конкретные значения количества разбиений S(n,k) Утверждение 2.1. О рекуррентной формуле для чисел разбиений Доказательство Утверждения 2.1 Пример на формулу для чисел разбиений Сюрьективное отображение Понятие сюрьективного отображения Утверждение 2.2. О количестве сюрьективных отображений Доказательство Утверждения 2.2 Основные комбинаторные соотношения для чисел Стирлинга II рода Два основных соотношения Доказательство первого основного соотношения Полиномиальная аргументация Доказательство второго основного соотношения Числа Белла Разбиения на произвольное число классов Рекуррентное соотношение для чисел Белла Доказательство рекуррентного соотношения Размещение n одинаковых обектов по m различным ящикам	-
Лекция 9	Принцип включений – исключений Формула включений – исключений. Задача о числе беспорядков. Количество сюръективных отображений. Оглавление Введение Метод включений-исключений Суть метода включений-исключений Простейшие примеры Общая схема метода включений-исключений, обозначения Основная задача метода включений-исключений Теорема 1. Формула включений-исключений Пример на индексы суммирования Доказательство Теоремы 1 Задача о числе беспорядков Понятие беспорядка Задача о подсчете числа беспорядков Выражение числа беспорядков через число е Другие способы представления числа беспорядков Подсчет чисел Стирлинга II рода Числа Стирлинга и сюрьективные отображения Теорема 2. О количестве сюрьективных отображений Подсчет количества сюрьективных отображений Мощь метода включений-исключений Явная формула для чисел отображений Следствие из теоремы 2. Формула явного вида чисел Стирлинга II рода	-
Лекция 10	Системы представителей множеств Определение системы различных представителей. Критерий наличия системы различных представителей для заданной системы множеств. Алгоритм построения системы. Оглавление Введение Системы различных представителей (С.Р.П.) Понятие представителя множества Система различнвх представителей Примеры систем различных представителей Критерий наличия системы различных представителей Существование систем различных представителей Теорема 1. Критерий наличия системы различных представителей Доказательство критерия: необходимость Доказательство критерия: достаточность. Алгоритм построения системы Метод доказательства Построение системы различных представителей Замена представителей Случай 1: построенная система полностью состоит из представителей Случай 2: наличие в системе не представителя, замена представителей Пример на построение системы различных представителей Количество различных С.Р.П. Система общих (одновременных представителей) Понятие системы общих представителей Условие существования системы общих представителей	-
Тест 4 1 час 6 минут	22 задания	-
Лекция 11	Графы, основные определения Предмет теории графов. Определение ориентированного и неориентированного графа. Кратные ребра и петли. Простые графы. Степени вершин. Изоморфизм графов. Машинное представление графов. Пути и циклы. Оглавление Введение Элементы теории графов Исторический экскурс. Проблема 4 красок Теория графов в наше время Основные определения теории графов Ориентированный и неориентированный граф Графическое изображение графа, пример Начальная, конечная фершина ребра Инцидентная вершина, инцидентное ребро Смежные ребра Полный неориентированный граф. Количество ребер в нем Полный ориентированный граф. Количество ребер в нем Расширение понятия графа. Кратность ребра, степени вершин Кратные ребра Петли Простой граф Степени вершин Изолированные вершины О степени вершин Теорема 1. (Лемма о рукопожатиях) Примеры на степени вершин Графическое представление графов. Изоморфизм графов Пример изоморфизма графов Понятие изоморфизма Определение изоморфизма графов Продолжение Примера на изоморфизм графов О задаче установления изоморфизма 2 графов Машинное представление графов Графическое представление, пример Матрица инциденций Матрица смежности Списки инциденций Пути и циклы Путь, определение Длина пути Простой путь Цикл	-
Лекция 12	Связность графов. Деревья Часть графа. Подграф. Связные графы. Компоненты связности. Максимальное число ребер в простом графе с заданным количеством вершин и компонент связности. Количество деревьев на заданном множестве вершин. Оглавление Введение Связность графа Часть графа, определение Подграф, определение Примеры на часть графа, подграф Связанные вершины. Связные графы Связанные вершины, определение Связный граф, определение Пример на разбиение множества вершин Представление графа в виде объединения связанных компонент Теоремы о связности графа и количестве вершин в нем Теорема 2. О связности единственных вершин нечетной степени Доказательство Теоремы 2 Теорема 3. О максимальном количестве ребер в графе Доказательство Теоремы 3 Применение свойств параболы при оценке количества ребер графа Доказательство Теоремы 3, окончание Следствие. О связности графа с данным количеством ребер Деревья, определения и утверждения Дерево, определение Утверждение 1. О единственности простого пути Графическое представление дерева. Растительная терминология Концевая вершина, концевое ребро Применение деревьев. Тест на грамматику Утверждение 2. О нетривиальности дерева Утверждение 3. О количестве ребер дерева Количество различных деревьев, которые можно построить на n заданных вершинах Задача о количестве различных деревьев Примеры на количество различных деревьев Теорема 4. О количестве деревьев на n вершинах Доказательство Теоремы 4 Примеры Замечания о списках вершин для деревьев	-
Тест 5 1 час 6 минут	22 задания	-
Лекция 13	Эйлеровы пути и циклы Окончание доказательства о числе деревьев.. Задача о кенингсбергских мостах. Эйлеровы пути и циклы. Критерий существования эйлеровых путей в графе. Алгоритм построения эйлерова цикла. Оглавление Введение Задача о количестве деревьев Связь количества деревьев и количества слов Задача о числе деревьев на n вершинах с k концевыми вершинами Доказательство к задаче, начало. Метод включений-исключений Доказательство к задаче, окончание. Метод разбиений Ответ к задаче Примеры решения задачи Эйлеровы пути и циклы Задача о Кенигсбергскийх мостах Задача о Кенигсбергких мостах в виде графа Эйлеров путь. Эйлеров цикл Применение эйлеровых циклов Конечный граф. Теорема 1. Критерий существования эйлерова пути в графе Сведение задачи об эйлеровом пути к задаче об эйлеровом цикле Теорема 2. Критерий существования эйлерова цикла Доказательство критерия. Необходимость Доказательство критерия. Достаточность. Алгоритм построения эйлерова цикла Пример построения эйлерова цикла Оценка сложности построенного алгоритма	-
Лекция 14	Гамильтоновы пути и циклы Игра "Кругосветное путешествие" У. Гамильтона. Гамильтоновы пути и циклы. Путь, имеющий тип цикла. Условие, при котором простой путь имеет тип цикла. Простой путь. Максимальный простой путь , имеющий тип цикла. Достаточные условия существования гамильтоновых путей и циклов. Оглавление Введение Гамильтоновы пути и циклы Игра: Кругосветное путешествие. Применение гамильтоновых циклов Гамильтонов путь, определение Существование гамильтоновых путей Условия существования гамильтоновых циклов Путь типа цикла Условия существования гамильтоновых циклов (продолжение) Построение цикла Полный путь. Максимальный полный путь Полный путь Пример полного пути Ребра и нцидентные началу и концу пути Теорема 1. О полном простом пути, имеющием тип цикла Максимальный полный путь Теорема 2. О максимальном простом пути, имеющем тип цикла Доказательство Теоремы 2 Теорема 3. Неравенство о длине максимальных путей Теорема 4. О графе без гамильтоновых циклов Теорема 5. Достаточное условие существования гамильтоновых путей и циклов Следствие. Теорема Дирака Теорема 6. О существовании гамильтонова цикла в графе с заданной степенной последовательностью Возможность существования гамильтонова пути. Тета-граф Тета-граф 2-связный граф Гамильтонов и негамильтонов граф Теорема 7. О тета-подграфе 2-связного негамильтонового графа Доказательство Теоремы 7 3-связный и 4-связный граф. Плоский граф	-
Лекция 15	Нахождение кратчайших путей в графе Ориентированные графы с весами ребер. Сложность задач о нахождении кратчайших путей от источника до всех остальных вершин (граф без циклов отрицательной длины, граф с неотрицательными весами ребер, граф без циклов). Алгоритм нахождения кратчайших путей для второй задачи. Оглавление Введение Ориентированные графы с весами ребер Кратчайший путь, расстояние Приложения задачи поиска кратчайшего пути Сложность задач о нахождении кратчайших путей от источника до всех остальных вершин Поиск кратчайших путей в ориентированном графе без циклов отрицательной длины Поиск кратчайших путей в графе с нетрицательными весами ребер Поиск кратчайших путей в графе без циклов Алгоритм поиска кратчайших путей в графе с нетрицательными весами ребер История вопроса. Алгоритм Дейкстры Вход алгоритма Результат работы алгоритма Метод алгоритма. Идея Алгоритм, по шагам Пример на алгоритм Исправление в алгоритм Продолжение примера Доказательство корректности алгоритма. Метод, этапы Доказательство алгоритма. База индукции Доказательство алгоритма. Индуктивный переход Алгоритм нахождения кратчайших путей в графе без циклов отрицательной длины	-
Тест 6 54 минуты	18 заданий	-
5 часов	Экзамен	-

Авторизоваться

Дискретный анализ

План занятий