Скачать 200.79 Kb.
|
РОССИЙСКАЯ ФЕДЕРАЦИЯМИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИГосударственное образовательное учреждение высшего профессионального образования ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Институт математики, естественных наук и информационных технологийКафедра алгебры и математической логикиДёгтев А.Н. Теория автоматов Учебно-методический комплекс. Рабочая программа для студентов очной формы обучения НАПРАВЛЕНИЕ 010200.62 «МАТЕМАТИКА И КОМПЬЮТЕРНЫЕ НАУКИ», профиль подготовки: «Алгебра и дискретная математика». Тюменский государственный университет 2011 Дёгтев А.Н.Теория автоматов. Учебно-методический комплекс. Рабочая программа для студентов направления 010200.62 – МАТЕМАТИКА И КОМПЬЮТЕРНЫЕ НАУКИ, профиль подготовки: «Алгебра и дискретная математика», форма ОБУЧЕНИЯ – ОЧНАЯ. Тюмень, 2011, 11 стр. Рабочая программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ПрООП ВПО по направлению и профилю подготовки. Рабочая программа дисциплины опубликована на сайте ТюмГУ: «Теория автоматов» [электронный ресурс] / Режим доступа: http://www.umk3.utmn.ru., свободный. Рекомендовано к изданию кафедрой алгебры и математической логики. Утверждено проректором по учебной работе Тюменского государственного университета. ОТВЕТСТВЕННЫЙ РЕДАКТОР: заведующий кафедрой алгебры и математической логики доктор физико-математических наук, профессорКутрунов В.Н.© Тюменский государственный университет, 2011. © Дёгтев А.Н.., 2011.
1.1. Цели и задачи дисциплины. Дисциплина "Теория автоматов " обеспечивает приобретение знаний и умений в соответствии с Федеральным государственным образовательным стандартом, содействует фундаментализации образования, формированию мировоззрения и развитию логического мышления. Цели дисциплины: - овладение студентами математическим аппаратом, необходимым для применения математических методов в практической деятельности и в исследованиях; - ознакомление студентов с понятиями, фактами и методами, составляющими теоретические основы информатики; - развитие логического мышления; - обеспечение студентов знаниями по конкретному объекту – конечным автоматам, необходимые для понимания математики. В частности одного из классов алгоритмов, имеющего важное значение для программирования. Задачи изучения дисциплины: - изучить материал дисциплины; - усвоить основные понятия и методы, изучаемые в процессе освоения материала дисциплины; - приобрести навыки самостоятельного решения задач различной степени сложности; - выработать умение проводить анализ полученных в процессе решения фактов и результатов; - обобщить и систематизировать полученные знания, умения и навыки.
Дисциплина «Теория автоматов» в соответствии с Федеральным государственным образовательным стандартом высшего профессионального образования (ФГОС ВПО) по направлению «Математика и компьютерные науки» относится к профессиональному циклу. Дисциплины по выбору. Она является логическим продолжением базовых профессиональных курсов алгебры, математической логики и теории алгоритмов. С методической точки зрения она хорошо иллюстрирует общие теоремы и конструкции этих базовых дисциплин на примерах исследования свойств конкретных объектов – конечных автоматов. Знания, полученные после изучения этой дисциплины, позволяют ориентироваться в различных направлениях практической деятельности, связанных с дискретной математикой, защитой информации, компьютерными науками. В качестве входных знаний необходимы основы алгебры, математической логики и теории алгоритмов. Изучение этой дисциплины может сопровождаться практикумом на ЭВМ по теоретико - числовым алгоритмам с использованием пакетов прикладных программ, таких как «Математика и компьютерные науки», и практикумом по параллельным методам решения теоретико-числовых задач на кластерах. В ходе изучения дисциплины «Теория автоматов» студенты должны усвоить основные понятия и методы теории автоматов, получить основные сведения о структурах, используемых в персональных компьютерах. Освоение дисциплины предусматривает приобретение навыков работы с соответствующими учебниками, учебными пособиями, монографиями, научными статьями. На основе приобретенных знаний формируются умения применять математические методы при решении профессиональных задач повышенной сложности, владеть методами построения математической модели профессиональных задач и содержательной интерпретации полученных результатов. Знание теории автоматов может существенно помочь в научно-исследовательской работе.
В результате освоения ООП бакалавриата выпускник должен обладать следующими компетенциями: -выпускник должен обладать следующими общекультурными компетенциями (ОК): способностью применять в научно-исследовательской и профессиональной деятельности базовые знания в области фундаментальной и прикладной математики и естественных наук (ОК-6); способностью и постоянной готовностью совершенствовать и углублять свои знания, быстро адаптироваться к любым ситуациям (ОК-8); умением быстро находить, анализировать и грамотно контекстно обрабатывать научно-техническую, естественнонаучную и общенаучную информацию, приводя ее к проблемно-задачной форме (ОК-10); значительными навыками самостоятельной работы с компьютером, программирования, использования методов обработки информации и численных методов решения базовых задач (ОК-12); базовыми знаниями в областях информатики и современных информационных технологий, навыками использования программных средств и навыками работы в компьютерных сетях, умением создавать базы данных и использовать ресурсы Интернета (ОК-13); - выпускник должен обладать следующими профессиональными компетенциями (ПК): научно-исследовательская и научно-изыскательская деятельность: умением понять поставленную задачу (ПК-2); умением формулировать результат (ПК-3); умением самостоятельно увидеть следствия сформулированного результата (ПК-6); умением грамотно пользоваться языком предметной области (ПК-7); умением ориентироваться в постановках задач (ПК-8); пониманием корректности постановок задач (ПК-10); навыками самостоятельного построения алгоритма и его анализа (ПК-11); пониманием того, что фундаментальное знание является основой компьютерных наук (ПК-12); способностью передавать результат проведенных физико-математических и прикладных исследований в виде конкретных рекомендаций, выраженной в терминах предметной области изучавшегося явления (ПК-15); выделением главных смысловых аспектов в доказательствах (ПК-16); умением извлекать полезную научно-техническую информацию из электронных библиотек, реферативных журналов, сети Интернет (ПК-17); производственно-технологическая деятельность: владением методом алгоритмического моделирования при анализе постановок математических задач (ПК-19); владением методами математического и алгоритмического моделирования при анализе и решении прикладных и инженерно-технических проблем (ПК-20); владением проблемно-задачной формой представления математических и естественнонаучных знаний (ПК-21); умением увидеть прикладной аспект в решении научной задачи, грамотно представить и интерпретировать результат (ПК-22); умением проанализировать результат и скорректировать математическую модель, лежащую в основе задачи (ПК-23); организационно-управленческая деятельность: умением самостоятельно математически и физически корректно ставить естественнонаучные и инженерно-физические задачи и организовывать их решение в рамках небольших коллективов (ПК-25); В результате освоения дисциплины обучающийся должен: Знать: понятие конечного автомата (КА) и его вариантов, диаграммы КА, упрощение диаграммы до приведённого вида, языки, реализуемые в КА, поведение КА с выходом, игровая интерпретация детермизации, возможности расшифровки «черных ящиков». Уметь: по языку строить КА, реализующий этот язык ( если это возможно) и диаграмму этого КА, склеивать тупиковые вершины и нерациональные состояния, по КА определять двухполюсник, соответствующий ему, расшифровывать КА с заданной частотой.
Семестр 8. Форма промежуточной аттестации: зачет, экзамен. Общая трудоемкость дисциплины составляет 3 зачетные единицы, 108 часов. 3. Тематический план. Таблица 1. Тематический план.
. Таблица 2. Виды и формы оценочных средств в период текущего контроля.
Таблица 3. Планирование самостоятельной работы студентов.
Курс «Теория автоматов» является специальным курсом, продолжающим курс «Теория алгоритмов» и читается в восьмом семестре. Так как последующие дисциплины отсутствуют, то и связи с последующими дисциплинами отсутствуют.
Модуль 1. 1.1. Конечные автоматы (КА). Определение конечного автомата (КА) и их варианты ( автомат без памяти, автономный, без выхода, с задержкой, автомат Мура). Диаграммы автоматов. Потоки и язык.
Неразличимые состояния и недостижимые вершины. Приведённый КА. Эквивалентность КА, автоматов Мура и КА без выхода. Модуль 2.
Представление языков. Взаимозаменяемость и различимость слов. Распознание свойств КА.
Источники и макроисточники. Двухполюсники. Удаление недостижимых вершин, склеивание близнецов и тупиковых вершин. Операции над источниками. Детерминизация источников. Теоремы о конкатенации и итерации. Модуль 3. 3.1. Поведение КА с выходом. Игры и стратегии. Игровая интерпретация проблем униформизации. Теорема о порядковых стратегиях. Спектры достижимости и различимости. Параметры КА. Проблемы униформизации. 3.2. Расшифровка КА. Алгоритмы расшифровки КА. Расшифровка относительных «чёрных ящиков». Частотные критерии. Интерактивные алгоритмы. Расшифровка абсолютных «чёрных ящиков».
Модуль 1. 1.1. Конечные автоматы (КА). Словарные операторы и КА. Задание КА и их диаграмм. Примеры КА и их варианты. Декартовы произведения автоматов. Всеобщий язык и конкатенции слов.
Эквивалентные КА. Алгоритм получения по данныму КА эквивалентного ему приведённого КА. Муровская эквивалентность. Вес оператора и реализующего его КА. Модуль 2. 2.1. Поведение КА без выход Представление языков в КА. Операции над языками (. Отношение взаимозамещаемости на примерах, классы неразличимости. Распознание пустоты и бесконечности языка КА. Проекции, примеры. 2.2. Детерминизация источников. Упрощение источников: удаление недостижимых вершин, склеивание близнецов, тупиковых вершин на примерах диаграмм КА, Конкатенация и итерация языков. Грамматики и КА. Модуль 3. 3.1. Поведение КА с выходом. Предвосхищение. Константные операторы и вес КА. Примеры конечных игр, определение выиграшных стратегий у белых (чёрных), Порядковые векторы, реализация игр автоматами. 3.2. Расшифровка КА. Смысл расшифровки и её варианты. Примеры краткого безусловного алгоритма. Остаточная различимость и оценки абсолютной степени восстановления. Примеры интерактивных и кратных алгоритмов.
Не предусмотрены.
Не предусмотрены.
Текущая аттестация: Три контрольные работы ( примеры контрольных работ указаны ниже). Промежуточная аттестация: Зачет,экзамен (письменно-устная форма). К экзамену по дисциплине допускаются все успешно прошедшие текущий контроль . Экзамены оцениваются по системе: неудовлетворительно, удовлетворительно, хорошо, отлично. Текущий и промежуточный контроль освоения и усвоения материала дисциплины осуществляется в рамках рейтинговой (100-балльной) и традиционной (4-балльной) систем оценок. Варианты контрольных работ. Контрольная работа № 1.
Контрольная работа № 2.
Построить КА B, реализующий язык
Контрольная работа № 3.
Темы рефератов:
Вопросы к зачету: Дать определение и привести примеры - КА и его диаграммы; - КА без памяти и его диаграмма; - КА автономный и его диаграмма; - КА без выхода и его диаграмма; - КА с задержкой и его диаграмма; - автомат МУРА и его диаграмма; - Языков Я и ¬Я; - Я1 Я2 и Y- цилиндр Я; - взаимозамещаемости и неразрешимости ; - распознаваемости свойств КА; - проекции и источники; - операций конкатенации и детерминизации; - итерации и сильной итерации; - эквивалентности и приведенного КА; - представление языков и униформизации; - игры и её стратегии; - метаязыка регулярных формул; - «черного ящика» и его расшифровки. Вопросы к экзамену: Привести доказательство теоремы - о приведенных КА; - о КА Мура; - о совпадении языков; - Клини; - о числе классов неразрешимости; - о распознаваемости свойств КА - о двухполюснике; - о замкнутости классов языков; - о детерминизации; - Ершова - Лупанова; - об играх и стратегиях; - о кратном алгоритме расшифровки; - о метаязыке И.
При чтении лекций применяются технологии объяснительно-иллюстративного и проблемного обучения в сочетании с современными информационными технологиями обучения (различные демонстрации с использованием проекционного и мультимедийного оборудования). При проведении практических занятий применяются технологии проблемного обучения, дифференцированного обучения, репродуктивного обучения, а также современные информационные технологии обучения (самостоятельное изучение студентами учебных материалов в электронной форме, выполнение студентами электронных практикумов, различные демонстрации с использованием проекционного мультимедийного оборудования). При организации самостоятельной работы применяются технологии проблемного обучения, проблемно-исследовательского обучения (в частности, при самостоятельном изучении части теоретического материала), дифференцированного обучения, репродуктивного обучения, а также современные информационные технологии обучения (системы поиска информации, работа с учебно-методическими материалами, размещенными на сайте университета). В процессе проведения аудиторных занятий используются следующие активные и интерактивные методы и формы обучения: проблемная лекция, проблемное практическое занятие, работа в малых группах, практические занятия в диалоговом режиме, самостоятельная работа с учебными материалами. 11.Учебно-методическое и информационное обеспечение дисциплины . 11.1. Основная литература: 1. Трахтенброт Б.А., Барздинь Я.М. «Конечные автоматы», М: «Наука», 1970. 2. Глушков В.М. «Синтез цифровых автоматов» , М:, «Наука», 1962. 3. Гаврилов М.А. «Теория релейно-контактных схем», Издательство АН СССР, 1960. 4. Гилл А. «Введение в теорию конечных автоматов», 1966. 5. Мальцев И.А. «Дискретная математика», Санкт –Петербург: Издательство ООО «Издательство «Лань», 2010. -304 с. 11.2. Дополнительная литература: 6. Мальцев А.И. «алгоритмы и рекурсивные функции., М: «Наука», 2005. 7. Айзерман М.А., Гусев Л.А. «»логика, автоматы, алгоритмы»,М: Физматлит, 2003. 12.Технические средства и материально-техническое обеспечение дисциплины. Учебные аудитории для проведения лекционных и практических занятий, в том числе, оснащённые мультимедийным оборудованием, доступ студентов к компьютеру с Microsoft Office. |