Учебно-методический комплекс дисциплины «Математическая логика и теория алгоритмов»

Скачать 374.54 Kb.

Название	Учебно-методический комплекс дисциплины «Математическая логика и теория алгоритмов»
страница	2/5
Дата публикации	15.03.2015
Размер	374.54 Kb.
Тип	Учебно-методический комплекс

100-bal.ru > Информатика > Учебно-методический комплекс

1 2 3 4 5

Начальник методического отдела БГТУ

___________________/ Емельянов В.Ю. /

САНКТ-ПЕТЕРБУРГ

2008 г.
ЛИСТ СОГЛАСОВАНИЯ
Рабочая программа составлена на основании государственного образовательного стандарта ВПО и рассмотрена на заседании кафедры И7
“__” _______ 2008 г Заведующий кафедрой __________________/ С.Д. Шапорев /
Программа согласована в учебно-методической комиссии факультета «И»
"__"_____2008 г. Председатель МК ________________________/ В.В. Смирнов /
СОГЛАСОВАНО:
Заведующий кафедрой И3 _________________________________________ /О.С. Ипатов /
"__"______2008 г.
Заведующий кафедрой И5 _________________________________________ /Н.Н. Смирнова /
"__"______2008 г.
Учебная дисциплина обеспечена основной литературой
Директор библиотеки БГТУ___________________________/ Н. В. Сесина /
"__"_____2008 г

Выдержка из ГОС ВПО РФ (2000 г.)

по направлению 230100 Информатика и вычислительная техника

для специальности 230102 Автоматизированные системы обработки информации и управления

по минимуму содержания программы дисциплины, входящей в цикл общих математических и естественнонаучных дисциплин из перечня обязательных дисциплин федерального компонента ГОС

ЕН.Ф.01.04 Общее число часов: 100
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ
Логика высказываний; логика предикатов; исчисления; непротиворечивость; полнота; синтаксис и семантика языка логики предикатов. Клаузальная форма. Метод резолюций в логике предикатов. Принцип логического программирования. Темпоральные логики; нечеткая и модальные логики; нечеткая арифметика; алгоритмическая логика Ч. Хоара. Логика высказываний. Логическое следование, принцип дедукции. Метод резолюций. Аксиоматические системы, формальный вывод. Метатеория формальных систем. Понятие алгоритмической системы. Рекурсивные функции. Формализация понятия алгоритма; Машина Тьюринга. Тезис Черча; Алгоритмически неразрешимые проблемы. Меры сложности алгоритмов. Легко и трудноразрешимые задачи. Классы задач P и NP. NP – полные задачи. Понятие сложности вычислений; эффективные алгоритмы. Основы нечеткой логики. Элементы алгоритмической логики.

ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ.

ТРЕБОВАНИЯ К УРОВНЮ ОСВОЕНИЯ СОДЕРЖАНИЯ УЧЕБНОЙ ДИСЦИПЛИНЫ.

Преподавание данной дисциплины, предусмотренное обязательным минимумом содержания основной образовательной программы специальности 230102, преследует и реализует следующие цели и возможности:

развивает способности студентов к строгому абстрактно-формальному логическому и алгоритмическому мышлению;
является существенной частью общего математического образования студентов, ориентирует их на использование методов математической логики при решении прикладных задач.

Вопросы, изучаемые в курсе математической логики и теории алгоритмов, базируются на общематематических курсах, изучаемых студентами на предыдущих семестрах, в частности, в курсах математического анализа, вычислительной и дискретной математики.

В результате изучения дисциплины студенты должны:

знать основные понятия и факты исчисления высказываний, алгебры логики, исчисления предикатов, теории аксиоматических систем и доказательств;

знать определение и основные характеристики алгоритма, понятия, факты и проблемы теории алгоритмов;

уметь проводить формально-логические построения на основе теории и формул математической логики;

уметь определять и строить вычислимые функции на основе рекурсивных алгоритмов;

уметь строить машины Тьюринга, вычисляющие заданные функции и по программе машины Тьюринга определять её характеристики;

представлять значение и строение математических теорий как аксиоматических теорий, построенных на основе выбранных систем аксиом, строить интерпретации формул теории и её модели;

уметь строить доказательства теорем в наиболее значимых теориях исчисления высказываний и предикатов.

