Дискретный анализ: Информация

Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
 
Уровень:
Специалист
Длительность:
6:27:00
Студентов:
932
Выпускников:
36
Качество курса:
4.80 | 4.40
Дискретный анализ содержит материал, излагаемый в первом семестре курса дискретного анализа: комбинаторика, элементы алгебры логики, начальные сведения теории графов. В курс включены как основополагающие понятия и результаты перечисленных разделов, так и материал повышенной трудности, часто в лекциях не излагаемый. Курс предназначен для изучения студентами соответствующих разделов программы основ дискретного анализа.
Математическая экспансия - вторжение математики в новые, ранее ею не контролируемые территории - привела к использованию математических методов представителями как естественнонаучных, так и гуманитарных областей знания. Все это сделало понимание путей использования математического аппарата важнейшим элементом общей культуры, а владение терминами «математическая структура» и «математическая модель» - необходимыми атрибутами образованного человека. Именно поэтому в курс включены три основных раздела дискретного анализа: алгебра логики, комбинаторика, теория графов. Дисциплина является необходимым языковым и методологическим основанием для формирования принципов и методов дискретного мышления. Дисциплина направлена на развитие навыков формализации и организации понятий, необходимых при изучении информатики и математического моделирования и при решении теоретических и прикладных задач. Дискретные математические объекты, теория и методы построения математических и прикладных дискретных моделей лежат в основе профессиональных навыков и умений грамотного специалиста в области прикладной информатики и составляют необходимую часть ремесла грамотного исследователя, аналитика, практика, формирует их профессиональную культуру.
Специальности: Программист, Математик
 

План занятий

Занятие
Заголовок <<
Дата изучения
Функции алгебры логики
Предмет алгебры логики. Элементарные высказывания. Элементарные логические операции (дизъюнкция, конъюнкция, импликация, эквивалентность, булева сумма, штрих, стрелка). Коммутативность, ассоциативность, дистрибутивность операций.Основные соотношения.
Оглавление
-
Выразимость произвольной функции алгебры логики с помощью операций дизъюнкции, конъюнкции и отрицания. Полнота, замкнутые классы
Разложение произвольной функции алгебры логики в дизъюнктивную форму по одной и всем переменным. Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма. Полнота систем функций алгебры логики и замкнутые классы.
Оглавление
-
Замкнутые классы (окончание). Основная лемма критерия полноты
Замкнутые классы линейных, самодвойственных и монотонных функций (L, S, M). Лемма о несамодвойственной функции. Лемма о немонотонной функции. Основная лемма критерия полноты (начало).
Оглавление
-
Тест 1
1 час 9 минут
-
Комбинаторика. Задачи о числе функции и размещений
Предмет комбинаторики. Основные задачи комбинаторики. Два принципа комбинаторики (принцип произведения, принцип суммы). Число произвольных и инъективных отображений конечных множеств. Количество слов длины n в алфавите из m символов. Числа Стирлинга первого рода.
Оглавление
-
Тест 2
1 час 6 минут
-
Упорядоченные размещения и монотонные слова
Число упорядоченных размещений n различных объектов по m различным ящикам. Число монотонных слов длины n в алфавите m символов. Задача Муавра.
Оглавление
-
Сочетания и биномиальные коэффициенты
Определение сочетаний. Число сочетаний. Производящие функции. Бином и биномиальные коэффициенты. Важнейшие соотношения для биномиальных коэффициентов. Полиномиальные коэффициенты.
Оглавление
-
Тест 3
1 час 6 минут
-
Разбиения
Разбиения множества на классы. Число разбиений (числа Стирлинга второго рода). Число сюръективных отображений (число размещений n различных объектов по m неразличным ящикам). Основные комбинаторные соотношения для чисел Стирлинга второго рода.
-
Принцип включений – исключений
Формула включений – исключений. Задача о числе беспорядков. Количество сюръективных отображений.
-
Системы представителей множеств
Определение системы различных представителей. Критерий наличия системы различных представителей для заданной системы множеств. Алгоритм построения системы.
Оглавление
-
Тест 4
1 час 6 минут
-
Графы, основные определения
Предмет теории графов. Определение ориентированного и неориентированного графа. Кратные ребра и петли. Простые графы. Степени вершин. Изоморфизм графов. Машинное представление графов. Пути и циклы.
Оглавление
-
Связность графов. Деревья
Часть графа. Подграф. Связные графы. Компоненты связности. Максимальное число ребер в простом графе с заданным количеством вершин и компонент связности. Количество деревьев на заданном множестве вершин.
Оглавление
-
Тест 5
1 час 6 минут
-
Эйлеровы пути и циклы
Окончание доказательства о числе деревьев.. Задача о кенингсбергских мостах. Эйлеровы пути и циклы. Критерий существования эйлеровых путей в графе. Алгоритм построения эйлерова цикла.
Оглавление
-
Гамильтоновы пути и циклы
Игра "Кругосветное путешествие" У. Гамильтона. Гамильтоновы пути и циклы. Путь, имеющий тип цикла. Условие, при котором простой путь имеет тип цикла. Простой путь. Максимальный простой путь , имеющий тип цикла. Достаточные условия существования гамильтоновых путей и циклов.
Оглавление
-
Нахождение кратчайших путей в графе
Ориентированные графы с весами ребер. Сложность задач о нахождении кратчайших путей от источника до всех остальных вершин (граф без циклов отрицательной длины, граф с неотрицательными весами ребер, граф без циклов). Алгоритм нахождения кратчайших путей для второй задачи.
Оглавление
-
Тест 6
54 минуты
-
1 час 40 минут
-