Стандарт организации (стр. 10 )

3) ((A Ù B)↔ B)↔(B→ A).

4) (A→ B)↔(B→A).

5) ((A→ B)→ A)→ A.

6) A→(A→ B) .

7) (A→ B) Ú (AÙ B).

8) (A→ B)→(B→A).

9) (A→C)→((B→C)→(AÚ B→C)).

10) (A→ B)→((A Ù C)→(B Ù C)).

4. Доказать, что первая формула логически влечет вторую формулу.

1) (AÚ B); (AÙ B).

2) A; B→ A.

3) (A→ B)(B→C); A→C .

4) A→ B; (AÙC)→(B ÙC).

5) A→C ; (B→C)→(AÚ B→C).

6) A; A.

7) A; A→ B.

8) A→ B; (AÚ C)→(B Ú C).

9) A→ B; B→A.

10) A→(B→C); (A→ B)→(A→C).

5. Построить вывод формулы.

1) (A→ B)→((A→(B→C))→(A→C)).

2) (A→ B)→((B→C)→(A→C)) .

3) (A→B)→((B→C)→((C →D)→ (A→ D))) .

4) A→(A→ B) .

5) A→ A.

6) A→A.

7) (A→B)→(A→ B).

8) ( A→ B)→(A→ B).

9) (A→B)→(B→A).

10) A→(B→(A→ B)) .

11) (A→ B)→((B→ A)→ B).

12) ((A→B)→ A)→ A.

6. Записать инверсию формулы в предваренной нормальной форме.

1) $xA(x).

2) $x(A(x)B(x)).

3) "xA(x) .

4) "x(A(x)→ "yB( y)).

5) $x(A(x)B(x)C(x)).

6) "x(A(x)→ B(x)).

7) $x(A(x)↔ B(x)).

8) "x(A(x) Ú $yB( y)).

9) "x(A(x)→ B(x))Ù $x(C(x) ÙD(x)).

10) "x$y"z(A(x, y, z)→ B(x, y, z)).

А.3 Отчет по лабораторной работе

Согласно СТП 12 700 2007 отчёт должен быть оформлен на сброшюрованных листах формата А4 (210´297 мм), отчёт составляется каждым студентом индивидуально. ;

Отчёт должен включать следующие структурные элементы:

а) титульный лист, оформленный в соответствии с СТП 12 570-2006;

б) цель работы, в том числе задание на лабораторную работу;

в) основную часть.

А.4 Сроки сдачи лабораторных работа

Лабораторная работа №1 – 2 неделя, №2 – 4 неделя, №3 – 8 неделя, №4 – 10 неделя, № 5 – 14 неделя, № 6 – 17 неделя.

А.5 Учебно-методическое и информационное обеспечение

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

1  Игошин, логика и теория алгоритмов: учеб. пособие /.-М.: Академия, 2008. – 448 с. - 25 экз.

2  Крючкова, логика и теория алгоритмов: учебное пособие / . – Барна0. - Режим доступа: http//elib. alstu. ru, свободный

3  Судоплатов, логика и теория алгоритмов: учебник /, .-Новосибирск: НГТУ, 2010.- 255 с. - 2 экз.

Дополнительная литература

4  Соболева, математика: [учеб. для вузов по специальностям "Информатика и вычисл. техника", "Информ. системы", "Информ. безопасность"] /, ; под ред. .-М.: Академия, 2006. - 254 с. – 11 экз.

5  Лавров, логика : [учеб. пособие для вузов по техн. и естеств.-науч. специальностям] / ; под ред. . - М. : Академия, 2006. – 239 с. – 11 экз.

6  Успенский курс математической логики: [учеб. пособие] /, , .-М.: ФИЗМАТЛИТ, 2с. – 3 экз.

7  Мендельсон Эллиот. Введение в математическую логику: переводное издание /Э. Мендельсон; пер. с англ. .-М.: Наука, 1984. - 319 с. – 14 экз.

Рекомендуемые сайты:

1. www. intuit. ru

2. www. window. edu. ru

5. Электронная библиотека: http//elib. alstu. ru/

ПРИЛОЖЕНИЕ Б

МЕТОДические указания по выполнению РАСЧЕТНОГО ЗАДАНИЯ

По ДИСЦИПЛИНЕ "МАТЕМАТИЧЕСКАЯ ЛОГИКА И

ТЕОРИЯ АЛГОРИТМОВ "

Б.1 Общие сведения о расчетном задании

Б.1.1 Цель выполнения расчетного задания

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

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

Б.1.2 Организация выполнения расчетного задания

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

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

Процесс сдачи расчетного задания включает в себя:

