Программа учебной дисциплины


Модуль 2. Основы теории алгоритмов



Скачать 278.34 Kb.
страница4/6
Дата30.07.2018
Размер278.34 Kb.
ТипПрограмма
1   2   3   4   5   6

Модуль 2. Основы теории алгоритмов


Виды учебной работы

Объем

в часах

Сроки

проведения, недели

Лекции

8

9–11

Семинары

8

9–11

Лабораторные работы







Практические занятия







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







  • домашнее задание №2 «Теория алгоритмов»

12

9–11

  • рубежный контроль №2

4

11

  • проработка лекционного материала, подготовка к семинарам

10




Трудоемкость, час

34




Трудоемкость, зач.единицы

0,9




Контроль освоения модуля 2

Неделя проведения

контроля модуля

Формы контроля


Оценка в баллах

Минимальная

максимальная

5

Домашнее задание

7

10

5

Рубежный контроль

19

30




ИТОГО

26

40

После освоения модуля 2 студент должен приобрести следующие знания, умения и владения, соответствующие компетенциям ООП.

Знания

Компетенции

  • понятие конструктивного объекта и интуитивная концепция вычислимости;

  • понятие машины Тьюринга как точной модели алгоритма;

  • понятие нормального алгорифма Маркова как точной модели алгоритма;

  • основные положения теории алгоритмов: сочетания (алгебра алгоритмов), универсальный алгоритм, разрешимость и перечислимость – на основе модели нормального алгорифма;

  • основные алгоритмически неразрешимые проблемы и понятие сводимости.

ОК-1, ОК-2, ОК-4, ОК-11, ОК-12, ОК-16
ПК-1, ПК-2, ПК-11


Умения

Компетенции

  • составлять программы машин Тьюринга и схемы нормальных алгорифмов Маркова для простых вычислимых функций;

  • анализировать разрешимость (неразрешимость) конкретных проблем.

ОК-1, ОК-2, ОК-4, ОК-11,

ОК-12
ПК-4, ПК-5,

ПК-14





Владение навыками

Компетенции

  • программирования заданных функций в виде программ машин Тьюринга и схем нормальных алгорифмов;

  • обоснования корректности построенной программы (схемы).

ОК-1, ОК-2, ОК-4, ОК-11
ПК-5, ПК-12, ПК-13

Содержание модуля 2

Лекции

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

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

Нормальные алгорифмы Маркова (4 ч.). Понятие нормального алгорифма. Процесс работы нормального алгорифма со словом. Вычислимость по Маркову и принцип нормализации. Способы сочетания нормальных алгорифмов. Универсальный нормальный алгорифм. Разрешимые и перечислимые множества. Проблема применимости нормальных алгорифмов как неразрешимая проблема.

Семинары

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

Разработка схем нормальных алгорифмов Маркова (2 ч.). Разработка схем нормальных алгорифмов для разных вербальных функций.

Разрешимость и перечислимость (2 ч.). Разработка разрешающих нормальных алгоритмов для некоторых множеств. Разработка нормальных перечисляющих алгорифмов для некоторых множеств.

Рубежный контроль (2 ч.).

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

В модуле 2 предусмотрено выполнение домашнего задания, а также самостоятельная проработка материала лекций и семинаров и подготовка к итоговой аттестации (рубежному контролю). Рубежный контроль проводится в форме письменной работы на семинарском занятии.





Поделитесь с Вашими друзьями:
1   2   3   4   5   6


База данных защищена авторским правом ©znate.ru 2019
обратиться к администрации

    Главная страница