Алгоритмы. Роль алгоритмизации в решении задач и формализации знаний

 

Название " алгоритм" произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi), жившего в 783—850 гг. В своей книге " Об индийском счете" он изложил правила записи натуральных чисел с помощью арабских цифр и правила действий над ними " столбиком", знакомые теперь каждому школьнику. В XII веке эта книга была переведена на латынь и получила широкое распространение в Европе.

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

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

1. Понятность — исполнитель алгоритма должен понимать, как его выполнять. Иными словами, имея алгоритм и произвольный вариант исходных данных, исполнитель должен знать, как надо действовать для выполнения этого алгоритма.

2. Дискpетность (прерывность, раздельность) — разбиение процесса обработки на более простые шаги.

3. Опpеделенность — каждое пpавило алгоpитма должно быть четким, однозначным. Благодаpя этому свойству выполнение алгоpитма носит механический хаpактеp и не тpебует никаких дополнительных указаний или сведений о pешаемой задаче.

4. Pезультативность (или конечность) состоит в том, что алгоритм должен приводить к правильному результату при всех допустимых входных значения.

5. Массовость означает, что один и тот же алгоритм можно использовать с разными исходными данными

На практике наиболее распространены следующие формы представления алгоритмов:

• словесная (запись на естественном языке);
• графическая (изображения из графических символов);
• программная (тексты на языках программирования).

Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.

Например. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел (алгоритм Эвклида).

Алгоритм может быть следующим:

1. задать два числа;

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

3. определить большее из чисел;

4. заменить большее из чисел разностью большего и меньшего из чисел;

5. повторить алгоритм с шага 2.

Описанный алгоритм применим к любым натуральным числам и должен приводить к решению поставленной задачи. Убедитесь в этом самостоятельно, определив с помощью этого алгоритма наибольший общий делитель чисел 125 и 75.

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

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

Название символа	Обозначение и пример заполнения	Пояснение
Процесс		Вычислительное действие или последовательность действий
Решение		Проверка условий
Модификация		Начало цикла
Предопределенный процесс		Вычисления по подпрограмме, стандартной подпрограмме
Ввод-вывод		Ввод-вывод в общем виде
Пуск-останов		Начало, конец алгоритма, вход и выход в подпрограмму
Документ		Вывод результатов на печать

 

Блок " процесс" применяется для обозначения действия или последовательности действий, изменяющих значение, форму представления или размещения данных. Для улучшения наглядности схемы несколько отдельных блоков обработки можно объединять в один блок. Представление отдельных операций достаточно свободно.

Блок " решение" используется для обозначения переходов управления по условию. В каждом блоке " решение" должны быть указаны вопрос, условие или сравнение, которые он определяет.

Блок " модификация" используется для организации циклических конструкций. (Слово модификация означает видоизменение, преобразование). Внутри блока записывается параметр цикла, для которого указываются его начальное значение, граничное условие и шаг изменения значения параметра для каждого повторения.

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

Алгоритмы можно представлять как некоторые структуры, состоящие из отдельных базовых (т.е. основных) элементов.

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

1. Базовая структура " линейная". Образуется последовательностью действий, следующих одно за другим:

	блок-схема
действие 1 действие 2......... действие n

2. Базовая структура " ветвление". Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран. Структура ветвление существует в четырех основных вариантах:

• если—то;
• если—то—иначе;
• выбор;
• выбор—иначе.

	блок-схема
1. если—то
если условие то действия все
2. если—то—иначе
если условие то действия 1 иначе действия 2 все
3. выбор
выбор при условие 1: действия 1 при условие 2: действия 2............ при условие N: действия N все
4. выбор—иначе
выбор при условие 1: действия 1 при условие 2: действия 2............ при условие N: действия N иначедействия N+1 все

 

Примеры структуры ветвление

 

	Язык блок-схем
если x > 0 то y: = sin(x) все
если a > b то a: = 2*a; b: = 1 иначе b: = 2*b все
выбор при n = 1: y: = sin(x) при n = 2: y: = cos(x) при n = 3: y: = 0 все
выбор при a > 5: i: = i+1 при a = 0: j: = j+1 иначе i: = 10; j: =0 все

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

	Язык блок-схем
Цикл типа пока. Предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова пока.
нц пока условие тело цикла (последовательность действий) кц
Цикл типа для. Предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне.
нц для i от i1до i2 тело цикла (последовательность действий) кц

 

Примеры структуры цикл

 

Школьный алгоритмический язык	Язык блок-схем
нц пока i < = 5 S: = S+A[i] i: = i+1 кц
нц для i от 1 до 5 X[i]: = i*i*i Y[i]: = X[i]/2 кц

 

 

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

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

Пример вложенных циклов “ для “

Вычислить сумму элементов заданной матрицы А(5, 3).

Матрица А

S: = 0; нц для i от 1 до 5 нц для j от 1до 3 S: =S+A[i, j] кц кц

Пример вложенных циклов “ пока “

Вычислить произведение тех элементов заданной матрицы A(10, 10), которые расположены на пересечении четных строк и четных столбцов.

i: =2; P: =1 нц пока i < = 10 j: =2 нц пока j < = 10 P: =P*A[i, j] j: =j+2 кц i: =i+2 кц

 

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

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

Следовательно, язык для записи алгоритмов должен быть формализован. Такой язык принято называть языком программирования, а запись алгоритма на этом языке — программой для компьютера.

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

Любой алгоритм есть последовательность предписаний, выполнив которые можно за конечное число шагов перейти от исходных данных к результату. В зависимости от степени детализации предписаний обычно определяется уровень языка программирования — чем меньше детализация, тем выше уровень языка.

По этому критерию можно выделить следующие уровни языков программирования:

• машинные;
• машинно-оpиентиpованные (ассемблеpы);
• машинно-независимые (языки высокого уровня).

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

Языки высокого уровня делятся на:

• процедурные (алгоритмические) (Basic, Pascal, C и др.), которые предназначены для однозначного описания алгоритмов; для решения задачи процедурные языки требуют в той или иной форме явно записать процедуру ее решения;
• логические (Prolog, Lisp и др.), которые ориентированы не на разработку алгоритма решения задачи, а на систематическое и формализованное описание задачи с тем, чтобы решение следовало из составленного описания;
• объектно-ориентированные (Object Pascal, C++, Java и др.), в основе которых лежит понятие объекта, сочетающего в себе данные и действия над нами.
• 55555555555555555555555555555555555555555

Программное обеспечение ПК

Под программным обеспечением (Software) понимается совокупность программ, выполняемых вычислительной системой.

К программному обеспечению (ПО) относится также вся область деятельности по проектированию и разработке ПО:

• технология проектирования программ (например, нисходящее проектирование, структурное и объектно-ориентированное проектирование и др.);
• методы тестирования программ;
• методы доказательства правильности программ;
• анализ качества работы программ;
• документирование программ;
• разработка и использование программных средств, облегчающих процесс проектирования программного обеспечения, и многое другое.

Программное обеспечение — неотъемлемая часть компьютерной системы. Оно является логическим продолжением технических средств. Сфера применения конкретного компьютера определяется созданным для него ПО.

Программное обеспечение современных компьютеров включает миллионы программ — от игровых до научных.

 

⇐ Предыдущая45678910111213Следующая ⇒

Поделиться: