Министерство образования и науки республики казахстан евразийский национальный университет им.Л.Н.Гумилева

Кафедра «Вычислительная техника»

________________________________

(наименование кафедры полностью)

______Бекенов Махсут Искандерович

доцент кафедры «Вычислительная техника» __

(ф. и. о. авторов, должность)

Методические указания

к семинарским, практическим и лабораторным занятиям по дисциплине

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

(наименование дисциплины)

для студентов специальности__5В070400

(шифр)

Вычислительная техника и программное обеспечение

(шифр, наименование специальности)

Астана, 2011

______ Бекенов Махсут Искандерович

(ф. и. о. авторов)

Методические указания к семинарским, практическим и лабораторным занятиям по дисциплине ______ Теория алгоритмов

(наименование дисциплины)

Астана, ЕНУ 2011г. ____79___ с.

(кол-во стр.)

Методические указания составлены в соответствии с требованиями учебного плана и программой дисциплины __ Теория алгоритмов

(наименование дисциплины)

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

Методические указания предназначены для студентов специальностей

____ Вычислительная техника и программное обеспечение

(наименование специальностей)

Утверждено на заседании кафедры ___________________________________

«______» ______________ 2011 г. / Протокол № _______________________/

Заведующий кафедрой ______________________ К.Т.Искаков.

(Ф.И.О. , подпись)

Утверждено учебно-методическим советом ______________________факультета

«_______» _________________ 2011 г. / Протокол № ___________________/

Председатель УМС _____________________________________________

(Ф.И.О. , подпись)

© Евразийский национальный университет им. Л.Н.Гумилева

© Бекенов Махсут Искандерович

Содержание

Исторический обзор 4

Цели и задачи теории алгоритмов 4

Практическое применение результатов теории алгоритмов 5

Формализация понятия алгоритма 5

Машина Тьюринга 7

Основная гипотеза теории алгоритмов (тезис Чёрча) 10

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

Тезис Маркова 12

Анализ трудоёмкости алгоритмов 16

Классы сложности 18

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

Лекция 1.