ТЕМАТИЧЕСКИЙ ПЛАН И СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

( с распределением общего бюджета времени в часах)

КУРС	СЕМЕСТР	Раздел дисциплины, содержание	ВСЕГО	АУДИТОРНЫЕ				Самостоятельная работа студентов
				Лекции	Аудиторный практикум		Лабораторный практикум
2	3	Раздел I. Основы математической логики	42	12	16			14
		Тема 1. Логика высказываний Высказывание как первичное понятие алгебры логики. Основные операции над высказываниями. Пропозициональные связки. Истинностные функции. Формулы алгебры высказываний, их виды. Метод истинностных таблиц. Три группы равносильных формул. Равносильные преобразования формул. Полные системы связок. Понятие о нечётких и модальных логиках.	6	2	2			2
		Тема 2. Функции алгебры логики Понятие булевой функции (функции двузначной логики). Элементарные булевы функции, логические связки. Формулы алгебры логики, функции, их реализующие. Основные эквивалентные формулы алгебры логики. Метод истинностных таблиц. Представление произвольной функции алгебры логики в виде формулы алгебры логики. Свойства совершенства. Закон двойственности и двойственные операции. Нормальные формы. Алгоритмы приведения к совершенным дизъюнктивной и конъюнктивной нормальным формам. Полиномы Жегалкина. Двойственность. Принцип двойственности. Теорема Поста. Проблемы полноты и разрешимости.	16	4	6			6
		Тема 3. Приложения алгебры логики Релейно-контактные схемы, их математическое описание и методы построения. Решение логических задач.	10	2	4			4
		Тема 4. Логика предикатов Кванторные операции как обобщения операций конъюнкции и дизъюнкции. Предикаты. Синтаксис и семантика языка логики предикатов. Формулы логики предикатов. Свободные и связанные переменные. Интерпретации, выполнимость и общезначимость формул логики предикатов. Равносильности логики предикатов. Приведенная нормальная форма. Общезначимость и выполнимость формул логики предикатов. Эквивалентные формулы логики предикатов. Примеры распознавания общезначимости в частных случаях. Запись математических предложений на языке логики предикатов. Запись математических определений. Формулировка математических теорем. Построение противоположных утверждений. Доказательство методом от противного. Формулировка обратных и противоположных теорем. Формулировка необходимых и достаточных условий.	10	4	4			2
		Раздел II. Аксиоматические теории	34	12	10			12
		Тема 5. Исчисление высказываний Задание формальной аксиоматической теории: алфавит, система аксиом, основные и производные правила вывода. Основные понятия теории доказательств: гипотеза, следствие, вывод, теорема, разрешимая и неразрешимая теория. Построение аксиоматической теории исчисления высказываний. Основные и производные правила вывода. Понятие выводимости формул. Правило одновременной подстановки, правило сложного заключения, правило силлогизма, правило контрпозиции, правило снятия двойного отрицания. Формулы и правила, выводимые из совокупности формул. Правила вывода теории исчисления высказываний. Теорема дедукции, обобщение теоремы дедукции. Закон перестановки посылок, законы соединения и разъединения посылок. Примеры доказательств некоторых теорем теории исчисления высказываний. Теории исчисления высказываний Клини, Гильберта-Аккермана, Россера, интуиционистская.	18	6	6				6
		Тема 6. Исчисление предикатов Построение аксиоматической теории исчисления предикатов первого порядка. Правила вывода теории исчисления предикатов. Коллизия переменных в формулах исчисления предикатов. Правила вывода. Замена переменных: а) замена переменного высказывания, б) замена переменного предиката, в) замена свободной предметной переменной, г) правило переименования связанных предметных переменных. Правила связывания квантором. Теорема дедукции. Эквивалентные и дедуктивно эквивалентные формулы. Непротиворечивость исчисления предикатов. Полнота в узком и широком смысле. Примеры доказательств некоторых теорем. Примеры теорий первого порядка. Метод резолюций в логике предикатов.	12	4	4				4
		Тема 7. Проблемы полноты и разрешимости формальных систем Метаязык и метатеория. Проблемы разрешимости, полноты и непротиворечивости формальных аксиоматических теорий. Теоремы о полноте и непротиворечивости теории исчисления высказываний. Непротиворечивость теорий первого порядка. Теорема Гёделя о полноте.	4	2					2
		Раздел III. Теория вычислимых функций	26	10	8				8
		Тема 8. Формализация понятия алгоритма. Рекурсивные функции Эффективная вычислимость функции. Уточнение понятия алгоритма. Разрешимые и перечислимые множества. Примитивная рекурсия. Примитивно-рекурсивные функции. Оператор минимизации. Частично-рекурсивные функции. Общерекурсивные функции. Примитивная рекурсивность и общерекурсивность некоторых арифметических функций. Тезис Чёрча. Словарные множества и функции. Операции над словарными функциями. Словарная примитивная рекурсия.	8	4	2				2
		Тема 9. Машины Тьюринга Компоненты машины Тьюринга: внешний и внутренний алфавиты, команды и программа. Конфигурация машины Тьюринга. Распознавание применимости машины Тьюринга к начальной конфигурации. Понятие функции, вычислимой по Тьюрингу. Примеры машин Тьюринга, вычисляющих некоторые арифметические функции. Тезис Тьюринга. Действия над машинами Тьюринга.	14	4	6				4
		Тема 10. Проблемы алгоритмической неразрешимости и сложности алгоритмов Алгоритмически неразрешимые проблемы. Меры сложности алгоритмов. Легко и трудноразрешимые задачи. Классы задач P и NP. NP – полные задачи. Понятие сложности вычислений; эффективные алгоритмы.	4	2				2
		Итого за 3 семестр:	102	34		34		34

