Рабочая программа составлена в соответствии с требованиями фгос впо с учетом рекомендаций и Прооп впо по направлению и профилю подготовки рабочая программа дисциплины опубликована на сайте ТюмГУ: «Теория алгоритмов»






Скачать 197.56 Kb.
НазваниеРабочая программа составлена в соответствии с требованиями фгос впо с учетом рекомендаций и Прооп впо по направлению и профилю подготовки рабочая программа дисциплины опубликована на сайте ТюмГУ: «Теория алгоритмов»
Дата публикации16.02.2015
Размер197.56 Kb.
ТипРабочая программа
l.120-bal.ru > Документы > Рабочая программа
РОССИЙСКАЯ ФЕДЕРАЦИЯ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ


Государственное образовательное учреждение

высшего профессионального образования

ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Институт математики, естественных наук и информационных технологий

Кафедра алгебры и математической логики



Дёгтев А.Н.

Теория алгоритмов

Учебно-методический комплекс. Рабочая программа

для студентов очной формы обучения

НАПРАВЛЕНИЕ 010100.62 «МАТЕМАТИКА»,

профиль подготовки: «Алгебра, теория чисел, математическая логика».

Тюменский государственный университет
2011

Дёгтев А.Н.Теория алгоритмов. Учебно-методический комплекс. Рабочая программа для студентов направления 010100.62 – МАТЕМАТИКА, профиль подготовки: «Алгебра, теория чисел, математическая логика», форма ОБУЧЕНИЯ – ОЧНАЯ. Тюмень, 2011, 11 стр.

Рабочая программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ПрООП ВПО по направлению и профилю подготовки.

Рабочая программа дисциплины опубликована на сайте ТюмГУ:

«Теория алгоритмов» [электронный ресурс] / Режим доступа: http://www.umk3.utmn.ru., свободный.

Рекомендовано к изданию кафедрой алгебры и математической логики. Утверждено проректором по учебной работе Тюменского государственного университета.

ОТВЕТСТВЕННЫЙ РЕДАКТОР: заведующий кафедрой алгебры и математической логики доктор физико-математических наук, профессор

Кутрунов В.Н.






© Тюменский государственный университет, 2011.

© Дёгтев А.Н.., 2011.


  1. Пояснительная записка:

1.1. Цели и задачи дисциплины.

Дисциплина "Теория алгоритмов " обеспечивает приобретение знаний и умений в соответствии с Федеральным государственным образовательным стандартом, содействует фундаментализации образования, формированию мировоззрения и развитию логического мышления.

Цели дисциплины:

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

- ознакомление студентов с понятиями, фактами и методами, составляющими теоретические основы информатики;

- развитие логического мышления;

- обеспечение студентов знаниями по конкретному объекту – теории алгоритмов, необходимые для понимания математики. В частности одного из классов алгоритмов, имеющего важное значение для программирования.

Задачи изучения дисциплины:

- изучить материал дисциплины;

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

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

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

- обобщить и систематизировать полученные знания, умения и навыки.

    1. Место дисциплины в структуре ООП бакалавриата.


Дисциплина «Теория алгоритмов» в соответствии с Федеральным государственным образовательным стандартом высшего профессионального образования (ФГОС ВПО) по направлению «Математика» относится к профессиональному циклу. Дисциплины по выбору. Она является логическим продолжением базовых профессиональных курсов алгебры, математической логики и теории алгоритмов. С методической точки зрения она хорошо иллюстрирует общие теоремы и конструкции этих базовых дисциплин на примерах исследования свойств конкретных объектов – конечных автоматов. Знания, полученные после изучения этой дисциплины, позволяют ориентироваться в различных направлениях практической деятельности, связанных с дискретной математикой, защитой информации, компьютерными науками. В качестве входных знаний необходимы основы алгебры, математической логики и теории алгоритмов. Изучение этой дисциплины может сопровождаться практикумом на ЭВМ по теоретико - числовым алгоритмам с использованием пакетов прикладных программ, таких как «Математика», и практикумом по параллельным методам решения теоретико-числовых задач на кластерах.

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

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

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

