теория алгоритмов

Программа курса «Теория алгоритмов. 1. Организационно-методический раздел. 1.1 Название курса. Теория алгоритмов. Направление - 552800 Информатика и вычислительная техника. Раздел - общие математические и естественнонаучные дисциплины. Компонент - федеральный. 1.2 Цели и задачи курса. Дисциплина " Теория алгоритмов" предназначена для изучения прикладных методов в математической логике, применяющихся в программировании. Основной целью освоения дисциплины является изучения метода резолюций и прикладных логик. Для достижения поставленной цели выделяются задачи курса: 1) изучение теоретической части курса в соответствии с программой 2) решение цикла задач по курсу в соответствии с программой 3) выполнение контрольных работ 4) сдача зачета и экзамена в соответствии с учебным планом. 1.3 Требования к уровню освоения содержания курса. По окончании изучения указанной дисциплины студент должен - иметь представление о месте и роли изучаемой дисциплины среди других наук; - знать содержание программы курса; - знать основные типы временных и нечетких логик, уметь пользоваться методом резолюций. 1.4 Формы контроля Итоговый контроль. Для контроля усвоения дисциплины учебным планом предусмотрены экзамен и зачет. Текущий контроль. В течение семестра выполняются контрольные работы и принимаются домашние задания. Выполнение указанных видов работ является обязательным для всех студентов, а результаты текущего контроля служат основанием для выставления оценок в ведомость контрольной недели на факультете. 2 2.1 Содержание дисциплины. Тематический план курса. Количество Наименование разделов Лаборатор и тем Лекци Семина и ры ные работы Теория моделей 4 4 0 Прикладные логики 18 18 0 Логическое 10 10 0 программирование Итого по курсу: 32 32 0 часов Самостояте ль-ная работа 2 9 5 Всег о часо в 10 45 25 16 80 1 2.2 Содержание отдельных разделов и тем. Теория моделей. 1. Скулемизации. 2. Теорема Эрбрана Прикладые логики. 1. Временная логика высказываний (семантика). Структуры Крипке. Примеры модальностей. 2. Синтаксис временной логики высказываний. Теорема о корректности. 3. Теорема о дедукции. 4. Теорема о замене. 5. Полные и непротиворечивые множества формул. Их свойства. 6. Теорема о существовании моделей. 7. Слабая теорема о полноте. 8. Примеры других исчислений (с ветвящимся временем) 9. Временная логика первого порядка. 10. Нечеткие логики. Нечеткозначные логики. Нечеткие лингвистические логики. Теория приблизительных рассуждений (Fuzzy Logic). Логическое программирование. 1. Подстановки. Унификаторы. 2. Алгоритм унификации. Теорема об унификации. 3. Резолюции. Резольвента. Понятие вывода. 4. Теорема о корректности. 5. Модели Эрбрана. Наименьшая модель Эрбрана. Теорема о наименьшей модели Эрбрана. 6. Множество решений программы. Теорема о множестве решений программы. 7. Теорема о полноте резолюций. 8. Алгоритмические свойства наименьшей модели Эрбрана. 3 Учебно-методическое обеспечение дисциплины 3.1 Образцы вопросов для подготовки к экзамену (дифференцированному зачету, зачету). В экзаменационный билет входит один вопрос из прикладных логик и родин вопрос из логического программирования. Дополнительная задача дается по усмотрению экзаменатора. Ниже приводятся образцы экзаменационных вопросов: 1. Скулемовские функции. Подстановки. Композиция подстановок. Свойства композиции. 2.