Лекции - Теория алгоритмов

Подождите немного. Документ загружается.

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

► Понятие алгоритма и вычислимой функции являются

наиболее фундаментальными понятиями математики,

логики и информатики.

► Многие теоретические и практические задачи требуют

указать алгоритм – такой набор инструкций, выполняя

которые, мы за конечное число шагов решим поставленную

задачу.

► Выработка точного понятия алгоритма является одним

из наиболее значительных достижений науки XX

столетия. Такое определение было получено в работах

выдающихся специалистов по математической логике

К.Геделя, А.Черча, Э.Поста, А.Тьюринга, А.А.Маркова.

► Систематическое изучение алгоритмов и различных

моделей вычислений привело к созданию ряда

прикладных дисциплин, развитию средств вычислительной

техники и современных коммуникаций. Развитие теории

алгоритмов в 30-е годы XX столетия, когда никаких

компьютеров еще не было, явилось стимулом для

появления в 40-х годах первых компьютеров.

Основатели теории алгоритмов

СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

1. Алгоритмы в математике. Основные черты

алгоритмов. Числовые функции и алгоритмы их

вычисления. Примитивно рекурсивные функции.

2. Частично рекурсивные функции. Тезис Черча.

3. Машины Тьюринга и машины с неограниченными

регистрами. Вычислимость частично рекурсивных

функций на МНР.

4. Нумерации и универсальные функции.

5. Нормальные алгорифмы.

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

7. Разрешимые и перечислимые множества и

предикаты.

Вопросы для зачета

1. Основные черты алгоритмов.

2. Числовые функции и алгоритмы их вычисления.

3. Примитивно рекурсивные функции.

4. Частично-рекурсивные функции.

5. Машины Тьюринга.

6. Машины с неограниченными регистрами.

7. Рекурсивные и рекурсивно-перечислимые множества.

8. Рекурсивно-перечислимые предикаты.

9. Нумерации.

10. Универсальная функция.

11. Неразрешимые алгоритмические проблемы.

ТРЕБОВАНИЯ К УРОВНЮ

ОСВОЕНИЯ ДИСЦИПЛИНЫ

►

Студент, изучивший дисциплину, должен знать:

► основные определения и теоремы из теории

алгоритмов: вычислимость в интуитивном

смысле; частично-рекурсивная функция,

перечислимое множество, понятие нумерации;

►

Студент, изучивший дисциплину, должен уметь:

► доказывать рекурсивность функций, должен

уметь составлять программы для машины

Тьюринга и для МНР, составлять схему

нормального алгорифма.

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

1. Игошин В.И. Задачник-практикум по математической

логике: учеб. пособие для студентов-заочников физ.-

мат. фак. пед. ин-тов. Подольск: Академия, 2005. –

156 с.

2. Ильиных А.П. Теория алгоритмов: учебное пособие.

Урал. гос. пед. ун-т. Екатеринбург, 2006. – 148 c.

3. Лавров Н.Я. , Л.Л. Максимова. Задачи по теории

множеств, математической логике и теории

алгоритмов. 5-е изд. – М.: Физмалит, 2004. – 256 с.

4. Мальцев А. И. Алгоритмы и рекурсивные функции. М.:

Наука, 1986. – 386 с.

Лекция 1. Алгоритмы в математике.

Основные черты алгоритмов

►Алгоритмы в математике.

Во многих разделах математики, логики и информатики

возникают вычислительные процедуры механического

характера. В них требуется найти решение конкретной

задачи по некоторому общему правилу (алгоритму) для

решения задач данного класса.

Примеры алгоритмов:

Сложение натуральных чисел.

5438+3745=9183.

Алгоритм Евклида.

Понятие алгоритма

(неформальное определение)

► Алгоритм – это точное предписание, которое задает

вычислительную процедуру.

► Данная процедура перерабатывает исходный набор данных

(входной объект) и направлена на получение обусловленного

этими данными результата

(объекта на выходе).

► Она состоит из отдельных, элементарных шагов – тактов работы

алгоритма. Каждый шаг заключается в смене одного набора

данных другим набором (объектом, состоянием).

► Переход от предыдущего состояния к последующему происходит

по заранее заданному, конечному набору инструкций.

► Эти инструкции не должны предполагать никаких догадок и

вероятностных соображений со стороны человека или машины,

нужно только точно их исполнять.

► Некоторые состояния опознаются как заключительные, при

которых процесс вычислений заканчивается. При этом на основе

некоторой инструкции определяется, что считать результатом

вычислений.

Три случая протекания

алгоритмического процесса

1. На некотором шаге возникает состояние, опознаваемое как

заключительное. При этом происходит остановка вычислений и выдается

результат

2. Каждое очередное состояние сменяется последующим до бесконечности,

т.е. процесс вычислений никогда не останавливается.

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

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

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

перехода к следующему шагу и нет результата вычислений. В этом случае

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

► Считается, что алгоритм

применим к исходному набору данных

тогда

и только тогда, когда выполнен случай 1, т.е. когда процесс вычислений

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

. Этот результат будем

обозначать через

A(P)

. В случаях 2 и 3 результат

A(P)

не существует.

Происхождение термина

«алгоритм»

► Само слово «алгоритм»

происходит от латинской

транслитерации «alchorismi»

или «algorismi» арабского

имени среднеазиатского

ученого ал-Хорезми

Мухаммеда бен Мусы (780 –

847). По латинским

переложениям

арифметического трактата

ал-Хорезми средневековая

Европа познакомилась с

индийской десятичной

позиционной системой

счисления.