Знание теории алгоритмов может существенно помочь в научно-исследовательской работе.
    1. Компетенции выпускника ООП бакалавриата, формируемые в результате освоения данной ООП ВПО.



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

-   выпускник должен обладать следующими общекультурными компетенциями (ОК):

способностью применять знания на практике (ОК-6);

способностью приобретать новые знания, используя современные образовательные и информационные технологии (ОК-8);

способностью понимать сущность и значение информации в развитии современного общества, соблюдением основных требований информационной безопасности, в том числе защиты государственных интересов и приоритетов (ОК-9);

фундаментальной подготовкой по основам профессиональных знаний и готовностью к использованию их в профессиональной деятельности (ОК-11);

навыками работы с компьютером (ОК-12);

базовыми знаниями в областях информатики и современных информационных технологий, навыки использования программных средств и навыки работы в компьютерных сетях, умение создавать базы данных и использовать ресурсы Интернет (ОК-13);

способностью к анализу и синтезу (ОК-14);

- выпускник должен обладать следующими профессиональными компетенциями (ПК):

научно-исследовательская и научно-изыскательская деятельность:

умением понять поставленную задачу (ПК-2);

умением формулировать результат (ПК-3);

умением грамотно пользоваться языком предметной области (ПК-7);

пониманием того, что фундаментальное знание является основой компьютерных наук (ПК-12);

умением извлекать полезную научно-техническую информацию из электронных библиотек, реферативных журналов, сети Интернет (ПК-17);

производственно-технологическая деятельность:

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

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

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

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

Владеть: математическим аппаратом, необходимым для профессиональной деятельности.


  1. Структура и трудоемкость дисциплины.


Семестр 6. Форма промежуточной аттестации: зачет. Общая трудоемкость дисциплины составляет 3 зачетные единицы, 108 часов.
3. Тематический план.

Таблица 1.

Тематический план.



Тема

недели семестра

Виды учебной работы и самостоятельная работа, в час.

Итого часов по теме

Из них в интерактивной форме

Итого количество баллов

Лекции*

Семинарские (практические) занятия*

Самостоятельная работа*










1

2

3

4

5

7

8

9

10




Модуль 1






















1.1.

Алгоритмы

1 – 3

6

3

9

18

2

0-17

1.2.

Рекурсивные функции


4 –6

6

3

9

18

2

0-18




Всего




12

6

18

36

4

0-35




Модуль 2






















2.1.

Решение РПМ

7 – 9

6

3

9

18

2

0-17

2.2.

Сводимости.

10-12

6

3

9

18

2

0-18




Всего




12

6

18

36

4

0-35




Модуль 3






















3.1.

Комбинаторные множества

13 – 15

6

3

9

18

1

0-15

3.2.

Импликативные множества

16 – 18

6

3

9

18

2

0-15




Всего




12

6

18

36

3

0-30




Итого (часов, баллов):




36

18

54

108

11

0-100




Из них часов в интерактивной форме




3

8














Таблица 2.

Виды и формы оценочных средств в период текущего контроля.



Устный опрос

Письменные работы

Итого количество

баллов

собеседование

ответ на семинаре

Контрольная

работа

Домашняя

работа

реферат




Модуль 1



















1.1.




0-1

0-14

0-2




0-17

1.2.




0-2

0-14

0-2




0-18

Всего




0-3

0-28

0-4




0-35

Модуль 2



















2.1.




0-1

0-14

0-2




0-17

2.2.

0-1

0-1

0-14

0-2




0-18

Всего

0-1

0-2

0-28

0-4




0-35

Модуль 3



















3.1.







0-10

0-1




0-11

3.2.

0-4




0-10

0-1

0-4

0-19

Всего

0-4




0-20

0-2

0-4

0-30

Итого

0-5

0-5

0-76

0-10

0-4

0-100


Таблица 3.

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



Модули и темы

Виды СРС

Неделя семестра

Объем часов

