Программа дисциплины о. 17 «теория алгоритмов и вычислительных процессов»


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



Pdf көрінісі
бет3/9
Дата23.01.2023
өлшемі487,97 Kb.
#62533
түріПрограмма
1   2   3   4   5   6   7   8   9
Байланысты:
B1.O.17 Teorija algoritmov i vychislitel\'nyh processov 2021

 
2. Структура и содержание дисциплины 
 
2.1 Распределение трудоёмкости дисциплины по видам работ 
 
Общая трудоёмкость дисциплины составляет 5 зач.ед. (180 часов), их 
распределение по видам работ представлено в таблице
 
Вид учебной работы 
Всего 
часов 
Семестры 

Аудиторные занятия (всего) 
86,3 
86,3 
В том числе: 
Занятия лекционного типа 
34 
34 
Лабораторные занятия 
50 
50 
КСР 


ИКР 
0,3 
0,3 
Самостоятельная работа (всего) 
58 
58 
В том числе: 
Проработка учебного (теоретического) материала 
58 
58 
Промежуточная аттестации 
экзамен 
Контроль 
35,7 
35,7 
Общая трудоемкость 
час 
зач. ед. 
180 

180 
 
 
 
 


2.2 Структура дисциплины 
 
Распределение видов учебной работы и их трудоемкости по разделам дисциплины. 
Разделы дисциплины, изучаемые в _4_ семестре (очная форма). 
 
 
 
№ 
Раздела 
 
 
Наименование раздела 
Количество часов 
 
Всего 
Аудиторная работа 
Самостоятельная 
работа 
Лек ЛР КСР ИКР СРС 
Контроль 
 

Алгоритмы и 
алгоритмические 
проблемы 
 
12 
 

 

 
12 
 

Вычислимость по 
Тьюрингу и другие 
модели вычислений 
 
34 
 
10 
 
18 
 
12 

Универсальная машина 
Тьюринга 
12 





Алгоритмически 
неразрешимые проблемы 
12 


10 

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

Основы сетей Петри 
46 

6
0,3 

35,7 

Всего 
180 
34 
50 

0,3 
58 
35,7 


2.3 Содержание разделов дисциплины 
 
2.3.1 Занятия лекционного типа 
 
 
№ 
раздела 
 
Наименование 
раздела 
 
 
Содержание раздела 
Форма 
текущег 
о 
контрол 
я 




 

Алгоритмы и 
алгоритмическ 
ие проблемы 
Понятие алгоритма и его свойства. Необходимость 
формализации алгоритма и ее варианты. Примеры 
алгоритмически неразрешимых проблем. 
 
ЛР 
 

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

Универсальная 
машина 
Тьюринга 
Словарное описание машины Тьюринга. Формат 
ленты и принцип работы универсальной машины 
Тьюринга. Работа кодировщика и декодировщика в 
схеме универсальной машины. 
 
ЛР 
 

Алгоритмическ 
и 
неразрешимые 
проблемы 
Проблема самоприменимости. Проблемы 
остановки машины Тьюринга. Проблема 
соответствия Поста. Проблема домино
 
ЛР 
 
 
 
 

 
 
 
Рекурсивные 
функции 
Базовые функции. Операторы рекурсии, 
минимизации. Классы примитивно рекурсивных и 
частично рекурсивных функций. Теоремы о 
суммировании, мультиплицировании и неявной 
функции. Канторовская и геделевская нумерации. 
Рекурсивные и рекурсивно перечислимые множест- 
ва и их свойства. Характеризация рекурсивно 
перечислимых множеств и частично рекурсивных 
функций. Теоремы Клини и Успенского-Райса. 
Функция Аккермана и ее свойства. 
 
 
 
 
ЛР 
 

 
Основы сетей 
Петри 
Структурное описание сети Петри. Примеры 
описания известных задач синхронизации сетями 
Петри. Классификация сетей Петри. Диаграмма 
маркировок. 
 
ЛР 


2.3.2 Занятия семинарского типа 
 
Учебным планом не предусмотрены. 
2.3.3 Лабораторные занятия 
 
№ 
работы 
№ раздела 
дисциплины 
Наименование лабораторных работ 


Блок-схемы и диаграммы Несси-Шнейдермана 
 
2-10 
 

Построение машин Тьюринга, нормальных алгоритмов для 
решения массовых проблем с конструктивными объектами. 
Анализ поведения заданных машин Тьюринга 
11-13 

Словарные описания машин Тьюринга. Построение диаграмм 
Тьюринга. Варианты универсальных машин Тьюринга. 
 
14−15 
 

Метод сведения одной алгоритмической проблемы к другой. 
Доказательства неразрешимости алгоритмических проблем 
методом Кантора. Примеры алгоритмических проблем. 


Достарыңызбен бөлісу:
1   2   3   4   5   6   7   8   9




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет