Математическая логика и теория алгоритмов (стр. 2 )

№	Тема	Содержание СРС	Источники	Форма Выполнения СРС	Ко-лич час.
1.	Высказывания. Истинностные таблицы.	Высказывания. Операции над высказываниями. Истинностные значения и истинностные таблицы. Равносильность формул. Истинностные функции.	1. , Математическая логика. - М.: Наука, 2007. 320с. (24-35)	Письменное практическое задание	12
2.	Совершенные нормальные формы истинностных функции.	Совершенные нормальные формы истинностных функции. СДНФ и СКНФ. Полные системы истинностных функций.	1. ведение в математическую логику. - М.: Наука, 2010. 320с. (5-10) 2. Лихтарников, логика: курс лекций: задачник-практикум и решения: учеб. пособие. – 4-е изд., стер. – СПб.:Лань, 2009. – 276 с. (12-36)	Письменное практическое задание, Тестирование	12
3.	Виды формул алгебры высказываний.	Виды формул алгебры высказываний, их классификация. Свойства общезначимых формул. Методы установления общезначимости формул. Равносильные преобразования формул.	1. Ершов, логика: учеб. пособие / , . – 4-е изд., стер. – СПб.: Лань, 2006. – 336 с. (8-21) 2. ведение в математическую логику. - М.: Наука, 2010. 320с. (12-42)	Контрольная работа	12
4.	Исчисление высказываний.	Исчисление высказываний. Система аксиом. Теорема дедукции. Полнота исчисления высказываний.	1. ведение в математическую логику. - М.: Наука, 2010. 320с. (31-46) 2. , Задачи по теории множеств, математической логике и теории алгоритмов. - М.: Наука, 2006. - 224с. (27-48)	Письменное практическое задание, Тестирование	10
5.	Теории первого порядка. Предваренные нормальные формы.	Теории первого порядка.	1. Ершов, логика: учеб. пособие / , . – 4-е изд., стер. – СПб.: Лань, 2006. – 336 с. (24-52)	10
Интерпретации. Выполнимость и истинность. Модели. Предваренные нормальные формы. Нормальная форма Сколема.	Письменное тестирование	10
6.	Математическое определение алгоритма. Вычислимые функции.	Математическое определение алгоритма. Понятие алфавитного оператора. Вычислимые функции. Разрешимые и перечислимые множества. Пересечение и объединение перечислимых множеств.	1. Игошин, логика и теория алгоритмов: учеб. пособие для студ. вузов / . – 2-е изд., стер. – М.: Академия, 2008. – 446 с. (24-46) 2. Алгоритмы и рекурсивные функции. - М.: Наука, 2006. 367с. (18-43)	Графическая работа. Письменное практическое задание.	12
7.	Рекурсивные функции.	Рекурсивные функции. Примитивно рекурсивные функции. Операторы суперпозиции и примитивной рекурсии. Частично рекурсивные и общерекурсивные функции. Оператор минимизации и ограниченный оператор минимизации.	1. Игошин, логика и теория алгоритмов: учеб. пособие для студ. вузов / . – 2-е изд., стер. – М.: Академия, 2008. – 446 с. (45-66) 2. Алгоритмы и рекурсивные функции. - М.: Наука, 2006. 367с. (44-57)	Контрольная работа	12
8.	Машина Тьюринга.	Машина Тьюринга. Задание машины Тьюринга. Принцип машины Тьюринга. Представление машины Тьюринга графом. Вычислимые по Тьюрингу функции. Операции над машинами Тьюринга.	1. Алгоритмы и рекурсивные функции. - М.: Наука, 2006. 367с. (34-57) 2. , Задачи по теории множеств, математической логике и теории алгоритмов. - М.: Наука, 2006. - 224с. (42-65)	Письменное практическое задание	12
9.	Нормальные алгоритмы Маркова.	Нормальные алгоритмы Маркова. Функции вычислимые по Маркову. Замыкание, распространение нормального алгоритма. Операции над нормальными алгоритмами.	1. , Задачи по теории множеств, математической логике и теории алгоритмов. - М.: Наука, 2006. - 224с. (24-62)	Контрольное тестирование	12
Итого	48

4.Фонд оценочных средств

4.1. Перечень компетенций программы:

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

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

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

знать:

?  место математической логики, теории алгоритмов в системе современного научного знания и ее значение как науки,

? основные исторические сведения и главные направления развития математической логики, теории алгоритмов,

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

уметь:

? решать типовые задачи в указанной предметной области;

?  работать самостоятельно с учебной и дополнительной литературой;

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

владеть:

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

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

?  логической символикой, основами теории логического вывода.

4.2. Описание показателей и критериев оценивания компетенций:

Итоговой формой контроля знаний, умений и навыков по дисциплине является экзамен, который оценивается оценками – «отлично», «хорошо», «удовлетворительно», «неудовлетворительно». Эти оценки проставляются в аттестационную ведомость.

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

При выставлении оценки могут быть применены рекомендательные критерии:

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

Оценка «хорошо» выставляется студенту, если он  усвоил программный материал;  логично его излагает, умеет увязывать теорию с практикой, но не в достаточной мере справляется с задачами, вопросами и другими видами применения знаний.

Оценка «удовлетворительно» выставляется студенту, если он слабо усвоил программный материал; с трудом излагает его содержимое, постоянно сбивается, не справляется в должной степени с задачами, вопросами и другими видами применения знаний.

Оценка «неудовлетворительно» выставляется студенту, который не знает значительной части программного материала, допускает существенные ошибки, с большим затруднениями выполняет практические работы. Как правило, оценка «неудовлетворительно» ставится студентам, которые не могут продолжить обучение без дополнительных занятий по дисциплине.

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

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

4.3 Типовые контрольные задания

Контрольная работа по математической логике 

№1. Исходя из данных условий, определите истинностные значения высказываний P, Q,R, S,T. Найдите самое короткое решение.

0	P?Q=1	Q?R=0	R?S=0	S?T=1
1	P?Q=1	Q?R=0	R?S=0	S?T=0
2	P?Q=0	Q?R=0	R?S=1	S?T=1
3	P?Q=1	Q?R=1	R?S=1	S?T=0
4	P?Q=1	Q?R=0	R?S=0	S?T=1
5	P?Q=0	Q?R=0	R?S=1	S?T=0
6	P?Q=1	Q?R=1	R?S=1	S?T=1
7	P?Q=1	Q?R=0	R?S=0	S?T=0
8	P?Q=0	Q?R=0	R?S=1	S?T=1
9	P?Q=1	Q?R=1	R?S=1	S?T=0
10	P?Q=1	Q?R=0	R?S=0	S?T=1

Решение варианта 0. По определению импликации из R?S?0 следует R?1 и S?0. По определению отрицания ?S?1. По определению эквивалентности из ?S?T?0 и ?S?1 следует T?0. По определению конъюнкции из Q?R?0 и R?1 следует Q?0. По определению дизъюнкции из P?Q?1 и Q?0 следует P?1. Ответ: (P, Q,R, S,T)?(1,0,1,0,0).