Радиофизический факультет

Скачать 124.1 Kb.

Название	Радиофизический факультет
Дата публикации	21.01.2015
Размер	124.1 Kb.
Тип	Документы

100-bal.ru > Математика > Документы

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Нижегородский государственный университет им. Н.И. Лобачевского»

Радиофизический факультет

Кафедра математики

УТВЕРЖДАЮ

Декан радиофизического факультета
____________________Якимов А.В.

«18» мая 2011 г.

Учебная программа
Дисциплины С3.Р2 «Математическая логика и теория алгоритмов»
по специальности 090302 «Информационная безопасность телекоммуникационных систем»

Нижний Новгород

2011 г.

1. Цели и задачи дисциплины

Дисциплина «Математическая логика и теория алгоритмов» обеспечивает приобретение знаний и умений в соответствии с ФГОС ВПО, содействует формированию мировоззрения и системного мышления. Целью преподавания дисциплины «Математическая логика и теория алгоритмов» является подготовка специалистов к деятельности в сфере разработки, исследования и эксплуатации информационных систем.
2. Место дисциплины в структуре программы специалиста

Дисциплина «Математическая логика и теория алгоритмов» относится к дисциплинам вариативной части профессионального цикла основной образовательной программы по специальности 090302 «Информационная безопасность телекоммуникационных систем», преподается в 3 семестре.
3. Требования к уровню освоения содержания дисциплины

Изучение дисциплины «Математическая логика и теория алгоритмов» обеспечивает овладение следующими общекультурными компетенциями:

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

Изучение дисциплины «Математическая логика и теория алгоритмов» обеспечивает овладение следующими профессиональными компетенциями:

способностью выявлять естественнонаучную сущность проблем, возникающих в ходе профессиональной деятельности, и применять соответствующий физико-математический аппарат для их формализации, анализа и выработки решения (ПК-1);
способностью применять математический аппарат, в том числе с использованием вычислительной техники, для решения профессиональных задач (ПК-2);
способностью применять методологию научных исследований в профессиональной деятельности, в том числе в работе над междисциплинарными и инновационными проектами (ПК-5).

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

познакомиться с принципами построения формальных теорий, исключающими возможность возникновения противоречий;

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

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

4. Объём дисциплины и виды учебной работы:

Общая трудоемкость дисциплины составляет 4 зачетные единицы, 144 часа.

Виды учебной работы	Всего часов	Семестры
Общая трудоемкость дисциплины	144	3
Аудиторные занятия	51	51
Лекции	34	34
Практические занятия (ПЗ)	17	17
Семинары (С)	–	–
Лабораторные работы (ЛР)	–	–
Другие виды аудиторных занятий	–	–
Самостоятельная работа	57	57
Курсовой проект (работа)	–	–
Расчетно-графическая работа	–	–
Реферат	–	–
Другие виды самостоятельной работы	–	–
Вид итогового контроля (зачет, экзамен)	экзамен (36)	экзамен (36)

5. Содержание дисциплины

5.1. Разделы дисциплины и виды занятий

№ п/п	Раздел дисциплины	Лекции	ПЗ (или С)	ЛР
1	Введение.	2	-	-
2	Исчисление высказываний.	8	6	-
3	Исчисление предикатов.	10	5	-
4	Рекурсивные функции.	6	2	-
5	Машина Тьюринга.	4	2	-
6	Нормальные алгоритмы Маркова.	2	2	-
7	Формальная арифметика.	2	-	-

5.2. Содержание разделов дисциплины
Раздел 1. Введение.

Принципы построения формальных теорий. Определение и виды формальных теорий.
Раздел 2. Математическая логика.

2.1. Исчисление высказываний.

Язык, системы аксиом и основные правила вывода исчисления высказываний. Производные правила вывода в исчислении высказываний. Теорема дедукции. Теорема об общезначимых формулах в исчислении высказываний. Проблема разрешимости в логике высказываний и методы ее решения. Метод резолюций в исчислении высказываний. Проблемы аксиоматического исчисления высказываний.
2.2. Исчисление предикатов.

Определение предиката. Операции над предикатами, кванторы существования и всеобщности. Формулы логики предикатов. Свободные и связанные переменные. Равносильность формул в логике предикатов и в различных интерпретациях. Основные равносильности. Нормальные формы логики предикатов. Выполнимость и общезначимость для предикатов. Основные общезначимые формулы в логике предикатов. Теоремы об общезначимости и выполнимости в логике предикатов. Проблема разрешимости в общем случае (теорема Черча) и для формул, содержащих только одноместные предикатные символы. Язык, система аксиом и основные правила вывода исчисления предикатов. Производные правила вывода в исчислении предикатов: правила переименования связанных переменных, правило связывания квантором. Теорема об общезначимых формулах в исчислении предикатов. Проблемы аксиоматического исчисления предикатов.
Раздел 3. Теория алгоритмов.

3.1. Формализация понятия алгоритма.

Характерные черты произвольного алгоритма. Необходимость формализации алгоритма. Универсальные алгоритмические модели.

