Компьютерные науки
Математика и логика

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

Программа о дискретном анализе охватывает три ключевых раздела: алгебру логики, комбинаторику и теорию графов. Она включает как базовые понятия, так и материал повышенной сложности, формируя прочное методологическое основание для развития дискретного мышления и построения математических моделей.
Студентов 1066 Выпускников 52 Для специалистов
690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
Темы:
Алгоритмы и сложность, Математика
Объем
36 час.
Длительность
30 дней
Нагрузка в неделю
9 час.
Формат обучения
Дистанционно (самостоятельно)
Описание Учебная программа знакомит с основами дискретного анализа, необходимыми для работы с современными информационными технологиями. Освоение материала разбито на тематические блоки, начиная с функций алгебры логики и критериев полноты, переходя к комбинаторным задачам и завершая теорией графов. Особое внимание уделяется развитию навыков формализации понятий и построению математических моделей. Изучаются методы нахождения кратчайших путей, эйлеровы и гамильтоновы циклы. Большинство тем включает проверочные тесты. Материал адресован ИТ-специалистам и исследователям, которым важно применять математический аппарат для решения прикладных задач.
Цели
  • Сформировать методологическую базу дискретного мышления.
  • Познакомить с основными принципами алгебры логики, комбинаторики и теории графов.
  • Дать навыки формализации задач и построения дискретных математических моделей.
Чему я научусь?
  • Использовать функции алгебры логики и проверять их на полноту.
  • Решать комбинаторные задачи на размещения, сочетания и разбиения.
  • Применять принцип включений-исключений в расчетах.
  • Анализировать графы, находить кратчайшие пути, эйлеровы и гамильтоновы циклы.

Авторы

Флеров Юрий Арсениевич
Флеров Юрий Арсениевич
Доктор физико-математических наук, профессор, член-корреспондент РАН.
Чему я научусь?
  • Использовать функции алгебры логики и проверять их на полноту.
  • Решать комбинаторные задачи на размещения, сочетания и разбиения.
  • Применять принцип включений-исключений в расчетах.
  • Анализировать графы, находить кратчайшие пути, эйлеровы и гамильтоновы циклы.

Учебный план

