Дискретный анализ: Информация
Автор: Юрий Флеров
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
Вам нравится? Нравится 17 студентам
Уровень:
Специалист
Длительность:
6:27:00
Студентов:
936
Выпускников:
36
Качество курса:
4.80 | 4.40
Дискретный анализ содержит материал, излагаемый в первом семестре курса дискретного анализа: комбинаторика, элементы алгебры логики, начальные сведения теории графов. В курс включены как основополагающие понятия и результаты перечисленных разделов, так и материал повышенной трудности, часто в лекциях не излагаемый. Курс предназначен для изучения студентами соответствующих разделов программы основ дискретного анализа.
Математическая экспансия - вторжение математики в новые, ранее ею не контролируемые территории - привела к использованию математических методов представителями как естественнонаучных, так и гуманитарных областей знания. Все это сделало понимание путей использования математического аппарата важнейшим элементом общей культуры, а владение терминами «математическая структура» и «математическая модель» - необходимыми атрибутами образованного человека.
Именно поэтому в курс включены три основных раздела дискретного анализа: алгебра логики, комбинаторика, теория графов.
Дисциплина является необходимым языковым и методологическим основанием для формирования принципов и методов дискретного мышления. Дисциплина направлена на развитие навыков формализации и организации понятий, необходимых при изучении информатики и математического моделирования и при решении теоретических и прикладных задач. Дискретные математические объекты, теория и методы построения математических и прикладных дискретных моделей лежат в основе профессиональных навыков и умений грамотного специалиста в области прикладной информатики и составляют необходимую часть ремесла грамотного исследователя, аналитика, практика, формирует их профессиональную культуру.
Специальности: Программист, Математик
Дополнительные курсы
План занятий
Занятие
Заголовок <<
Дата изучения
Функции алгебры логики
Предмет алгебры логики. Элементарные высказывания. Элементарные логические операции (дизъюнкция, конъюнкция, импликация, эквивалентность, булева сумма, штрих, стрелка). Коммутативность, ассоциативность, дистрибутивность операций.Основные соотношения.
Оглавление
- Введение
- Учебные дисциплины направления: Дискретный анализ
- Элементы математической логики. Исторический и философский экскурс
- Функции алгебры логики (Ф.А.Л.)
- Элементарные функции алгебры логики
- Формулы
- Коммутативность, ассоциативность, дистрибутивность операций
- О записи формул
- Теорема 1. О разложении функции алгебры логики в дизъюнктивную форму по одной переменной
-
Выразимость произвольной функции алгебры логики с помощью операций дизъюнкции, конъюнкции и отрицания. Полнота, замкнутые классы
Разложение произвольной функции алгебры логики в дизъюнктивную форму по одной и всем переменным. Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма. Полнота систем функций алгебры логики и замкнутые классы.
-
Замкнутые классы (окончание). Основная лемма критерия полноты
Замкнутые классы линейных, самодвойственных и монотонных функций (L, S, M). Лемма о несамодвойственной функции. Лемма о немонотонной функции. Основная лемма критерия полноты (начало).
Оглавление
-
Критерий полноты
Лемма о нелинейной функции. Критерий полноты. Предполные классы функций алгебры логики. Следствия из критерия полноты. Представление о результатах Поста.
-
Комбинаторика. Задачи о числе функции и размещений
Предмет комбинаторики. Основные задачи комбинаторики. Два принципа комбинаторики (принцип произведения, принцип суммы). Число произвольных и инъективных отображений конечных множеств. Количество слов длины n в алфавите из m символов. Числа Стирлинга первого рода.
-
Упорядоченные размещения и монотонные слова
Число упорядоченных размещений n различных объектов по m различным ящикам. Число монотонных слов длины n в алфавите m символов. Задача Муавра.
-
Сочетания и биномиальные коэффициенты
Определение сочетаний. Число сочетаний. Производящие функции. Бином и биномиальные коэффициенты. Важнейшие соотношения для биномиальных коэффициентов. Полиномиальные коэффициенты.
-
Разбиения
Разбиения множества на классы. Число разбиений (числа Стирлинга второго рода). Число сюръективных отображений (число размещений n различных объектов по m неразличным ящикам). Основные комбинаторные соотношения для чисел Стирлинга второго рода.
Оглавление
- Введение
- Разбиение множества из n элемкентов на k классов
- Конкретные значения количества разбиений S(n,k)
- Утверждение 2.1. О рекуррентной формуле для чисел разбиений
- Доказательство Утверждения 2.1
- Пример на формулу для чисел разбиений
- Сюрьективное отображение
- Основные комбинаторные соотношения для чисел Стирлинга II рода
- Числа Белла
- Размещение n одинаковых обектов по m различным ящикам
-
Принцип включений – исключений
Формула включений – исключений. Задача о числе беспорядков. Количество сюръективных отображений.
-
Системы представителей множеств
Определение системы различных представителей. Критерий наличия системы различных представителей для заданной системы множеств. Алгоритм построения системы.
Оглавление
-
Графы, основные определения
Предмет теории графов. Определение ориентированного и неориентированного графа. Кратные ребра и петли. Простые графы. Степени вершин. Изоморфизм графов. Машинное представление графов. Пути и циклы.
-
Связность графов. Деревья
Часть графа. Подграф. Связные графы. Компоненты связности. Максимальное число ребер в простом графе с заданным количеством вершин и компонент связности. Количество деревьев на заданном множестве вершин.
-
Эйлеровы пути и циклы
Окончание доказательства о числе деревьев.. Задача о кенингсбергских мостах. Эйлеровы пути и циклы. Критерий существования эйлеровых путей в графе. Алгоритм построения эйлерова цикла.
-
Гамильтоновы пути и циклы
Игра "Кругосветное путешествие" У. Гамильтона. Гамильтоновы пути и циклы. Путь, имеющий тип цикла. Условие, при котором простой путь имеет тип цикла. Простой путь. Максимальный простой путь , имеющий тип цикла. Достаточные условия существования гамильтоновых путей и циклов.
-
Нахождение кратчайших путей в графе
Ориентированные графы с весами ребер. Сложность задач о нахождении кратчайших путей от источника до всех остальных вершин (граф без циклов отрицательной длины, граф с неотрицательными весами ребер, граф без циклов). Алгоритм нахождения кратчайших путей для второй задачи.
Оглавление
- Введение
- Ориентированные графы с весами ребер
- Кратчайший путь, расстояние
- Приложения задачи поиска кратчайшего пути
- Сложность задач о нахождении кратчайших путей от источника до всех остальных вершин
- Алгоритм поиска кратчайших путей в графе с нетрицательными весами ребер
- Алгоритм нахождения кратчайших путей в графе без циклов отрицательной длины
-