3.2. Рекурсивные функции.

Понятие рекурсивных функций. Примитивно рекурсивные функции: базовые функции и элементарные операции. Простейшие примитивно рекурсивные функции. Теорема о примитивной рекурсивности суммы и произведения примитивно рекурсивных функций. Ограниченный оператор минимизации и его применения. Теорема Робинсона об одноместных примитивно рекурсивных функциях. Неограниченный оператор минимизации. Частично рекурсивные функции. Тезис Черча о вычислимых функциях. Общерекурсивные функции. Функция Аккермана. Теорема Аккермана.

3.3. Машина Тьюринга.

Словарные функции. Определение машины Тьюринга. Способы задания машин Тьюринга. Композиция машин Тьюринга. Неприменимость машины Тьюринга к исходной информации. Тезис Тьюринга. Теорема о соответствии между частично рекурсивными функциями и функциями, вычислимыми по Тьюрингу.

3.4. Нормальные алгоритмы Маркова.

Определение нормального алгоритма Маркова и порядок его работы. Тезис Маркова. Эквивалентность машин Тьюринга и нормальных алгоритмов Маркова.

3.5. Неразрешимость алгоритмических проблем.

Сравнительный анализ трех типов алгоритмических моделей. Оценка сложности алгоритма. Проблема остановки машины Тьюринга и проблема ее самоприменимости. Теорема Райса и ее смысл. Проблема эквивалентности слов для ассоциативных исчислений и проблема соответствий Поста.
Раздел 4. Теории первого порядка.

Особенности прикладных исчислений. Свойства равенства в теории с равенством. Формальная арифметика. Теоремы Геделя о неполноте (без доказательства) и их смысл.
5.3. План практических занятий

Формулы логики высказываний. Правильность рассуждений.
Исчисление высказываний: правила вывода и доказуемость формул.
Алгоритмы Квайна и резолюций проверки общезначимости формул исчисления высказываний.
Логические и кванторные операции над предикатами.
Формулы логики предикатов. Их выполнимость и общезначимость. Нормальные формы. Вывод формул из аксиом исчисления предикатов.
Контрольная работа по темам “Исчисление высказываний” и “Исчисление предикатов”.
Рекурсивные функции.
Составление программ для машин Тьюринга.
Нормальные алгоритмы Маркова.

6. Лабораторный практикум

Не предусмотрен.
7. Учебно-методическое обеспечение дисциплины

7.1. Рекомендуемая литература.

а) основная литература:

Шапорев С.Д. Математическая логика. Курс лекций и практических занятий: Учеб. пособие. - СПб: БХВ-Петербург, 2005. – 416 с.
Гуц А.К. Математическая логика и теория алгоритмов: Учеб. пособие. - Омск: Наследие. Диалог-Сибирь, 2003. – 108 с.
Фалевич Б.Я. Теория алгоритмов. М.: Машиностроение, 2004. – 160 с.
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. М.: Энергоатомиздат, 1988. 2-е изд., переработанное и дополненное.
Нефедов В.Н., Осипова В.А. Курс дискретной математики: Учеб. пособие. - М.: Изд-во МАИ, 1992.
Новиков Ф.А. Дискретная математика для программистов. СПб: Питер, 2001.

8. Вопросы для контроля

Определение и виды формальных теорий.
Проблема разрешимости в логике высказываний и методы ее решения.
Язык, системы аксиом и основные правила вывода исчисления высказываний.
Производные правила вывода в исчислении высказываний: выводимость , правило введения импликации, транзитивность выводимости, теорема дедукции, правило силлогизма, правило введения отрицания.
Теорема об общезначимых формулах в исчислении высказываний.
Метод резолюций в исчислении высказываний.
Проблемы аксиоматического исчисления высказываний.
Определение предиката. Область определения, множество истинности предиката. Операции над предикатами, кванторы существования и всеобщности.
Формулы логики предикатов. Свободные и связанные переменные.
Равносильность формул в логике предикатов и в различных интерпретациях. Основные равносильности: перестановка кванторов и переименование связанных переменных.
Правила переноса квантора через отрицание в формулах логики предикатов.
Правила выноса квантора за скобки в формулах логики предикатов.
Нормальные формы логики предикатов. Теорема о предваренной нормальной форме.
Выполнимость и общезначимость для предикатов. Основные общезначимые формулы в логике предикатов.
Теоремы об общезначимости и выполнимости в логике предикатов. Проблема разрешимости в общем случае (теорема Черча) и для формул, содержащих только одноместные предикатные символы.
Язык, система аксиом и основные правила вывода исчисления предикатов.
Производные правила вывода в исчислении предикатов: правила переименования связанных переменных, правило связывания квантором.
Теоремы об общезначимых формулах и о замене эквивалентных подформул в исчислении предикатов.
Наиболее важные эквивалентности исчисления предикатов и их применение для построения предваренной нормальной формы.
Проблемы аксиоматического исчисления предикатов.
Формализация понятия алгоритма.
Понятие рекурсивных функций. Примитивно рекурсивные функции: базовые функции и элементарные операции.
Простейшие примитивно рекурсивные функции. Теорема о примитивной рекурсивности суммы и произведения примитивно рекурсивных функций.
Ограниченный оператор минимизации и его применения. Теорема Робинсона об одноместных примитивно рекурсивных функциях.
Неограниченный оператор минимизации. Частично рекурсивные функции. Тезис Черча о вычислимых функциях.
Общерекурсивные функции. Функция Аккермана. Теорема Аккермана.
Словарные функции. Определение машины Тьюринга.
Способы задания машин Тьюринга. Реализация на машине Тьюринга программы “перенос нуля”. Композиция машин Тьюринга.
Неприменимость машины Тьюринга к исходной информации. Тезис Тьюринга. Теорема о соответствии между частично рекурсивными функциями и функциями, вычислимыми по Тьюрингу.
Определение нормального алгоритма Маркова и порядок его работы.
Пример работы нормального алгоритма Маркова. Тезис Маркова. Теорема об эквивалентности машин Тьюринга и нормальных алгоритмов Маркова.
Сравнительный анализ трех типов алгоритмических моделей. Оценка сложности алгоритма.
Проблема остановки машины Тьюринга и проблема ее самоприменимости. Теорема Райса и ее смысл.
Проблема эквивалентности слов для ассоциативных исчислений и проблема соответствий Поста.
Особенности прикладных исчислений. Теорема об основных свойствах равенства в теории с равенством.
Формальная арифметика. Теоремы Геделя о неполноте и их смысл.