№ Занятия
Экзамен экстерном Внимание! Экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите подтвердить свои знания по данному курсу без его изучения или поверить свои знания по нему. Экзамен экстерном можно сдать только один раз. 90 мин
1 Функции алгебры логики Предмет алгебры логики. Элементарные высказывания. Элементарные логические операции (дизъюнкция, конъюнкция, импликация, эквивалентность, булева сумма, штрих, стрелка).... Предмет алгебры логики. Элементарные высказывания. Элементарные логические операции (дизъюнкция, конъюнкция, импликация, эквивалентность, булева сумма, штрих, стрелка). Коммутативность, ассоциативность, дистрибутивность операций.Основные соотношения. ещё
2 Выразимость произвольной функции алгебры логики с помощью операций дизъюнкции, конъюнкции и отрицания. Полнота, замкнутые классы Разложение произвольной функции алгебры логики в дизъюнктивную форму по одной и всем переменным. Совершенная дизъюнктивная нормальная... Разложение произвольной функции алгебры логики в дизъюнктивную форму по одной и всем переменным. Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма. Полнота систем функций алгебры логики и замкнутые классы. ещё
3 Замкнутые классы (окончание). Основная лемма критерия полноты Замкнутые классы линейных, самодвойственных и монотонных функций (L, S, M). Лемма о несамодвойственной функции. Лемма о... Замкнутые классы линейных, самодвойственных и монотонных функций (L, S, M). Лемма о несамодвойственной функции. Лемма о немонотонной функции. Основная лемма критерия полноты (начало). ещё
Замкнутые классы (окончание). Основная лемма критерия полноты тест для курса Дискретный анализ 115 мин
4 Критерий полноты Лемма о нелинейной функции. Критерий полноты. Предполные классы функций алгебры логики. Следствия из критерия полноты. Представление... Лемма о нелинейной функции. Критерий полноты. Предполные классы функций алгебры логики. Следствия из критерия полноты. Представление о результатах Поста. ещё
5 Комбинаторика. Задачи о числе функции и размещений Предмет комбинаторики. Основные задачи комбинаторики. Два принципа комбинаторики (принцип произведения, принцип суммы). Число произвольных и инъективных... Предмет комбинаторики. Основные задачи комбинаторики. Два принципа комбинаторики (принцип произведения, принцип суммы). Число произвольных и инъективных отображений конечных множеств. Количество слов длины n в алфавите из m символов. Числа Стирлинга первого рода. ещё
Комбинаторика. Задачи о числе функции и размещений тест для курса Дискретный анализ 110 мин
6 Упорядоченные размещения и монотонные слова Число упорядоченных размещений n различных объектов по m различным ящикам. Число монотонных слов длины n в... Число упорядоченных размещений n различных объектов по m различным ящикам. Число монотонных слов длины n в алфавите m символов. Задача Муавра. ещё
7 Сочетания и биномиальные коэффициенты Определение сочетаний. Число сочетаний. Производящие функции. Бином и биномиальные коэффициенты. Важнейшие соотношения для биномиальных коэффициентов. Полиномиальные... Определение сочетаний. Число сочетаний. Производящие функции. Бином и биномиальные коэффициенты. Важнейшие соотношения для биномиальных коэффициентов. Полиномиальные коэффициенты. ещё
Сочетания и биномиальные коэффициенты тест для курса Дискретный анализ 110 мин
8 Разбиения Разбиения множества на классы. Число разбиений (числа Стирлинга второго рода). Число сюръективных отображений (число размещений n... Разбиения множества на классы. Число разбиений (числа Стирлинга второго рода). Число сюръективных отображений (число размещений n различных объектов по m неразличным ящикам). Основные комбинаторные соотношения для чисел Стирлинга второго рода. ещё
9 Принцип включений – исключений Формула включений – исключений. Задача о числе беспорядков. Количество сюръективных отображений.
10 Системы представителей множеств Определение системы различных представителей. Критерий наличия системы различных представителей для заданной системы множеств. Алгоритм построения системы.
Системы представителей множеств тест для курса Дискретный анализ 110 мин
11 Графы, основные определения Предмет теории графов. Определение ориентированного и неориентированного графа. Кратные ребра и петли. Простые графы. Степени вершин.... Предмет теории графов. Определение ориентированного и неориентированного графа. Кратные ребра и петли. Простые графы. Степени вершин. Изоморфизм графов. Машинное представление графов. Пути и циклы. ещё
12 Связность графов. Деревья Часть графа. Подграф. Связные графы. Компоненты связности. Максимальное число ребер в простом графе с заданным количеством... Часть графа. Подграф. Связные графы. Компоненты связности. Максимальное число ребер в простом графе с заданным количеством вершин и компонент связности. Количество деревьев на заданном множестве вершин. ещё
Связность графов. Деревья тест для курса Дискретный анализ 110 мин
13 Эйлеровы пути и циклы Окончание доказательства о числе деревьев.. Задача о кенингсбергских мостах. Эйлеровы пути и циклы. Критерий существования эйлеровых... Окончание доказательства о числе деревьев.. Задача о кенингсбергских мостах. Эйлеровы пути и циклы. Критерий существования эйлеровых путей в графе. Алгоритм построения эйлерова цикла. ещё
14 Гамильтоновы пути и циклы "Игра ""Кругосветное путешествие"" У. Гамильтона. Гамильтоновы пути и циклы. Путь, имеющий тип цикла. Условие, при котором... "Игра ""Кругосветное путешествие"" У. Гамильтона. Гамильтоновы пути и циклы. Путь, имеющий тип цикла. Условие, при котором простой путь имеет тип цикла. Простой путь. Максимальный простой путь , имеющий тип цикла. Достаточные условия существования гамильтоновых путей и циклов." ещё
15 Нахождение кратчайших путей в графе Ориентированные графы с весами ребер. Сложность задач о нахождении кратчайших путей от источника до всех остальных... Ориентированные графы с весами ребер. Сложность задач о нахождении кратчайших путей от источника до всех остальных вершин (граф без циклов отрицательной длины, граф с неотрицательными весами ребер, граф без циклов). Алгоритм нахождения кратчайших путей для второй задачи. ещё
Нахождение кратчайших путей в графе тест для курса Дискретный анализ 90 мин
Тренировочный экзамен Внимание! Тренировочный экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите проверить свои знания курса перед сдачей экзамена. Тренировочный экзамен можно сдавать сколько угодно один раз. 90 мин
Экзамен 60 мин

Какой документ я получу?

Сертификат

Выдаётся автоматически после успешного завершения программы.

Удостоверение о повышении квалификации

Выдается при наличии среднего специального или высшего образования (необходимые документы).

Стоимость программы

690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
^