Структура и содержание дисциплины

2.2 Структура дисциплины 
 
Распределение видов учебной работы и их трудоемкости по разделам дисциплины. 
Разделы дисциплины, изучаемые в _4_ семестре (очная форма). 
 
 
 
№ 
Раздела 
 
 
Наименование раздела 
Количество часов 
 
Всего 
Аудиторная работа 
Самостоятельная 
работа 
Лек ЛР КСР ИКР СРС 
Контроль 
 
1 
Алгоритмы и 
алгоритмические 
проблемы 
 
12 
 
4 
 
2 
 
12 
 
2 
Вычислимость по 
Тьюрингу и другие 
модели вычислений 
 
34 
 
10 
 
18 
 
12 
3 
Универсальная машина 
Тьюринга 
12 
4 
6 
2 
6 
4 
Алгоритмически 
неразрешимые проблемы 
12 
4 
4 
10 
5 
Рекурсивные функции 
28 
10 
14
10
6 
Основы сетей Петри 
46 
2 
6
0,3 
8 
35,7 
7 
Всего 
180 
34 
50 
2 
0,3 
58 
35,7 

2.3 Содержание разделов дисциплины 
 
2.3.1 Занятия лекционного типа 
 
 
№ 
раздела 
 
Наименование 
раздела 
 
 
Содержание раздела 
Форма 
текущег 
о 
контрол 
я 
1 
2 
3 
4 
 
1 
Алгоритмы и 
алгоритмическ 
ие проблемы 
Понятие алгоритма и его свойства. Необходимость 
формализации алгоритма и ее варианты. Примеры 
алгоритмически неразрешимых проблем. 
 
ЛР 
 
2 
Вычислимость 
по Тьюрингу и 
другие модели 
вычислений 
Машина Тьюринга, диаграмма Тьюринга и ее 
примеры. Простейшие машины Тьюринга. 
Нормированная вычислимость. Вычислимость 
функций по Тьюрингу и композиции функций. 
 
ЛР 
 
3 
Универсальная 
машина 
Тьюринга 
Словарное описание машины Тьюринга. Формат 
ленты и принцип работы универсальной машины 
Тьюринга. Работа кодировщика и декодировщика в 
схеме универсальной машины. 
 
ЛР 
 
4 
Алгоритмическ 
и 
неразрешимые 
проблемы 
Проблема самоприменимости. Проблемы 
остановки машины Тьюринга. Проблема 
соответствия Поста. Проблема домино. 
 
ЛР 
 
 
 
 
5 
 
 
 
Рекурсивные 
функции 
Базовые функции. Операторы рекурсии, 
минимизации. Классы примитивно рекурсивных и 
частично рекурсивных функций. Теоремы о 
суммировании, мультиплицировании и неявной 
функции. Канторовская и геделевская нумерации. 
Рекурсивные и рекурсивно перечислимые множест- 
ва и их свойства. Характеризация рекурсивно 
перечислимых множеств и частично рекурсивных 
функций. Теоремы Клини и Успенского-Райса. 
Функция Аккермана и ее свойства. 
 
 
 
 
ЛР 
 
6 
 
Основы сетей 
Петри 
Структурное описание сети Петри. Примеры 
описания известных задач синхронизации сетями 
Петри. Классификация сетей Петри. Диаграмма 
маркировок. 
 
ЛР 

2.3.2 Занятия семинарского типа 
 
Учебным планом не предусмотрены. 
2.3.3 Лабораторные занятия 
 
№ 
работы 
№ раздела 
дисциплины 
Наименование лабораторных работ 
1 
1 
Блок-схемы и диаграммы Несси-Шнейдермана 
 
2-10 
 
2 
Построение машин Тьюринга, нормальных алгоритмов для 
решения массовых проблем с конструктивными объектами. 
Анализ поведения заданных машин Тьюринга 
11-13 
3 
Словарные описания машин Тьюринга. Построение диаграмм 
Тьюринга. Варианты универсальных машин Тьюринга. 
 
14−15 
 
4 
Метод сведения одной алгоритмической проблемы к другой. 
Доказательства неразрешимости алгоритмических проблем 
методом Кантора. Примеры алгоритмических проблем. 

жүктеу/скачать 487,97 Kb.

Достарыңызбен бөлісу: