Бакалавриат
2020/2021
Логика и алгоритмы
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус:
Курс обязательный (Совместный бакалавриат НИУ ВШЭ и ЦПМ)
Направление:
01.03.01. Математика
Кто читает:
Факультет математики
Где читается:
Факультет математики
Когда читается:
2-й курс, 3, 4 модуль
Формат изучения:
без онлайн-курса
Язык:
русский
Кредиты:
5
Контактные часы:
84
Программа дисциплины
Аннотация
Целями освоения дисциплины Логика и алгоритмы являются • получение представления об основных структурах, объектах и задачах математической логики и теории алгоритмов; • получение знания об основных результатах классической математической логики и теории алгоритмов; • получение представления о методах работы с формализованными логическими теориями; • развитие логической и алгоритмической интуиции. В результате освоения дисциплины студент должен: • Владеть основными методами преобразования логических выражений. • Владеть основными понятиями теории множеств. • Уметь записывать содержательные математические утверждения в языке исчисления предикатов. • Владеть методами доказательства теорем в исчислении высказываний и исчислении предикатов. • Владеть основными понятиями теории алгоритмов: вычислимость, разрешимость, перечислимость. • Уметь строить модели формул и теорий первого порядка. • Уметь реализовывать простые алгоритмы с помощью машин Тьюринга. • Знать важнейшие теоремы классической теории алгоритмов. • Уметь решать простые задачи о неразрешимости алгоритмических проблем. Для специализации математика настоящая дисциплина является базовой, относится к математическому и естественнонаучному циклу. Основные положения дисциплины должны быть использованы в дальнейшем при изучении следующих дисциплин: математический анализ, алгебра, топология.
Цель освоения дисциплины
- Получение представления об основных структурах, объектах и задачах математической логики и теории алгоритмов
- Получение знания об основных результатах классической математической логики и теории алгоритмов;
- Получение представления о методах работы с формализованными логическими теориями;
- Развитие логической и алгоритмической интуиции.
Планируемые результаты обучения
- Владеть основными методами преобразования логических выражений, владеть основными понятиями теории множеств.
- Владеть методами доказательства теорем в исчислении высказываний
- Уметь записывать содержательные математические утверждения в языке исчисления предикатов, и методами доказательства теорем в исчислении предикатов
- Владеть основными понятиями теории алгоритмов: вычислимость, разрешимость, перечислимость. Уметь строить модели формул и теорий первого порядка. Уметь реализовывать простые алгоритмы с помощью машин Тьюринга. Знать важнейшие теоремы классической теории алгоритмов. Уметь решать простые задачи о неразрешимости алгоритмических проблем
Содержание учебной дисциплины
- Логика высказываний и элементы теории множеств
- Логика предикатов
- Теория алгоритмов
Элементы контроля
- листки
- экзаменИтоговая оценка по дисциплине вычисляется по формуле 0,4KP + 0,3Л+ 0,3Э. При этом те студенты, которые до экзамена имеют оценку 8 и выше по формуле 0,5KP + 0,5Л, освобождаются от экзамена и получают эту оценку в качестве итоговой.
- контрольная
