Рабочая программа составлена в соответствии с требованиями фгос впо с учетом рекомендаций и Прооп впо по направлению и профилю подготовки рабочая программа дисциплины опубликована на сайте ТюмГУ: «Теория алгоритмов»
Скачать 197.57 Kb.
|
РОССИЙСКАЯ ФЕДЕРАЦИЯМИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИГосударственное образовательное учреждение высшего профессионального образования ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Институт математики, естественных наук и информационных технологийКафедра алгебры и математической логикиДёгтев А.Н. Теория алгоритмов Учебно-методический комплекс. Рабочая программа для студентов очной формы обучения НАПРАВЛЕНИЕ 010100.62 «МАТЕМАТИКА», профиль подготовки: «Алгебра, теория чисел, математическая логика». Тюменский государственный университет 2011 Дёгтев А.Н.Теория алгоритмов. Учебно-методический комплекс. Рабочая программа для студентов направления 010100.62 – МАТЕМАТИКА, профиль подготовки: «Алгебра, теория чисел, математическая логика», форма ОБУЧЕНИЯ – ОЧНАЯ. Тюмень, 2011, 11 стр. Рабочая программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ПрООП ВПО по направлению и профилю подготовки. Рабочая программа дисциплины опубликована на сайте ТюмГУ: «Теория алгоритмов» [электронный ресурс] / Режим доступа: http://www.umk3.utmn.ru., свободный. Рекомендовано к изданию кафедрой алгебры и математической логики. Утверждено проректором по учебной работе Тюменского государственного университета. ОТВЕТСТВЕННЫЙ РЕДАКТОР: заведующий кафедрой алгебры и математической логики доктор физико-математических наук, профессорКутрунов В.Н.© Тюменский государственный университет, 2011. © Дёгтев А.Н.., 2011.
1.1. Цели и задачи дисциплины. Дисциплина "Теория алгоритмов " обеспечивает приобретение знаний и умений в соответствии с Федеральным государственным образовательным стандартом, содействует фундаментализации образования, формированию мировоззрения и развитию логического мышления. Цели дисциплины: - овладение студентами математическим аппаратом, необходимым для применения математических методов в практической деятельности и в исследованиях; - ознакомление студентов с понятиями, фактами и методами, составляющими теоретические основы информатики; - развитие логического мышления; - обеспечение студентов знаниями по конкретному объекту – теории алгоритмов, необходимые для понимания математики. В частности одного из классов алгоритмов, имеющего важное значение для программирования. Задачи изучения дисциплины: - изучить материал дисциплины; - усвоить основные понятия и методы, изучаемые в процессе освоения материала дисциплины; - приобрести навыки самостоятельного решения задач различной степени сложности; - выработать умение проводить анализ полученных в процессе решения фактов и результатов; - обобщить и систематизировать полученные знания, умения и навыки.
Дисциплина «Теория алгоритмов» в соответствии с Федеральным государственным образовательным стандартом высшего профессионального образования (ФГОС ВПО) по направлению «Математика» относится к профессиональному циклу. Дисциплины по выбору. Она является логическим продолжением базовых профессиональных курсов алгебры, математической логики и теории алгоритмов. С методической точки зрения она хорошо иллюстрирует общие теоремы и конструкции этих базовых дисциплин на примерах исследования свойств конкретных объектов – конечных автоматов. Знания, полученные после изучения этой дисциплины, позволяют ориентироваться в различных направлениях практической деятельности, связанных с дискретной математикой, защитой информации, компьютерными науками. В качестве входных знаний необходимы основы алгебры, математической логики и теории алгоритмов. Изучение этой дисциплины может сопровождаться практикумом на ЭВМ по теоретико - числовым алгоритмам с использованием пакетов прикладных программ, таких как «Математика», и практикумом по параллельным методам решения теоретико-числовых задач на кластерах. В ходе изучения дисциплины «Теория алгоритмов» студенты должны усвоить основные понятия и методы теории алгоритмов, получить основные сведения о структурах, используемых в персональных компьютерах. Освоение дисциплины предусматривает приобретение навыков работы с соответствующими учебниками, учебными пособиями, монографиями, научными статьями. На основе приобретенных знаний формируются умения применять математические методы при решении профессиональных задач повышенной сложности, владеть методами построения математической модели профессиональных задач и содержательной интерпретации полученных результатов. Знание теории алгоритмов может существенно помочь в научно-исследовательской работе.
В результате освоения ООП бакалавриата выпускник должен обладать следующими компетенциями: - выпускник должен обладать следующими общекультурными компетенциями (ОК): способностью применять знания на практике (ОК-6); способностью приобретать новые знания, используя современные образовательные и информационные технологии (ОК-8); способностью понимать сущность и значение информации в развитии современного общества, соблюдением основных требований информационной безопасности, в том числе защиты государственных интересов и приоритетов (ОК-9); фундаментальной подготовкой по основам профессиональных знаний и готовностью к использованию их в профессиональной деятельности (ОК-11); навыками работы с компьютером (ОК-12); базовыми знаниями в областях информатики и современных информационных технологий, навыки использования программных средств и навыки работы в компьютерных сетях, умение создавать базы данных и использовать ресурсы Интернет (ОК-13); способностью к анализу и синтезу (ОК-14); - выпускник должен обладать следующими профессиональными компетенциями (ПК): научно-исследовательская и научно-изыскательская деятельность: умением понять поставленную задачу (ПК-2); умением формулировать результат (ПК-3); умением грамотно пользоваться языком предметной области (ПК-7); пониманием того, что фундаментальное знание является основой компьютерных наук (ПК-12); умением извлекать полезную научно-техническую информацию из электронных библиотек, реферативных журналов, сети Интернет (ПК-17); производственно-технологическая деятельность: возможностью преподавания физико-математических дисциплин и информатики в средней школе и средних специальных образовательных учреждениях на основе полученного фундаментального образования (ПК-29). В результате освоения дисциплины обучающийся должен: Знать: понятие формализации вычислений, методы построения алгоритма. описание и методы решения по теоретико-множественным операциям над рекурсивно-перечислимыми множествами. Уметь: строить алгоритмы для поставленных математических задач, строить универсальные рекурсивные функции. Применять теоремы о неподвижной точке. Владеть: математическим аппаратом, необходимым для профессиональной деятельности.
Семестр 6. Форма промежуточной аттестации: зачет. Общая трудоемкость дисциплины составляет 3 зачетные единицы, 108 часов. 3. Тематический план. Таблица 1. Тематический план.
Таблица 2. Виды и формы оценочных средств в период текущего контроля.
Таблица 3. Планирование самостоятельной работы студентов.
Содержание дисциплины. Модуль 1. 1.1. Алгоритмы. Понятие формализации вычислений функции. Продукции Поста. Нормальные и операторные алгоритмы. Теорема Дегловса.
Определение рекурсивной и универсальной функции. Теоремы Клини о рекурсии и неподвижной точке. Теорема Райса-Шапиро и Майхилла. Две теоремы Поста ( о рекурсивных и простых множествах). Теоремы Уллиана, Деккера и Дёгтева. Модуль 2.
Структура РПМ. Теоремы Фридберга и Лахлана. Конструкции с китайскими ящиками. Теоремы Робинсона и Дёгтева об описании фактор - решетки РПМ по модулю простых множеств.
Сводимости табличного типа. Теорема Булитко-Селиванова. Конструкции со счетчиками. Верхняя полурешетка m-степеней. О полурешеткахстепеней табличного типа. Нераспадающиеся степени. Модуль 3. 3.1. Комбинаторные множества . Описание комбинаторных и селекторных множеств. 3.2. Импликативные множества. Описание импликативно-селекторных и слабо-импликативных множеств размерности 3.
Модуль 1. 1.1. Алгоритмы. Написание по заданной функции программы машины Тьюринга, продукций Поста, нормального алгоритма Маркова и схемы операторного алгоритма.
Написание по заданной функции её схемы рекурсии. Решение задач на теоретико-множественные операции над рекурсивно перечислимыми множествами (РПМ). Построение универсальной рекурсивной функции. Задачи на применение теоремы о неподвижной точке.Примеры РПМ с ретрассируемыми, регрессивными и полурекурсивными дополнениями. Модуль 2. 2.1. Решение РПМ. Применение конструкции с китайскими ящиками. Дальнейшее ознакомление с результатами о РПМ. 2.2. Сводимости. Разбор теоремы Булитко-Селиванова. Написание счетчиков для основных и ограниченных сводимостей табличного типа. Дальнейшее ознакомление с результатами о верхних полурешетках РП степеней, элементарными теоремами и соотношениями между полными множествами для основных сводимостей табличного типа (m-.d-.c-.l-.p-.tt-). Модуль 3. 3.1. Комбинаторные множества . Классификация булевых функций (БФ) от трех существенных переменных. Выяснение свойств (прелюдия к основным теоремам). 3.2. Импликативные множества. В результате классификации БФ , выяснение их импликативно-селекторных свойств. Анализ последней статьи автора о слабо ИС-множествах.
Не предусмотрены.
Не предусмотрены
Текущая аттестация: Предусмотрено проведение контрольных работ ( примеры контрольных работ указаны ниже), написание рефератов. Заключительная аттестация: Зачет (письменно-устная форма). К зачету по дисциплине допускаются все успешно прошедшие текущий контроль . Текущий и промежуточный контроль освоения и усвоения материала дисциплины осуществляется в рамках рейтинговой (100-балльной). Варианты контрольных работ. Контрольная работа № 1.
(а)  .(б) g(x)=2 при x=0; при x=1 и приx≥2. Контрольная работа № 2.
Контрольная работа № 3.
Темы рефератов:
(а) машины Тьюринга ; (б) продукций Поста; (в) нормальных алгоритмов Маркова; (г) операторных алгоритмов. 2. Определение операций суперпозиции, примитивной ру\екурсии и минимизации. Тезис Чёрча. 3. Формулировки теорем Клини о рекурсии и неподвижной точки для частично рекурсивных функций различных местностей, эти же теоремы для рекурсивно перечислимых отношений. 4. Результаты Райса – Шапиро и Майхилла. Классы РПМ и теоремы о доопределении ЧРФ и принципы редукции. 5. Сплинтеры. Теорема Уллианы. Регрессивные и ретрассируемые множества, наследственные и полурекурсивные, их простые свойства. 6. определение сводимостей табличного типа и результаты Булитко- Селиванова. 7. Понятие счетчика для разных сводимостей, конструкции с ними. 8. Решетка РПМ. Теоремы Фридберга о разбиении и Лахлана о гипергиперпростых множествах 9. Теоремы Робинсона и Дёгтева ( без доказательства). 10. Определение (слабо) комбинаторно-селекторных и импликативно-селекторных множеств, основные теоремы о них.
При чтении лекций применяются технологии объяснительно-иллюстративного и проблемного обучения в сочетании с современными информационными технологиями обучения (различные демонстрации с использованием проекционного и мультимедийного оборудования). При проведении практических занятий применяются технологии проблемного обучения, дифференцированного обучения, репродуктивного обучения, а также современные информационные технологии обучения (самостоятельное изучение студентами учебных материалов в электронной форме, выполнение студентами электронных практикумов, различные демонстрации с использованием проекционного мультимедийного оборудования). При организации самостоятельной работы применяются технологии проблемного обучения, проблемно-исследовательского обучения (в частности, при самостоятельном изучении части теоретического материала), дифференцированного обучения, репродуктивного обучения, а также современные информационные технологии обучения (системы поиска информации, работа с учебно-методическими материалами, размещенными на сайте университета). В процессе проведения аудиторных занятий используются следующие активные и интерактивные методы и формы обучения: проблемная лекция, проблемное практическое занятие, работа в малых группах, практические занятия в диалоговом режиме, самостоятельная работа с учебными материалами. 11.Учебно-методическое и информационное обеспечение дисциплины . 11.1. Основная литература: 1. Дёгтев А.Н. Рекурсивно перечислимые множества и сводимости, М: «Наука», 1998 2. дёгтев А.Н. Избранные результаты по теории алгоритмов Тюмень:, Издательство ТюмГУ,2008. 11.2. Дополнительная литература: 3. Мальцев А.И. «Алгоритмы и рекурсивные функции., М: «Наука», 1965. 4. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость, М: «Мир», 1972. Айзерман М.А., Гусев Л.А. «Логика, автоматы, алгоритмы»,М: Физматгиз, 1963. 12.Технические средства и материально-техническое обеспечение дисциплины. Учебные аудитории для проведения лекционных и практических занятий, в том числе, оснащённые мультимедийным оборудованием, доступ студентов к компьютеру с Microsoft Office. . | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
- импликативно-селекторных множеств, где Добавить документ в свой блог или на сайт
