Шпаргалка ДНУ Теория алгоритмов ФФЭКС 3 курс
55 вопросов.
Вопросы:
Понятие алгоритма. Алгоритм Евклида.
Основные свойства алгоритмов.
Метод математической индукции как метод доказательства справедливости алгоритмов.
Метод доказательства справедливости произвольного алгоритма.
Множество, подмножество, множество-степень. Операции над множествами. Отношения между множествами. Разбиение на систему множеств.
Кортеж. Прямое произведение множеств. Степени множеств. Проекции множеств.
Соответствия. Обратное соответствие. Композиция соответствий.
Отображения и их свойства. Обратное отображение.
Инъективное, сюръективное и биективное отображения.
Отображения, заданные на одном множестве.
Функция как отображение. Способы задания функции.
Сужение функции. Обратная функция. Функция времени.
Функционалы.
Операторы.
Отношения. Основные свойства отношений.
Операции над бинарными отношениями.
Отношение эквивалентности. Классы эквивалентности.
Отношения порядка. Отношение доминирования.
Граф как отношение. Подграф. Частичный граф.
Ориентированные графы. Неориентированные графы. Дерево.
Отношение порядка и отношение эквивалентности на графе.
Понятие группы. Мультипликативная группа. Аддитивная группа.
Группоид, полугруппа, моноид, группа.
Примеры групп (с доказательством).
Степени элементов группы. Порядок элемента группы.
Подгруппа. Истинные и тривиальные подгруппы.
Образующие элементы группы. Циклическая группа.
Кольцо. Поле. Простое поле GF(p), p – простое число.
Абстрактный алфавит. Алфавитный оператор.
Кодирующие отображения. Условия обратимости кодирования.
Отображения в стандартном алфавите. Сопряженный алфавитный оператор.
Способы задания алфавитного оператора. Общее определение алгоритма. Свойства алфавитных операторов и алгоритмов.
Рекурсивные и вычислимые функции. Тезис Черча.
Операции суперпозиции, примитивной рекурсии и наименьшего корня.
Примитивно рекурсивные функции. Частично рекурсивные функции и их значение в теории алгоритмов.
Машина Тьюринга. Принцип работы машины Тьюринга.
Программирование машины Тьюринга.
Универсальная машина Тьюринга.
Композит машин Тьюринга.
Итерация машин Тьюринга.
Алгоритмическая система Маркова. Граф-схемы алгоритмов.
Обобщенные нормальные алгоритмы Маркова.
Нормальные алгоритмы Маркова. Принцип нормализации.
Нормальный алгоритм Маркова над алфавитом.
Композиция нормальных алгоритмов Маркова.
Построение универсального алгоритма Маркова.
Операторные алгоритмические системы.
Операторные алгоритмы Ляпунова.
Блок-схемный метод алгоритмизации.
Алгоритмически неразрешимые проблемы. Значение теорем Геделя.
Представление знаний. Основные свойства знаний.
Основные модели представления знаний.
Семантические сети.
Фреймовые представления знаний.
Логические модели представления знаний.
55 вопросов.
Вопросы:
Понятие алгоритма. Алгоритм Евклида.
Основные свойства алгоритмов.
Метод математической индукции как метод доказательства справедливости алгоритмов.
Метод доказательства справедливости произвольного алгоритма.
Множество, подмножество, множество-степень. Операции над множествами. Отношения между множествами. Разбиение на систему множеств.
Кортеж. Прямое произведение множеств. Степени множеств. Проекции множеств.
Соответствия. Обратное соответствие. Композиция соответствий.
Отображения и их свойства. Обратное отображение.
Инъективное, сюръективное и биективное отображения.
Отображения, заданные на одном множестве.
Функция как отображение. Способы задания функции.
Сужение функции. Обратная функция. Функция времени.
Функционалы.
Операторы.
Отношения. Основные свойства отношений.
Операции над бинарными отношениями.
Отношение эквивалентности. Классы эквивалентности.
Отношения порядка. Отношение доминирования.
Граф как отношение. Подграф. Частичный граф.
Ориентированные графы. Неориентированные графы. Дерево.
Отношение порядка и отношение эквивалентности на графе.
Понятие группы. Мультипликативная группа. Аддитивная группа.
Группоид, полугруппа, моноид, группа.
Примеры групп (с доказательством).
Степени элементов группы. Порядок элемента группы.
Подгруппа. Истинные и тривиальные подгруппы.
Образующие элементы группы. Циклическая группа.
Кольцо. Поле. Простое поле GF(p), p – простое число.
Абстрактный алфавит. Алфавитный оператор.
Кодирующие отображения. Условия обратимости кодирования.
Отображения в стандартном алфавите. Сопряженный алфавитный оператор.
Способы задания алфавитного оператора. Общее определение алгоритма. Свойства алфавитных операторов и алгоритмов.
Рекурсивные и вычислимые функции. Тезис Черча.
Операции суперпозиции, примитивной рекурсии и наименьшего корня.
Примитивно рекурсивные функции. Частично рекурсивные функции и их значение в теории алгоритмов.
Машина Тьюринга. Принцип работы машины Тьюринга.
Программирование машины Тьюринга.
Универсальная машина Тьюринга.
Композит машин Тьюринга.
Итерация машин Тьюринга.
Алгоритмическая система Маркова. Граф-схемы алгоритмов.
Обобщенные нормальные алгоритмы Маркова.
Нормальные алгоритмы Маркова. Принцип нормализации.
Нормальный алгоритм Маркова над алфавитом.
Композиция нормальных алгоритмов Маркова.
Построение универсального алгоритма Маркова.
Операторные алгоритмические системы.
Операторные алгоритмы Ляпунова.
Блок-схемный метод алгоритмизации.
Алгоритмически неразрешимые проблемы. Значение теорем Геделя.
Представление знаний. Основные свойства знаний.
Основные модели представления знаний.
Семантические сети.
Фреймовые представления знаний.
Логические модели представления знаний.