9. Критерии оценок

Превосходно	Превосходная подготовка с очень незначительными погрешностями.
Отлично	Подготовка, уровень которой существенно выше среднего с некоторыми ошибками.
Очень хорошо	В целом хорошая подготовка с рядом заметных ошибок.
Хорошо	Хорошая подготовка, но со значительными ошибками.
Удовлетворительно	Подготовка, удовлетворяющая минимальным требованиям.
Неудовлетворительно	Необходима дополнительная подготовка для успешного прохождения испытания.
Плохо	Подготовка совершенно недостаточная.

10. Примерная тематика курсовых работ и критерии их оценки

Не предусмотрены.
Программа составлена в соответствии с Федеральным государственным образовательным стандартом по специальности 090302 «Информационная безопасность телекоммуникационных систем».

Автор программы: _________________ Павлов И.С.

Программа рассмотрена на заседании кафедры 18 марта 2011 г. протокол № 10-11-04

Заведующий кафедрой _________________ Дубков А.А.

Программа одобрена методической комиссией факультета 11 апреля 2011 года

протокол № 05/10

Председатель методической комиссии_________________ Мануилов В.Н.

Добавить документ в свой блог или на сайт

	Радиофизический факультет Дисциплины 02 «Полупроводниковые лазеры в оптической связи и измерительных системах»		Радиофизический факультет Дисциплины р12 «Взаимодействие электронных потоков с электромагнитными полями»
	Радиофизический факультет Данная дисциплина относится к общепрофессиональным дисциплинам федерального компонента, преподается в 9 семестре		Радиофизический факультет Данная дисциплина относится к дисциплинам специализации федерального компонента, преподается в 6 и 7 семестрах
	Радиофизический факультет ...		Радиофизический факультет Цель курса – сформировать у студентов представления о квантовомеханических закономерностях, лежащих в основе современной физики и...
	Радиофизический факультет Целью преподавания дисциплины «Дискретная математика» является подготовка специалистов к деятельности в сфере разработки, исследования...		Радиофизический факультет Содержание дисциплины направлено на расширение знаний электродинамики плазменных процессов, обусловленных ионизационной нелинейностью...
	Радиофизический факультет Цель изучения дисциплины состоит в освоении студентами методологии и технологии моделирования (в первую очередь компьютерного) информационных...		Радиофизический факультет Содержание дисциплины направлено на углубленное изучение методов физики твердого тела, знакомство с некоторыми современными проблемами...
	Программа по формированию навыков безопасного поведения на дорогах... Факультет русской филологии и журналистики. Факультет истории и юриспруденции. Факультет татарской и сопоставительной филологии....		Радиофизический факультет Дисциплина базируется на знаниях студентов, приобретенных в курсах общей физики, полупроводниковой электроники, электродинамики и...
	Радиофизический факультет Большое внимание в курсе уделено сопутствующему математическому описанию указанных процессов и их использованию для расчета основных...		Радиофизический факультет Дисциплина «Физическая электроника» относится к дисциплинам базовой части профессионального цикла основной образовательной программы...
	Радиофизический факультет Основное внимание при чтении лекций уделяется приближенным методам решения задач распространения и рассеяния скалярных волн в средах...		Радиофизический факультет Содержание дисциплины направлено на изучение разделов аналитической геометрии и высшей алгебры, необходимых для понимания других...

Радиофизический факультет

Похожие: