элементы теории алгоритмов формализация понятия алгоритма

Главная Контакты Карта сайта Новости
Карта сайта Контакты Новости Учебные материалы Рефераты Фотоальбом Литература Дипломное проектирование Требования по оформлению курсовых, дипломных работ (проектов) Публикации Автоматизированная информационная система Системы автоматизированного проектирования Понятие информационной технологии Классификация автоматизированных информационных технологий Виды информационных технологий Информация Подходы к оценке информации Свойства информации Виды информации Понятие информационных ресурсов Коммуникационные свойства информации Этапы развития информатизации Пользователи средств информатизации Информационный обмен Методы и модели оценки количества информации Основные понятия теории алгоритмов Системы счисления Формы представления и преобразования информации Представление символьной информации в ЭВМ Индикаторы переноса и переполнения Сбор информации Автоматизированная обработка информации Управленческая информация Реквизиты информации Классификация экономической информации Обработка информации Передача информации Режимы обработки информации CALS - технологии Компьютерные сети Российский рынок финансово-экономических программ Информатизация государственного управления Управление персоналом в сфере информатизации CASE-средства Стандартизация программного продукта Программные продукты Информационный процесс представления знаний Документальные информационные системы База данных Информационная безопасность экономических систем Компьютерный вирус Имитационное моделирование Глоссарий Стандартизация разработки программных средств Надежность и качество программных средств Тестирование программного средства Консультации о поступлении Сетевые технологии. INTERNET Формирование технологической среды информационной системы ЭВМ Вычислительные сети Информационные технологии Научно-исследовательская деятельность Конкурсы и олимпиады Центр тестирования иностранных граждан по русскому языку Вебинары ЛОГИКА Базы данных Страница841
Основные понятия теории алгоритмов

Теория алгоритмов — раздел математики, изучающий общие свойства алгоритмов. Понятие «алгоритм» сформировалось в мате­матике в 20-х годах XX в. Началом систематической разработки теории алгоритмов можно считать 1936 г. и связывают это начало с публикацией работы А.А. Черча.
Под алгоритмом всегда (и до возникновения строгой теории) понималась процедура, которая позволяла путем выполнения после­довательности элементарных шагов получать однозначный результат (независящий от того, кто именно выполнял эти шаги) или за конечное число шагов прийти к выводу о том, что решения не существует.
Конечно же это нестрогое определение понятия алгоритма и именно попытки сформулировать такое понятие привели к возник­новению теории алгоритмов. Причиной развития этой теории были внутренние проблемы математики и лишь с возникновением и развитием вычислительной техники и смежных наук выяснилось, что в основе этих наук должна лежать теория алгоритмов. Так стало очевидным прикладное значение новой науки.
В основе формализации понятия «алгоритм» лежит идея построения алгоритмической модели. Составляющими такой модели должны быть конкретный набор элементарных шагов, способы определения следующего шага и т.д. От модели также требуется простота и универсальность. Требование простоты важно для того, чтобы выделить действительно необходимые элементы и свойства алгоритма и облегчить доказательства общих утверждений об свойствах. Универсальность необходима для того, чтобы моде позволяла описать любой алгоритм.
Результатами теоретических исследований явились три основных класса арифметических моделей.
Первый класс моделей основан на арифметизации алгоритмов. Предполагается, что любые данные можно закодировать числами, как следствие - всякое их преобразование становится в этом случае арифметическим вычислением, алгоритмом в таких моделях ее вычисление значения некоторой числовой функции, а его элемент» тарные шаги - арифметические операции. Последовательность ша­гов определяется двумя способами. Первый способ - суперпозиция, т.е. подстановка функции в функцию, а второй - рекурсия, т.е. определение значения функции через «ранее» вычисленные значения этой же функции. Функции, которые можно построить из целых чисел и арифметических операций с помощью суперпозиций рекурсивных определений, называются рекурсивными функциями. Простейшим примером рекурсивной функции является факториал.

Второй класс моделей порожден следующей идеей. Для тог чтобы алгоритм понимался однозначно, а его каждый шаг считался элементарным и выполнимым, он должен быть представлен чтобы его могла выполнять машина, к которой предъявляются уже упомянутые требования простоты и универсальности. Одной из машин явилась абстрактная машина Тьюринга. Машина Тьюринга состоит из трех частей ленты, головки и управляющего устройства (УУ). Лента бесконечна в обе стороны и разбита на ячейки. Элементарный шаг машины Тьюринга состоит из следующих действий:
головка считывает символ, записанный в ячейке, над которой она находится;
считанный символ и текущее состояние головки однозначно определяют новое состояние, новый записываемый символ и перемещение головки (которое может иметь значение на ячейку влево, на ячейку вправо, остаться на месте).
Устройство управления хранит и выполняет команды машины.
Третий класс моделей алгоритмов очень близок к предыдущему, но не оперирует конкретными машинными механизмами. Наиболее известная алгоритмическая модель этого типа - нормальные алгоритмы Маркова.
Для нормального алгоритма задается алфавит, над которым он работает, конечное множество допустимых подстановок и порядок их применения. Если в качестве алфавита взять алфавит русского языка, а в качестве множества подстановок то, используя правила 1— 3:
1) проверить возможность подстановок в порядке возрастания их номеров, и если она возможна (левая часть подстановки обнаружена в
исходном слове), произвести подстановку (заменив левую часть на правую);
2) если в примененной подстановке имеется символ «!», то преобразования прекращаются, а если нет, то текущее состояние
становится исходным и весь процесс начинается заново;
3) если ни одна подстановка не применима, то процесс преобразования завершен, можно обнаружить, что по заданному алгоритму исходное слово.
В теории алгоритмов строго доказано, что по своим возможностям преобразования нормальные алгоритмы эквивалентные машине Тьюринга и другим моделям, уточняющим понятия алгоритма.
Появление точного понятия алгоритма позволило сформулировать алгоритмически не разрешимые проблемы, т.е. задачи, для; решения которых невозможно построить алгоритм. Задача называется алгоритмически неразрешимой, если не существует машины Тьюринга (или рекурсивной функции, или нормального алгоритме Маркова), которая ее решает. Например, неразрешимой оказалась проблема распознавания эквивалентности алгоритмов: нельзя построить алгоритм, который по любым двум алгоритмам (программам) выяснял бы, вычисляют они одну и ту же функцию или нет. Знание основных неразрешимостей теории алгоритмов необходимо для специалиста по информатике. Оно предостережет его от увлечения глобальными прожектами всеобщей алгоритмизации точно так как знание основных законов физики предостерегает от попыток создания вечного двигателя.
{SHOW_TEXT}
Социальный интеллект Творческая система Квалификация знаний Методы и модели оценки количества информации Количественная оценка информации Системы счисления Позиционные системы счисления Формы представления и преобразования информации Смешанные системы счисления Другие позиционные системы счисления
Образовательный сайт Бармашовой Л.В.
Рассылки
Subscribe.Ru Современное образование
Подписаться письмом
Приглашаем принять участие в круглом столе!
подробнее >>> Институт Менеджмента, Экономики и Инноваций начинает набор на курсы повышения квалификации!
подробнее >>> Уважемые студенты АНО ВПО ИМЭиИ!
подробнее >>>
все новости...

элементы теории алгоритмов реферат

элементы теории алгоритмов интуит

Элементы теории алгоритмов, рекурсивные функции, машина Тьюринга. курс лекций [651,0 K], добавлен 08.08.2011.

Читать

элементы теории алгоритмов и программирование

вы можете посмотреть здесь. ender 6391. Элементы теории алгоритмов. Варпаховский Ф.Л.