- доказательство NP-полноты;

- демонстрацию программного продукта;

- предоставление расчета временной сложности;

- представление отчета о выполнении раcчетного задания;

- устную защиту.

По результатам выполнения расчетного задания студент должен сдать:

- отчет на бумажном носителе;

- электронную копию отчета;

- программный продукт в электронном варианте.

Процесс выполнения расчетного задания рекомендуется разделить на следующие этапы:

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

2) доказательство NP-полноты задачи;

3) разработка алгоритма решения задачи;

4) написание программы, ее тестирование и отладка;

5) оценка временной сложности программы;

6) оформление отчета;

7) сдача работы и защита работы.

Отчет рекомендуется оформлять параллельно с текущим этапом работы.

Б.1.3 Разработка программного продукта

Требования, предъявляемые к программному продукту:

- программа должна быть работоспособной;

- программа должна полностью правильно решать поставленную задачу.

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

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

Б.2 Темы расчетных заданий

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

Общие требования к теме расчетного задания:

- задача должна относиться к классу NP-полных задач;

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

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

- при выполнении расчетного задания студент должен продемонстрировать основные знания, умения и навыки, полученные при изучении данной дисциплины

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

Цель расчетного задания: приобрести практический опыт доказательства NP-полноты, разработки эффективного алгоритма, расчета временной сложности, закрепить на практике знания и навыки, полученные в ходе изучения дисциплины «Математическая логика и теория алгоритмов».

Примеры вариантов расчетных заданий:

1.  Имеется битовая плоскость размера MxM, на которой нарисован рисунок. Хватит ли N прямоугольников, чтобы закрыть ими рисунок?

2.  Фирма торгует мебелью N типов, для каждого типа известны цена и занимаемая ею площадь. Можно ли выбрать по одному наименованию мебели каждого типа так, чтобы она разместилась на заданной площади и ее цена была больше, чем известное число S?

3.  Администрация школы решила подарить каждому первокласснику по набору, включающему открытку, пенал, ручку и набор фломастеров. На каждого ребенка запланировано потратить не более N рублей. Однако требуется, чтобы у разных детей подарки в наборах не повторялись. Имеется прайс фирмы, торгующей канцтоварами. Удастся ли в фирме приобрести подарки для M первоклассников?

4.  Группа студентов сдает экзамен. В билете 2 вопроса и задача. Экзамен принимают два преподавателя, один принимает теорию, второй – задачу, порядок сдачи вопросов билета изменять нельзя. Время, нужное для сдачи каждым студентом первого, второго вопроса и задачи известно. Успеют ли преподаватели принять экзамен в течение N часов? Предложить порядок сдачи экзамена, чтобы время сдачи было минимально.

Б.3 Оформление отчета по расчетному заданию

Отчет по расчетному заданию должен включать:

- титульный лист;

- содержание;

- введение;

- постановку задачи;

- доказательство NP-полноты;

- описание алгоритма решения задачи;

- тест программы;

- результаты тестирования программы;

- расчет временной сложности;

- заключение;

- список использованных источников;

Оформление отчета должно быть осуществлено в соответствии с СТП АлтГТУ 12 570 и СТО 12 400 2009.

Б.4 Общие рекомендации

Изучите методические указания к выполнению расчетного задания.

Ответственно отнеситесь к выбору темы: если у Вас есть какие-то предпочтения по теме, то обсудите их с преподавателем.

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

Документируйте результаты отдельных видов работ по ходу их выполнения: в этом случае к окончанию работы текст отчета будет практически готов, текст программы – корректно оформлен и комментирован. После получения работоспособного программного продукта приступите к итоговому оформлению отчета.

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

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

Стремитесь к соблюдению графика работы, не затягивайте выполнение этапов.

Б.5 Примерный перечень информационных источников

Студенту могут быть полезны следующие информационные ресурсы:

1  ычислительные машины и труднорешаемые задачи. – М.: Мир, 1982. – 416 с.

2  Игошин, логика и теория алгоритмов: учеб. пособие /. - М.: Академия, 2008. – 448 с.

3  Крючкова, логика и теория алгоритмов: учебное пособие / . – Барна0. - Режим доступа: http//elib. alstu. ru, свободный

4  Судоплатов, логика и теория алгоритмов: учебник /, .-Новосибирск: НГТУ, 2010.- 255 с.

5  Соболева, математика: [учеб. для вузов по специальностям "Информатика и вычисл. техника", "Информ. системы", "Информ. безопасность"] /, ; под ред. .-М.: Академия, 2006. - 254 с.

Рекомендуемые сайты:

1. www. intuit. ru

2. www. window. edu. ru