Кол-во баллов

обязательные

дополнительные

Модуль 1
















1.1

Алгоритмы

Повторение пройденного материала. Выполнение домашних заданий

Подготовка к контрольной работе

1 -3

9

0-17

1.2

Рекурсивные функции








4-6

9

0-18




Всего по модулю 1:

18

0-35

Модуль 2
















2.1

Решение РПМ.

Повторение пройденного материала. Выполнение домашних заданий

Подготовка к контрольной работе

7-9

9

0-17

2.2

Сводимости.

Повторение пройденного материала. Выполнение домашних заданий

Подготовка к контрольной работе

10-12

9

0-18




Всего по модулю 2:

18

0-35

Модуль 3
















3.1

Комбинаторные множества

Повторение пройденного материала. Выполнение домашних заданий

Подготовка к контрольной работе

15 – 15

9

0-15

3.2

Импликативные множества.

типовых задач

Подготовка рефератов

16 – 18

9

0-15




Всего по модулю 3:

18

0-30




ИТОГО:

54

0-100



  1. Разделы дисциплины и междисциплинарные связи с обеспечиваемыми (последующими) дисциплинами

№ п/п

Наименование обеспечиваемых (последующих) дисциплин

Темы дисциплины необходимые для изучения обеспечиваемых (последующих) дисциплин

1.1

1.2

2.1

2.2


3.1

3.2


1.

Производственная практика




+

+

+




+




Криптография и криптоанализ

+

+




+

+

+




Теория нечетких множеств

+

+

+













Теория автоматов

+

+

+

+

+

+




Фракталы и их приложения

+

+

+













Вейвлет анализ сигналов и изображений

+

+

+











Содержание дисциплины.

Модуль 1.

1.1. Алгоритмы.

Понятие формализации вычислений функции. Продукции Поста. Нормальные и операторные алгоритмы. Теорема Дегловса.

    1. Рекурсивные функции.

Определение рекурсивной и универсальной функции. Теоремы Клини о рекурсии и неподвижной точке. Теорема Райса-Шапиро и Майхилла. Две теоремы Поста ( о рекурсивных и простых множествах). Теоремы Уллиана, Деккера и Дёгтева.

Модуль 2.

    1. Решение РПМ.

Структура РПМ. Теоремы Фридберга и Лахлана. Конструкции с китайскими ящиками. Теоремы Робинсона и Дёгтева об описании фактор - решетки РПМ по модулю простых множеств.

    1. Сводимости.

Сводимости табличного типа. Теорема Булитко-Селиванова. Конструкции со счетчиками. Верхняя полурешетка m-степеней. О полурешеткахстепеней табличного типа. Нераспадающиеся степени.


Модуль 3.

3.1. Комбинаторные множества

.

Описание комбинаторных и селекторных множеств.

3.2. Импликативные множества.

Описание импликативно-селекторных и слабо-импликативных множеств размерности 3.

  1. Планы семинарских занятий.

Модуль 1.

1.1. Алгоритмы.

Написание по заданной функции программы машины Тьюринга, продукций Поста, нормального алгоритма Маркова и схемы операторного алгоритма.

    1. . Рекурсивные функции

Написание по заданной функции её схемы рекурсии. Решение задач на теоретико-множественные операции над рекурсивно перечислимыми множествами (РПМ). Построение универсальной рекурсивной функции. Задачи на применение теоремы о неподвижной точке.Примеры РПМ с ретрассируемыми, регрессивными и полурекурсивными дополнениями.

Модуль 2.

2.1. Решение РПМ.

Применение конструкции с китайскими ящиками. Дальнейшее ознакомление с результатами о РПМ.

2.2. Сводимости.

Разбор теоремы Булитко-Селиванова. Написание счетчиков для основных и ограниченных сводимостей табличного типа. Дальнейшее ознакомление с результатами о верхних полурешетках РП степеней, элементарными теоремами и соотношениями между полными множествами для основных сводимостей табличного типа (m-.d-.c-.l-.p-.tt-).

