Рекомендации методические по выполнению самостоятельной работы студентов специальностей 080801 «Прикладная информатика в экономике», 230201 «Информационные системы и технологии» Бийск Федеральное агентство по образованию ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Бийский технологический институт (филиал) государственного образовательного учреждения высшего профессионального образования «Алтайский государственный технический университет им. И.И. Ползунова» Т.М. Тушкина, В.С. Фролов, О.Д. Ростова, Л.П. Кувшинова МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ Методические рекомендации по выполнению самостоятельной работы студентов специальностей 080801 «Прикладная информатика в экономике», 230201 «Информационные системы и технологии» Бийск Издательство Алтайского государственного технического университета им. И.И. Ползунова 2010 УДК 519.1 Рецензент: к.т.н., доцент кафедры МСИиА БТИ АлтГТУ Гареева Р.Г. Тушкина, Т.М. Математическая логика и теория алгоритмов: методические реко- мендации по выполнению самостоятельной работы студентов спе- циальностей 080801 «Прикладная информатика в экономике», 230201 «Информационные системы и технологии» / Т.М. Тушкина, В.С. Фролов, О.Д. Ростова, Л.П. Кувшинова; Алт. гос. техн. ун-т, БТИ. – Бийск: Изд-во Алт. гос. техн. ун-та, 2010. – 16 с. Данная методическая разработка является составной частью учебно-методического комплекса по дисциплине «Математическая логика и теория алгоритмов» для студентов специальностей 080801 «Прикладная информатика в экономике», 230201 «Информационные системы и технологии». В методических рекомендациях представлены план-график выполнения самостоятельной работы студентов (СРС), ее содержание, примерные нормы на выполнение внеаудиторной СРС по каждому заданию, требования к представлению и оформлению результатов и критерии оценки выполнения СРС по дисциплине «Математическая логика и теория алгоритмов». УДК 519.1 Рассмотрены и одобрены на заседании кафедры высшей математики и математической физики. Протокол № 3 от 03.07.2009 г. © Т.М. Тушкина, В.С. Фролов, О.Д. Ростова, Л.П. Кувшинова, 2010 © БТИ АлтГТУ, 2010 СОДЕРЖАНИЕ 1 ЦЕЛИ И ЗАДАЧИ КУРСА «МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ» 4 2 СОДЕРЖАНИЕ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ.. 5 3 ПЛАН-ГРАФИК ВЫПОЛНЕНИЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТАМИ ПО ДИСЦИПЛИНЕ 6 4 ХАРАКТЕРИСТИКА И ОПИСАНИЕ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ 7 5 ТРЕБОВАНИЯ К ПРЕДСТАВЛЕНИЮ И ОФОРМЛЕНИЮ РЕЗУЛЬТАТОВ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ.. 10 6 ФОРМЫ И МЕТОДЫ КОНТРОЛЯ ЗНАНИЙ СТУДЕНТОВ.. 10 РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА.. 14 1 ЦЕЛИ И ЗАДАЧИ КУРСА «МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ» В современной науке и технике математические методы исследования и проектирования играют все более возрастающую роль. Это обусловлено в первую очередь быстрым ростом возможностей вычислительной техники. Благодаря широкому внедрению вычислительной техники во все сферы научно-технической деятельности существенно расширяются возможности широкого применения математики при решении задач планирования и управления, проектирования технологических систем, логических устройств. Основной целью изучения дисциплины является овладение студентами аппаратом математической логики и теории алгоритмов для решения задач анализа информации, в том числе изучение способов формального представления информации (высказываний), построения новых высказываний из имеющихся с помощью логически выдержанных преобразований, а также способов (методов) установления истинности или ложности высказываний. Будущие специалисты в области информационных технологий должны иметь представления о формальных системах, владеть методами формализованного представления информации. В данном случае речь идет о методах, основанных на логических представлениях. В этой связи, будут рассмотрены следующие разделы изучаемой дисциплины: логика высказываний (модуль 1), логика предикатов (модуль 2), теория алгоритмов (модуль 3). Изучение дисциплины «Математическая логика и теория алгоритмов» студентами данных специальностей осуществляется во втором семестре. В результате изучения курса «Математическая логика и теория алгоритмов» обучающиеся должны: · иметь представление о месте и роли математической логики в системе математических наук и возможности ее применения в экономических и естественных науках; · владеть понятиями математической логики и теории алгоритмов; · знать и уметь использовать методы математической логики и теории алгоритмов при решении задач анализа информации. Для изучения дисциплины «Математическая логика и теория алгоритмов» студентам пригодятся знания по элементарной математике. Курс математической логики и теории алгоритмов является базовым при изучении таких дисциплин, как «Вычислительная математика», «Теория информационных процессов и систем», «Управление данными», «Моделирование систем», «Основы теории управления», «Алгоритмы и методы переработки информации», «Методы оптимального управления», «Информационный менеджмент», «Моделирование информационных процессов», «Проектирование информационных систем» и др. 2 СОДЕРЖАНИЕ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ На самостоятельную работу студентам специальности «Прикладная информатика в экономике» (ПИЭ) отводится 51 час, а студентам специальности «Информационные системы и технологии» (ИСТ) – 40 часов. В связи с тем, что объем часов достаточно большой, ряд вопросов студенты изучают самостоятельно по рекомендованной литературе. Для студентов, желающих иметь высокий текущий рейтинг, выдается индивидуальное дополнительное задание – задача повышенной степени сложности. Перечень таких задач находится у преподавателя. Отчитаться в выполнении дополнительного задания необходимо до наступления сессии. Виды самостоятельной работы, предусмотренные рабочей программой по дисциплине «Математическая логика и теория алгоритмов», представлены в таблице 1. Таблица 1 – Виды самостоятельной работы Наименование работы Объем, ч ПИЭ ИСТ 1 Подготовка к практическим занятиям 14 12 2 Подготовка к контрольным работам и контрольным опросам 7 6 3 Выполнение индивидуальных домашних заданий и подготовка к защите решения 10 7 4 Выполнение индивидуального дополнительного задания повышенной сложности* 10 5 4 Подготовка к зачету 10 10 Итого 51 40 * Задание выполняется по желанию студента с целью повышения аттестационного балла по дисциплине Различные виды самостоятельной работы предполагают: · изучение лекционного материала и рекомендованной литературы; · выполнение практических заданий, в том числе индивидуальных расчетных и дополнительных заданий; · подготовку ответов на вопросы, вынесенные на самостоятельное изучение. При самостоятельной работе студентам необходимо: · обратить внимание на новые понятия и термины, встретившиеся при изучении дисциплины, и при необходимости составить глоссарий (словарь терминов) по каждому модулю дисциплины; · отработать схемы решения типовых задач дисциплины. Для этого необходимо подробно разобрать схему или алгоритм решения основных классов задач; уметь привести примеры ситуаций, в которых схема решения или алгоритм могут быть использованы; уметь на примере показать действие схемы решения или алгоритма; · в процессе решения задач, тестов и т.п. связывать полученные знания с реальной действительностью. 3 ПЛАН-ГРАФИК ВЫПОЛНЕНИЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТАМИ ПО ДИСЦИПЛИНЕ Для рациональной организации самостоятельной работы студентам предлагается в течение семестра придерживаться плана-графика, представленного в таблице 2. Таблица 2 – План-график выполнения самостоятельной работы Вид самостоя-тельной работы Номер недели семестра 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ППЗ 1 1,5 2 2/1,5 2/1,5 2/1,5 1,5 2/1,5 ИДЗ 2/1 2/1,5 2/1,5 2/1,5 2/1,5 ПК 4/3 3/3 ДЗ 2/1 2/1 2/1 2/1 2/1 З 10 Итого в не-делю 1 3,5/ 2,5 4/3,5 8/6 4/3 4/2,5 2/1 5,5/4 2/1 7/5,5 10 В таблице 2: ППЗ – подготовка к практическим занятиям (изучение конспектов лекций и рекомендуемой литературы, решение задач); РЗ – выполнение расчетных заданий и подготовка к защите типового расчета; ДЗ – выполнение дополнительного задания повышенной сложности; ПК – подготовка к контрольной работе или контрольному опросу; З - подготовка к зачету. 4 ХАРАКТЕРИСТИКА И ОПИСАНИЕ САМОСТОЯТЕЛЬНОЙ РАБОТЫ С ТУДЕНТОВ Темы практических занятий по дисциплине «Математическая логика и теория алгоритмов» представлены в методических рекомендациях по проведению практических занятий. Учебным планом по дисциплине «Математическая логика и теория алгоритмов» на практические занятия отводится 17 часов учебной работы. Примерные нормы времени на подготовку к практическим занятиям в зависимости от вида деятельности приведены в таблице 3. Таблица 3 – Примерные нормы времени на подготовку к практическим занятиям Номер занятия Вид деятельности при подготовке к одному практическому занятию Изучение лекционного материала и рекомендуемой литературы, ч, ПИЭ/ИСТ Решение задач к практическому занятию, ч, ПИЭ/ИСТ 1 1/1 - 2 1/1 0,5/0,5 3 1/1 1/1 4 1/1 1/0,5 5 1/1 1/0,5 6 1/1 1/0,5 7 1/1 0,5/0,5 8 1/1 1/0,5 Одним из видов самостоятельной работы студентов является выполнение индивидуальных домашних заданий. Таковых заданий будет пять. Ниже описывается их тематика. Первое задание представляет собой задачу, в которой нужно найти таблицы истинности двух формул, одна из которых включает две переменные, а вторая – три. Для решения задачи студентам необходимо знать определения основных логических операций (отрицание, дизъюнкция, конъюнкция, импликация, эквиваленция, сложение по модулю 2), а также иметь представление о старшинстве логических операций. Второе задание – задача по теме «Равносильные преобразования формул алгебры логики». Для решения данной задачи студенту необходимо знать основные равносильности алгебры логики для дизъюнкции и конъюнкции, а также равносильности, позволяющие одни логические связки выражать через другие. Для установления равносильности формул следует воспользоваться известным критерием. Третье задание – задача по теме «Минимизация в классе дизъюнктивных (конъюнктивных) нормальных форм». Задачу можно решить любым известным методом, например, методом минимизирующих карт или методом Блейка-Порецкого. Четвертое задание – задача по теме «Полные системы булевых функций». Для ее решения необходимо изучить теорему Поста о функциональной полноте, определения монотонных, самодвойственнх, линейных логических функций, а также логических функций, сохраняющих 0 и 1. Пятое задание – задача по теме «Предикаты». Предикат от двух переменных задан на конечном множестве. Требуется построить таблицу истинности предиката, найти область его истинности, квантифицировать переменные всеми возможными способами и определить истинностный смысл полученных высказываний. Защита индивидуальных заданий происходит в форме письменной самостоятельной работы, включающей теоретические вопросы и задачи по указанным выше темам. Примерные нормы времени на выполнение индивидуальных домашних заданий в зависимости от их трудоемкости приведены в таблице 4. В ходе изучения дисциплины «Математическая логика и теория алгоритмов» студенты выполняют два теста текущего контроля знаний ( и контрольный опрос). В состав контрольной работы входят задачи по приведенным ниже темам: 1) таблица истинности логической связки; 2) равносильность формул алгебры логики; 3) тождественно истинные и тождественно ложные формулы; 4) таблица истинности логической формулы, соответствующей сложному высказыванию; 5) схема логически правильного рассуждения; 6) теорема о функциональной полноте; 7) алгоритм приведения формулы, не являющейся тождественной истинной (ложной) к СДНФ (СКНФ). Таблица 4 – Примерные нормы времени для выполнения расчетных заданий Номер расчетного задания Виды деятельности Решение задания типового расчета, ч Подготовка к защите задания типового расчета, ч 1 1/0,5 1/0,5 2 1/1 1/0,5 3 1/1 1/0,5 4 1/1 1/0,5 5 1/1 1/0,5 При проведении контрольного опроса студентам будут предложены задания по темам: 1) машины Тьюринга; 2) геделева нумерация; 3) кодирование натуральных чисел в алфавите {|}; 4) вычисление значений числовых функций с помощью машин Тьюринга; 5) применение машины Тьюринга к заданной начальной конфигурации. В процессе подготовки к контрольной работе и контрольному опросу студенту нужно повторить теоретический материал и дополнительно решить задачи (контрольные задания из конспекта лекций по дисциплине) по всем объявленным выше темам. Итоговая аттестация знаний студентов по дисциплине «Математическая логика и теория алгоритмов» в форме зачета происходит на последнем занятии по билетам. Билет содержит четыре вопроса: – теоретический вопрос по темам модуля 1; – теоретический вопрос по темам модулей 2, 3; – задача 1 – по одной из тем модуля 1; – задача 2 – по одной из тем модулей 2, 3. При подготовке к итоговой аттестации следует выучить и дать ответы на вопросы к зачету. Дополнительно нужно повторить ответы на контрольные вопросы и решения контрольных заданий, приведенных в конспекте лекций по дисциплине «Математическая логика и теория алгоритмов». 5 ТРЕБОВАНИЯ К ПРЕДСТАВЛЕНИЮ И ОФОРМЛЕНИЮ РЕЗУЛЬТАТОВ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ При выполнении и оформлении индивидуальных домашних заданий и заданий повышенной степени сложности необходимо соблюдать следующие правила. 5.1 Работу следует выполнять в отдельной тетради, на внешней обложке которой должны быть указаны фамилия и инициалы студента, название учебного заведения, номер группы, номер варианта. 5.2 Задания выполняются чернилами, с полями 3…4 см для замечаний преподавателя. 5.3 Решения задач располагаются в порядке номеров, указанных в заданиях. Перед решением задачи обязательно должно быть записано ее условие. 5.4 Решения задач и пояснения к ним должны быть подробными. При решении следует делать соответствующие ссылки на вопросы теории с указанием формул, теорем, выводов, которые используются. 5.5 Решение каждой задачи необходимо заканчивать записью ответа. 6 ФОРМЫ И МЕТОДЫ КОНТРОЛЯ ЗНАНИЙ СТУДЕНТОВ 6.1 Формы контроля знаний Текущий контроль знаний состоит из следующих мероприятий: · проверки решения заданий, предусмотренных для работы во внеаудиторное время (домашние работы), наличие домашней работы фиксируется в журнале преподавателя; · проверки решения индивидуальных домашних заданий и письменной самостоятельной работы по защите их решения; · двух тестов текущего контроля знаний: аудиторной контрольной работы по модулю 1 и письменного контрольного опроса по модулю 3 в сроки согласно графику изучения дисциплины. Итоговый контроль знаний осуществляется во время зачета на последнем практическом занятии. 6.2 Рейтинговая система оценки индивидуальной учебной деятельности студентов В АлтГТУ принята 100-балльная шкала оценок. Именно эти оценки учитываются при подсчете рейтингов, назначении стипендии и в других случаях. Традиционная шкала будет использоваться только в зачетных книжках. В таблице 5 представлено соответствие рейтинговой и традиционной оценок. Таблица 5 – Соответствие между рейтинговой и традиционной оценками Рейтинговый балл 0–24 25–49 50–74 75-100 Традиционная оценка Неудовлетво-рительно Удовлетво-рительно Хорошо Отлично Успеваемость студента оценивается с помощью текущего рейтинга (во время каждой аттестации) и итогового рейтинга (после сессии). Во всех случаях рейтинг вычисляется по формуле: где Ri – оценка за i -ю контрольную точку; pi – вес этой контрольной точки. Суммирование проводится по всем контрольным точкам с начала семестра до момента вычисления рейтинга. График контроля представлен в таблице 6. Таблица 6 – График контроля Модуль Контрольное испытание Время проведения (номер недели) Вес в итоговом рейтинге Примечания 1 2 3 4 5 1 Выполнение и защита индивидуального домашнего задания по теме 1 3 0,02 Одна задача Продолжение таблицы 6 1 2 3 4 5 Выполнение и защита индивидуального домашнего задания по теме 2 5 0,06 Три задачи Контрольная работа по темам 1–2 7 0,15 Семь задач 2 Выполнение и защита индивидуального домашнего задания по теме 3 13 0,02 Одна задача 3 Контрольный опрос по теме 4 15 0,15 Шесть вопросов 4 Защита решения заданий повышенного уровня сложности по темам 1–4 17 0,1 Зачет (по темам 1–4) 17 0,5 Четыре вопроса по 25 баллов При выставлении оценок за отдельные контрольные испытания, а также при определении текущего и итогового рейтингов преподаватель руководствуется следующими правилами. · Контрольная работа оценивается, исходя из следующих соображений: за одно задание студент может получить максимальный балл в том случае, когда реализована верная схема решения задачи, не допущено вычислительных ошибок, в результате получен правильный ответ. Если задача решена с недочетами или ошибками, то оценка снижается на балл, пропорциональный их количеству. Оценка за контрольную работу складывается из суммы баллов, полученных за отдельные задания. · За решение индивидуального задания студент получит 80 баллов, если это задание выполнено без ошибок, оформлено в соответствии с требованиями, указанными в разделе 5 настоящей методической разработки, защищено в срок. Дополнительные 20 баллов за выполнение одного задания студент может получить тогда, когда при решении был использован оригинальный подход или ЭВМ. · Любая контрольная точка, выполненная после срока без уважительной причины, оценивается на 10 % ниже. Максимальная оценка в этом случае 90 баллов. · К зачету допускаются студенты, не имеющие задолженностей по контрольным точкам. · Зачет проводится в письменной форме. Так же, как и в случае с контрольной работой, оценка на зачете складывается из баллов, полученных за отдельные вопросы (теоретические вопросы и задачи), включенные в билет. При этом считается, что теоретический вопрос на зачете освещен без недочетов, если определены и проиллюстрированы примерами основные понятия, включенные в этот вопрос; сформулированы и доказаны необходимые теоремы (свойства); сформулированы и проиллюстрированы на примерах алгоритмы и схемы решения задач. · «Автоматы» по дисциплине «Математическая логика и теория алгоритмов» не выставляются. Приведем пример определения текущего, семестрового и итогового рейтинга студента. Допустим, что студент получил следующие оценки: защита индивидуальных домашних заданий по темам 1, 2 – 40 баллов; по темам 1, 2 – 60 баллов, защита индивидуального задания по теме – 70 баллов; контрольный опрос по теме 4 – 70 баллов; дополнительное задание повышенной сложности не решено, т.е. 0 баллов; ответ на зачете – 60 баллов. На первой аттестации (седьмая неделя) его рейтинг равен: . На второй аттестации (13 неделя): . Перед зачетом вычисляется семестровый рейтинг: . Итоговый рейтинг, учитывающий зачет, вычисляется по формуле . В данном случае . В зачетку выставляется оценка «зачет». РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА Основная литература 1. Хаггарти, Р. Дискретная математика для программистов / Р. Хаг-гарти. – М.: Техносфера, 2005. 2. Новиков, Ф.А. Дискретная математика для программистов / Ф.А. Новиков. – СПб.: Питер, 2001. 3. Нефедов, В.Н. Курс дискретной математики: учеб. пособие / В.Н. Нефедов, В.А. Осипова. – М.: Изд-во МАИ, 1992. 4. Яблонский, С.В. Введение в дискретную математику: учебное пособие для вузов / С.В. Яблонский; под ред. В.А. Садовничего. – 3-е изд., стер. – М.: Высшая школа, 2002. 5. Лавров, И.А. Задачи по теории множеств, математической логике и теории алгоритмов / И.А. Лавров, Л.Л. Максимова. – Изд. 4-е. – М.: ФИЗМАТЛИТ, 2001. 6. Москинова, Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях: учеб. пособие / Г.И. Москинова. – М.: Логос, 2000. Дополнительная литература 7. Судоплатов, С.В. Дискретная математика: учебное пособие / С.В. Судоплатов, Е.В. Овчинникова. – М.: Инфра-М, 2007. 8. Романовский, И.В. Дискретный анализ / И.В. Романовский. – СПб.: Невский диалект, 2000. Перечень пособий, методических указаний и материалов, используемых в учебном процессе 9. Ростова, О.Д. Дискретная математика: методические рекомендации к типовому расчету по математике с вариантами заданий для студентов специальностей 071900, 351400, 170600, 171200 / О.Д. Ростова, Т.М. Тушкина, В.С. Фролов; Алт. гос. техн. ун-т, БТИ. – Бийск: Изд-во Алт. гос. техн. ун-та, 2005. 10. Тушкина, Т.М. Математическая логика и теория алгоритмов: методические рекомендации по проведению практических занятий для студентов специальностей 080801 «Прикладная информатика в экономике», 230201 «Информационные системы и технологии» / Т.М. Тушкина, В.С. Фролов, О.Д. Ростова, Л.П. Кувшинова; Алт. гос. техн. ун-т, БТИ. – Бийск: Изд-во Алт. гос. техн. ун-та, 2010. 11. Тушкина, Т.М. Математическая логика и теория алгоритмов: методические рекомендации по изучению дисциплины для студентов специальностей 080801 «Прикладная информатика в экономике», 230201 «Информационные системы и технологии» / Т.М. Тушкина, В.С. Фролов, О.Д. Ростова, Л.П. Кувшинова; Алт. гос. техн. ун-т, БТИ. - Бийск: Изд-во Алт. гос. техн. ун-та, 2010. Учебное издание ТУШКИНА Татьяна Михайловна ФРОЛОВ Виктор Савельевич РОСТОВА Ольга Дмитриевна КУВШИНОВА Лидия Павловна МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ Методические рекомендации по выполнению самостоятельной работы студентов специальностей 080801 «Прикладная информатика в экономике», 230201 «Информационные системы и технологии» Редактор Идт Л.И. Технический редактор Сазонова В.П. Подписано в печать 26.02.2010. Формат 60´84 1/16 Усл. п. л. - 0,93. Уч.-изд. л. - 1,00 Печать - ризография, множительно-копировальный аппарат «RISO EZ300» Тираж 50 экз. Заказ 2010-33 Издательство Алтайского государственного технического университета 656038, г. Барнаул, пр-т Ленина, 46 Оригинал-макет подготовлен ИИО БТИ АлтГТУ Отпечатано в ИИО БТИ АлтГТУ 659305, г. Бийск, ул. Трофимова, 27