русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

ИНТУИТИВНОЕ ПОНЯТИЕ АЛГОРИТМА, ОПЕРАЦИИ


Дата добавления: 2013-12-23; просмотров: 1908; Нарушение авторских прав


 

Теория алгоритмов возникла в математической логике как вспомогательная дисциплина, предназначенная для внутренних потребностей математики. Основными задачами, которые стояли перед ней, были: исследование феномена неразрешимости и обоснование математики. Практические применения теории алгоритмов первоначально основывались на интуитивном понятии алгоритма, поскольку математическое понятие алгоритма было разработано только для некоторых частных случаев, далеких от того, с чем приходится иметь дело на практике. Аналитическая теория алгоритмов, изучающая все их многообразие, возникла лишь в последнее десятилетие.

Интуитивное понятие алгоритма. Интуитивное понятие алгоритма рисует нам его как строго сформулированное правило, следуя которому можно осуществить процесс решения задачи, причем осуществить механически, максимально экономя усилия.

О п р е д е л е н и е. Алгоритм - это предписание, ведущее от исходных данных к искомому результату и обладающее свойствами: 1) определенности (общепонятности и точности); 2) массовости; 3) результативности.

Такое представление об алгоритме еще очень неясно, но его нетрудно уточнить. Такое уточнение нужно делать, во-первых, конкретизируя сказанное только что и, во-вторых, анализируя классические теории алгоритмов.

Алгоритм задается как предложение формального языка (это запись алгоритма) и определяет дискретный процесс преобразования исходного данного, запись которого является тоже предложением (другого) формального языка, в искомый результат (тоже предложение формального языка). Понятность алгоритма заключается в том, что для его выполнения должен быть задан другой алгоритм, называемый алгоритмом выполнения (или интерпретации), для которого исходным данным является совокупность записи алгоритма и записи операнда (объединяющая их символьная конструкция). От особенностей алгоритма выполнения зависит процесс, определяемый алгоритмом. Для некоторых вариантов исходных данных этот процесс содержит конечное число шагов (это - результативность алгоритма), но возможны и такие исходные данные, для которых алгоритмический процесс безрезультативно обрывается или никогда не заканчивается. В первом случае говорят, что алгоритм применим к исходному данному, а в двух последних - что неприменим.



Алгоритмический процесс состоит из шагов, каждый из которых представляет собой выполнение достаточно простых операций. Существует набор простейших операций, называемых натуральными, все же остальные операции - это отображения, индуцируемые алгоритмами. При определении нового класса алгоритмов достаточно простыми считаются операции, которые уже получены.

Такое понимание алгоритма неминуемо ведет к тому, что его определение принимают вид рекурсивного определения (новые алгоритмы строятся с помощью уже имеющихся). Процесс рекурсивного определения должен начинаться с определения каких-то алгоритмов, не опирающегося на понятие алгоритма, иначе все определение в целом являлось бы так называемым порочным кругом. В соответствии с вышесказанным широкое формальное определение алгоритма начинается с того, что вводится понятие первичных алгоритмов. Однако, поскольку понятие первичных алгоритмов связано с понятием операции, остановимся вначале на этом понятии.

Операции.

О п р е д е л е н и е. Операциями называются: 1) натуральные операции (см. ниже); 2) линеаризация и делинеаризация (см. ниже); 3) двухместная операция соединения слов (конкатенация); 4) всякое объявленное операцией отображение, осуществляемое алгоритмом.

Определим натуральные операции. Предварительно определим одну частную символьную конструкцию, которая нам при этом потребуется.

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

О п р е д е л е н и е. Конструкция, которая получится, если в непустом слове одну из букв выделить с помощью выделяющей связи (т.е. связать ее этой связью), называется квазисловом. Началом квазислова называется его буква, связанная начинающей связью следования, а его концом - связанная заканчивающей связью следования.

В качестве натуральных операций выбраны операции, умение выполнять которые при построении теории алгоритмов обычно постулируют, считая, что каждый человек умеет выполнять эти операции. Некоторые натуральные операции являются в действительности классами операций, причем для выделения индивидуальной операции должна быть указана буква языка операндов, которую мы будем в описаниях обозначать метасимволом a (см. табл.3.1).

Натуральные операции делятся на натуральные действия и натуральные условия. В свою очередь, натуральные действия делятся на четыре группы. В группу I входят преобразования слов в слова; в группу II - преобразования слов в квазислова; в группу III - преобразования квазислов в квазислова; наконец, в группу IV - преобразования квазислов в слова. V группу натуральных операций образуют условия, выполнение которых не изменяет операнда, но ставит ему в соответствие логическое значение (истина, если условие выполнено, или ложь, если не выполнено). Прежде чем приступить к разъяснению операций линеаризации и делинеаризации, рассмотрим проблему получения всевозможных нумераций произвольной совокупности предметов, если известна какая-нибудь их нумерация.



<== предыдущая лекция | следующая лекция ==>
Базовый FORTRAN (Formula translation). | ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ АЛГОРИТМА


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.004 сек.