Модуль 3.

3.1. Комбинаторные множества

. Классификация булевых функций (БФ) от трех существенных переменных. Выяснение свойств (прелюдия к основным теоремам).

3.2. Импликативные множества.

В результате классификации БФ , выяснение их импликативно-селекторных свойств. Анализ последней статьи автора о слабо ИС-множествах.

  1. Темы лабораторных работ (Лабораторный практикум).

Не предусмотрены.

  1. Примерная тематика курсовых работ

Не предусмотрены

  1. Учебно - методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины.

Текущая аттестация:

Предусмотрено проведение контрольных работ ( примеры контрольных работ указаны ниже), написание рефератов.

Заключительная аттестация:

Зачет (письменно-устная форма).

К зачету по дисциплине допускаются все успешно прошедшие текущий контроль .

Текущий и промежуточный контроль освоения и усвоения материала дисциплины осуществляется в рамках рейтинговой (100-балльной).

Варианты контрольных работ.

Контрольная работа № 1.

  1. Доказать теорему Райса-Шапиро.

  2. Написать программу для МТ, вычисляющую функции

(а) .

(б) g(x)=2 при x=0; при x=1 и приx≥2.
Контрольная работа № 2.

  1. Построить максимальное множество (Фридберг).

  2. Доказать, что пересечение двух простых множеств будет простым множеством.



Контрольная работа № 3.

  1. Доказать, что класс

  2. Доказать, что различных классов - импликативно-селекторных множеств, где - позитивная БФ, бесконечно много.


Темы рефератов:

  1. Законспектировать главу монографии Х.Роджерса .

  2. Законспектировать §21 монографии А.Дёгтева [1].

  3. Вопросы к зачету:

  1. Вычисление числовых функций с помощью

(а) машины Тьюринга ;

(б) продукций Поста;

(в) нормальных алгоритмов Маркова;

(г) операторных алгоритмов.

2. Определение операций суперпозиции, примитивной ру\екурсии и минимизации. Тезис Чёрча.

3. Формулировки теорем Клини о рекурсии и неподвижной точки для частично рекурсивных функций различных местностей, эти же теоремы для рекурсивно перечислимых отношений.

4. Результаты Райса – Шапиро и Майхилла. Классы РПМ и теоремы о доопределении ЧРФ и принципы редукции.

5. Сплинтеры. Теорема Уллианы. Регрессивные и ретрассируемые множества, наследственные и полурекурсивные, их простые свойства.

6. определение сводимостей табличного типа и результаты Булитко- Селиванова.

7. Понятие счетчика для разных сводимостей, конструкции с ними.

8. Решетка РПМ. Теоремы Фридберга о разбиении и Лахлана о гипергиперпростых множествах

9. Теоремы Робинсона и Дёгтева ( без доказательства).

10. Определение (слабо) комбинаторно-селекторных и импликативно-селекторных множеств, основные теоремы о них.

  1. Образовательные технологии.

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

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

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

В процессе проведения аудиторных занятий используются следующие активные и интерактивные методы и формы обучения: проблемная лекция, проблемное практическое занятие, работа в малых группах, практические занятия в диалоговом режиме, самостоятельная работа с учебными материалами.
11.Учебно-методическое и информационное обеспечение дисциплины .

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

1. Дёгтев А.Н. Рекурсивно перечислимые множества и сводимости, М: «Наука», 1998

2. дёгтев А.Н. Избранные результаты по теории алгоритмов Тюмень:, Издательство ТюмГУ,2008.

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

3. Мальцев А.И. «Алгоритмы и рекурсивные функции., М: «Наука», 1965.

4. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость, М: «Мир», 1972.

Айзерман М.А., Гусев Л.А. «Логика, автоматы, алгоритмы»,М: Физматгиз, 1963.
12.Технические средства и материально-техническое обеспечение дисциплины.

Учебные аудитории для проведения лекционных и практических занятий, в том числе, оснащённые мультимедийным оборудованием, доступ студентов к компьютеру с Microsoft Office.

