rpd000002313 (1006647), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Булевы алгебры, связь с логикой высказываний и алгеброй множеств.

1.3.3. Аксиоматические теории. Исчисление высказываний.(АЗ: 2, СРС: 4)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Понятие о формальной аксиоматической теории. Понятие вывода, вывода из системы гипотез. Основные свойства выводимости. Исчисление высказываний как аксиоматическая теория. Теорема дедукции. Непротиворечивость и полнота исчисления высказываний. Независимость аксиом.

1.4.1. Логика и исчисление предикатов.(АЗ: 4, СРС: 5)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Предикаты. Кванторы. Язык логики предикатов. Формулы логики предикатов. Понятие интерпретации. Равносильность формул логики предикатов. Истинность и общезначимость формул логики предикатов.

Приведенная нормальная форма формул логики предикатов. Проблема разрешимости. Формулировка теоремы Черча. Исчисление предикатов как аксиоматическая теория. Непротиворечивость исчисления предикатов. Общезначимость выводимых формул. Формулировка Геделя о полноте исчисления предикатов.

1.5.1. Основные понятия теории графов.(АЗ: 2, СРС: 2)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Ориентированные и неориентированные графы. Основные понятия. Матричное задание графа.

1.5.2. Пути в графе.(АЗ: 4, СРС: 3)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Связные графы и компоненты связности. Поиск путей в графе. Экстремальные пути. Специальные пути в графе. Эйлеровы и гамильтоновы пути.

Специальные пути в графе. Метод латинской композиции. Эйлеровы и гамильтоновы пути.

1.5.3. Транспортные сети.(АЗ: 4, СРС: 3)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Транспортные сети. Основные определения. Поток по сети.

Задача о наибольшем потоке в сетях.

2.1.1. Деревья и циклы.(АЗ: 4, СРС: 0)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Деревья. Свойства деревьев. Основное дерево графа. Минимальное остовное дерево.

Вектор-циклы. Цикломатическое число. Хроматическое число. Приложение к теории электрических цепей.

2.1.2. Внутренние и внешние устойчивые подмножества. Ядро.(АЗ: 2, СРС: 0)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Порядковая функция и функция Гранди. Внутренняя и внешняя устойчивость графа. Ядро графа.

2.1.3. Планарные графы.(АЗ: 2, СРС: 0)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Планарные графы. Формулы Эйлера. Существование непланарных графов. Теорема Понтрягина-Куратовского (формулировка).

2.2.1. Эффективная вычислимость.(АЗ: 2, СРС: 2)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Понятие алгоритма.

Примитивно рекурсивные и частично-рекурсивные функции. Тезис Черча.

2.2.2. Вычислимость по Тьюрингу(АЗ: 2, СРС: 2)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Машины Тьюринга. Вычислимость по Тьюрингу. Примеры неразрешимых алгоритмических проблем.

2.3.1. Полугруппы и группы(АЗ: 8, СРС: 2)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Бинарные операции. Полугруппы. Проблема тождества слов. Моноиды. Определение и ростейшие свойства. Группы. Порядок элемнта группы.

Подгруппы.Циклические подгруппы.Группы преобразований. Группы подстановок. Изоморфизм групп.

Смежные классы. Теорема Лагранжа. Нормальный делитель.

Фактор-группа. Гомоморфизм групп.

2.3.2. Элементы теории кодирования.(АЗ: 2, СРС: 0)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Двоичные групповые коды. Коды Хемминга.

2.3.3. Элементы теории колец и полей.(АЗ: 2, СРС: 2)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Кольцо. Поле. Простейшие свойства. Подкольцо. Классы вычетов. Фактор-кольцо. Кольца многочленов.

2.3.4. Представление группы графом.(АЗ: 2, СРС: 0)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Представление группы графом с одной и двумя образующими.

2.4.1. Комбинаторные схемы.(АЗ: 6, СРС: 0)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Теоремы о числе однозначных отображений. Перестановки. Размещения. Сочетания. Сочетания с повторениями.

Число функциональных отображений. Число целочисленных решений системы уравнений. Разбиения.

Полиномиальная формула. Формула включений и исключений.

2.4.2. Вычислительная сложность алгоритмов(АЗ: 2, СРС: 0)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Понятие вычислительной сложности алгоритма.

Линейная, полиномиальная, экспоненциальная сложность. Примеры алгоритмов.

1. Практические занятия

1.1.1. Основные понятия алгебры множеств.(АЗ: 2, СРС: 0)

Форма организации: Практическое занятие

Описание: Методы доказательства тождеств алгебры множеств. Диаграммы Эйлера-Венна.

Решение систем теоретико-множественных уравнений

1.2.1. Прямое произведение множеств. Бинарные отношения (АЗ: 2, СРС: 0)

Форма организации: Практическое занятие