1 2 3 4 5

Похожие:

	Учебно-методический комплекс по дисциплине математическая логика и теория алгоритмов Курс математическая логика и теория алгоритмов обеспечивает приобретение знаний в соответствии с государственным образовательным...		Рабочая программа составлена в соответствии с требованиями фгос впо... Дёгтев А. Н. Теория алгоритмов. Учебно-методический комплекс. Рабочая программа для студентов направления 010100. 62 – математика,...
	Программа дисциплины «Информатика, математическая логика и теория... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направлений подготовки 231000....		Учебно-методический комплекс дисциплины логика федеральное агентство... Логика, изучающая познающее мышление и применяемая как средство познания, возникла и развивалась в рамках теории познания, и в настоящее...
	Учебно-методический комплекс дисциплины специальность: 050202 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «Математическая логика» для студентов очной формы обучения по специальности 050202...		Рефератов по курсу «Математическая логика и теория алгоритмов» Темпоральные логики высказываний линейного времени и вычислительных деревьев: их синтаксис и семантика
	Радиофизический факультет Фгос впо, содействует формированию мировоззрения и системного мышления. Целью преподавания дисциплины «Математическая логика и теория...		Рабочая программа составлена в соответствии с требованиями фгос впо... Дёгтев А. Н. Теория автоматов. Учебно-методический комплекс. Рабочая программа для студентов направления 010100. 62 – математика,...
	Вопросы к государственному экзамену по информатике Дискретная математика. Теория алгоритмов. Математическая логика. Численные методы. Теоретические основы информатики. Исследование...		Учебно-методический комплекс дисциплины «логика» Учебно-методический комплекс «Логика» предназначен для студентов I курса специальности 030900. 62 Юриспруденция, составлен в соответствии...
	Учебно-методический комплекс дисциплины математическая логика Основная образовательная программа ...		Рабочая программа для студентов очной формы обучения, направление... Иванов Д. И. Математическая логика и теория алгоритмов. Учебно-методический комплекс. Рабочая программа для студентов очной формы...
	Рабочая программа дисциплины «Математическая логика и теория алгоритмов» Рабочая программа предназначена для преподавания дисциплины вариативной части профессионального цикла студентам очной формы обучения...		Рабочая программа для студентов очной формы обучения направление... Иванов Д. И. Математическая логика и теория алгоритмов. Учебно-методический комплекс. Рабочая программа для студентов очной формы...
	Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов» Методические указания предназначены для студентов, обучающихся по направлению 020400. 68 «Биология», магистерская программа 020400....		Программа вступительных испытаний по дисциплине «Математика» Курс математическая логика и теория алгоритмов обеспечивает приобретение знаний в соответствии с государственным образовательным...

Школьные материалы