.

Добавить документ в свой блог или на сайт

Похожие:

Рабочая программа составлена в соответствии с требованиями фгос впо с учетом рекомендаций и Прооп впо по направлению и профилю подготовки рабочая программа дисциплины опубликована на сайте ТюмГУ: «Теория алгоритмов» iconРабочая программа составлена в соответствии с требованиями фгос впо...
Дёгтев А. Н. Теория алгоритмов. Учебно-методический комплекс. Рабочая программа для студентов направления 010200. 62 – математика...

Рабочая программа составлена в соответствии с требованиями фгос впо с учетом рекомендаций и Прооп впо по направлению и профилю подготовки рабочая программа дисциплины опубликована на сайте ТюмГУ: «Теория алгоритмов» iconРабочая программа дисциплины (модуля) опубликована на сайте ТюмГУ
...

Рабочая программа составлена в соответствии с требованиями фгос впо с учетом рекомендаций и Прооп впо по направлению и профилю подготовки рабочая программа дисциплины опубликована на сайте ТюмГУ: «Теория алгоритмов» iconРабочая программа дисциплины опубликована на сайте ТюмГУ: Россия...
...

Рабочая программа составлена в соответствии с требованиями фгос впо с учетом рекомендаций и Прооп впо по направлению и профилю подготовки рабочая программа дисциплины опубликована на сайте ТюмГУ: «Теория алгоритмов» iconРабочая программа дисциплины (модуля) опубликована на сайте ТюмГУ:...
...

Рабочая программа составлена в соответствии с требованиями фгос впо с учетом рекомендаций и Прооп впо по направлению и профилю подготовки рабочая программа дисциплины опубликована на сайте ТюмГУ: «Теория алгоритмов» iconРабочая программа составлена в соответствии с требованиями фгос впо...
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

Рабочая программа составлена в соответствии с требованиями фгос впо с учетом рекомендаций и Прооп впо по направлению и профилю подготовки рабочая программа дисциплины опубликована на сайте ТюмГУ: «Теория алгоритмов» iconРабочая программа составлена в соответствии с требованиями фгос впо...
Рассмотрено на заседании умк института гуманитарных наук 21. 04. 2011. Протокол №1

Рабочая программа составлена в соответствии с требованиями фгос впо с учетом рекомендаций и Прооп впо по направлению и профилю подготовки рабочая программа дисциплины опубликована на сайте ТюмГУ: «Теория алгоритмов» iconРабочая программа составлена в соответствии с требованиями фгос впо...
Рассмотрено на заседании умк института гуманитарных наук 21. 04. 2011. Протокол №1

Рабочая программа составлена в соответствии с требованиями фгос впо с учетом рекомендаций и Прооп впо по направлению и профилю подготовки рабочая программа дисциплины опубликована на сайте ТюмГУ: «Теория алгоритмов» iconРабочая программа составлена в соответствии с требованиями фгос впо...
Рассмотрено на заседании умк института гуманитарных наук 21. 04. 2011. Протокол №1

Рабочая программа составлена в соответствии с требованиями фгос впо с учетом рекомендаций и Прооп впо по направлению и профилю подготовки рабочая программа дисциплины опубликована на сайте ТюмГУ: «Теория алгоритмов» iconРабочая программа составлена в соответствии с требованиями фгос впо...
Рассмотрено на заседании умк института гуманитарных наук 21. 04. 2011. Протокол №1

Рабочая программа составлена в соответствии с требованиями фгос впо с учетом рекомендаций и Прооп впо по направлению и профилю подготовки рабочая программа дисциплины опубликована на сайте ТюмГУ: «Теория алгоритмов» iconРабочая программа составлена в соответствии с требованиями фгос впо...
Рассмотрено на заседании умк института гуманитарных наук 21. 04. 2011. Протокол №1

Вы можете разместить ссылку на наш сайт:


Литература


При копировании материала укажите ссылку ©ucheba 2000-2015
контакты
l.120-bal.ru
..На главную