Категория
Информатика
Тип
реферат
Страницы
5 стр.
Дата
26.04.2009
Формат файла
.rtf — Rich Text Format (Wordpad)
Архив
18529.zip — 23.63 kb
  • formalizacija-ponjatija-algoritma_18529_1.rtf — 260.03 Kb
  • Readme_docus.me.txt — 125 Bytes
Рейтинг
6.67  из 10
Оценок
3
Оцените работу
Хорошо  или  Плохо


Текст работы

Формализация понятия алгоритма
Формализация понятия алгоритма
Д ля глубокого, строгого изучения свойств алгоритма и его организации необходима формализация, хотя бы для того, чтобы иметь возможность делать доказательные утверждения о свойствах алгоритма. Подчеркнем, что цель математического уточнения
понятия Алгоритма - изучение его свойств, а не создание практического инструмента для построения алгоритмов.
Один из возможных путей формализации состоит в том, чтобы подобрать понятия, уже известные в математике, и для которых уже разработан формализм. Одним из таких понятий-претендентов является функция. Действительно, на первый взгляд между функцией и алгоритмом есть много общего. У функции есть область определения, у алгоритма есть область применимости; у функции
есть область допустимых значений, у алгоритма есть определенное множество результатов.
Рассмотрим взаимосвязь между функцией и алгоритмом. Сразу отметим, что основные свойства этой взаимосвязи мы будем здесь приводить без доказательства. Тому есть как минимум две причины. Первая - у читателя не предполагается знания необходимого математического аппарата; вторая - это увело
бы нас в сторону от основной цели - формализации понятия алгоритма.
Определение 2 .1. Говорят, что алгоритм А вычисляет функцию f(x) , если:
Существует взаимно однозначное соответствие
между областью определения f (х) и областью применимости А
;
Для любого х из области определения f верно: f ( x )
= А ( (x))
В этом случае функция f(x) называется вычислимой функцией .
Определение 2.2. Говорят, что Алгоритм А разрешает множество М относительно множества Х, где М Х, если:
Для любого х из множества М верно, что А(х) = “истина” ;
Для любого у из Х, но



Ваше мнение



CAPTCHA