Описание: Доказательство тождеств с операцией прямого произведения. Операции с бинарными отношениями.

Нахождение Области определении, множества значений бинарного отношения, обратного отношения, композиции бинарных отношений

1.2.2. Отношения порядка и эквивалентности.(АЗ: 2, СРС: 0)

Форма организации: Практическое занятие

Описание: Проверка свойств отношения.

Нахождение наибольшего, наименьшего максимальных, минимальных элементов частично упорядоченного множества. Построение линейного порядка.

Нахождение классов эквивалентности.

1.2.3. Мощность множества. Функции(АЗ: 2, СРС: 0)

Форма организации: Практическое занятие

Описание: Нахождение мощности множеств.

Проверка свойств функций. Нахождений области определения и множества значений функции. Композиция функций. Обратная функция

1.3.1. Формулы логики высказываний(АЗ: 2, СРС: 0)

Форма организации: Практическое занятие

Описание: Составление формул по высказываниям.

Составление таблиц истинности для формул. Проверка выполнимости и истинности формул. Доказательство тождеств.

1.3.2. ДНФ, КНФ, СДНФ, СКНФ.(АЗ: 2, СРС: 0)

Форма организации: Практическое занятие

Описание: Приведение формул логики высказываний к СДНФ, СКНФ методом равносильных преобразований. Нахождение СДНФ, СКНФ по таблице соответствующей булевой функции.

1.3.3. Минимальная ДНФ. Правильные рассуждения.(АЗ: 2, СРС: 0)

Форма организации: Практическое занятие

Описание: Нахождение минимальной ДНФ.

Проектирование переключательных схем.

Анализ правильности рассуждений в логике высказываний.

1.3.4. Полные системы булевых функций(АЗ: 4, СРС: 0)

Форма организации: Практическое занятие

Описание: Проверка полноты и независимости систем булевых функций. Нахождение многочлена Жегалкина.

Проверка полноты и независимости систем булевых функций с использованием теории Поста.

1.3.5. Исчисление предикатов(АЗ: 2, СРС: 0)

Форма организации: Практическое занятие

Описание: Построение выводов в исчислении высказываний

1.4.1. Формулы логики предикатов(АЗ: 2, СРС: 0)

Форма организации: Практическое занятие

Описание: Составление формул логики предикатов в заданной интерпретации. Проверка общезначимости формул. Доказательство раносильности формул.

1.4.2. Предваренные нормальные формы(АЗ: 2, СРС: 0)

Форма организации: Практическое занятие

Описание: Построение предваренной нормальной формы для формул логики предикатов.

1.5.1. Матричное задание графа(АЗ: 2, СРС: 0)

Форма организации: Практическое занятие

Описание: Нахождение матриц смежности, инцидентности, связности по изображению графа. Построение изображение графа по матрицам инцидентности и связности. Нахождение матриц связности по матрице смежности.

2.2.1. Эффективная вычислимость(АЗ: 2, СРС: 0)

Форма организации: Практическое занятие

Описание: Построение функций из заданных с помощью операторов суперпозиции, примитивной рекурсии и минимизации.

Доказательство примитивной рекурсивности и частичной рекурсивности функций.

2.2.2. Машины Тьюринга(АЗ: 2, СРС: 0)

Форма организации: Практическое занятие

Описание: Составление программ машины Тьюринга

2.3.1. Полугруппы и группы(АЗ: 8, СРС: 0)

Форма организации: Практическое занятие

Описание: Проверка является ли данное множество полугруппой или гуппой.

Нахождение порядка элемента группы. Возведение подстановок в степень. Проверка изоморфизма групп.

Нахождение левых и правых смежных классов. Проверка является ли подгруппа нормальным делителем.

Проверка является ли данное множество фактор-группой. Примеры гомоморфизмов.

2.3.2. Элементы теории кодирования.(АЗ: 2, СРС: 0)

Форма организации: Практическое занятие

Описание: Нахождение кодовых слов для кода Хемминга. Нахождение исходного слова по кодовому.

2.3.3. Кольца и поля(АЗ: 2, СРС: 0)

Форма организации: Практическое занятие

Описание: Проверка является ли данное множество с указанными операциями кольцом или поем.

2.3.4. Контрольное занятие(АЗ: 2, СРС: 0)

Форма организации: Практическое занятие

Описание: Повторение тем семестра

2.4.1. Комбинаторные схемы(АЗ: 6, СРС: 0)

Форма организации: Практическое занятие

Описание: Нахождение числа размещений и сочетаний с повторениями и без.

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

Вычисление коэффициентов полиномиальной формулы. Решение задач на формулу включений и исключений.

2.4.2. Вычислительная сложность алгоритмов(АЗ: 2, СРС: 0)

Форма организации: Практическое занятие

Описание: Оценка вычислительной сложности алгоритмов

Характеристики

Список файлов учебной работы