Алгоритмы и величины
Слово "алгоритм" произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса аль-Хорезми (Alhorithmi), жившего в 783—850 гг. В своей книге "Об индийском счете" он изложил правила записи натуральных чисел с помощью арабских цифр и правила действий над ними "столбиком", знакомые теперь каждому школьнику. В XII веке эта книга была переведена на латынь и получила широкое распространение в Европе.
В течение длительного времени термин «алгоритм» употребляли преимущественно математики. При этом они пользовались так называемым интуитивным понятием алгоритма - заранее заданное, понятное и точное предписание возможному исполнителю совершить определенную последовательность действий для получения решения задачи за конечное число шагов.[1]
Решая различные задачи, математики столкнулись с рядом неразрешимых проблем, т.е. задач, для которых не удавалось создать решающий их алгоритм. Это стало предпосылкой к обоснованию сущности алгоритмов формальным, т.е. математическим путём.
Основные результаты теории алгоритмов были получены в 30-60 годах 20 века Э.Черчем, А. Тьюрингом, А. Постом, А. Колмогоровым, А. Марковым. Введенные в рассмотренные алгоритмические модели, машины Тьюринга, Поста дали возможность устанавливать алгоритмическую разрешимость проблемы путём построения соответствующих машин логического действия.
|
|
|
В настоящее время понятие алгоритма является не только одним из главных понятий математики, но одним из главных понятий современной науки. Более того, с наступлением эры информатики алгоритмы становятся одним из важнейших факторов цивилизации. [1]
Определение 1. Алгоритм – конечная последовательность детерминированных арифметических и логических действий над исходными и промежуточными данными задачи обработки информации, выполнение которых приводит к правильному ее решению, т.е. получению требуемых выходных данных. [2]
Свойства алгоритмов.
1. Понятность. Исполнитель алгоритма должен понимать, как его выполнять. Иными словами, имея алгоритм и произвольный вариант исходных данных, исполнитель должен знать, как надо действовать для выполнения этого алгоритма.
2. Дискретность (прерывность, раздельность). Алгоритм должен состоять из отдельных элементарных шагов. Количество шагов должно быть конечным, т.е. после выполнения этих шагов исполнитель должен остановиться. Если действия повторяются бесконечно, говорят, что алгоритм зациклился.
3. Определённость. Последовательность шагов алгоритма должна быть детерминированной (определённой). После каждого шага либо указывается, какой шаг выполнить дальше, либо даётся команда остановки, после этого действия алгоритма считаются законченными.
|
|
|
4. Результативность (конечность). После выполнения конечного количества шагов алгоритм должен выдавать правильный результат решения той или иной информационной задачи.
5. Массовость. Алгоритм решения задачи должен разрабатываться в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, так называемой области применимости алгоритма.[2]
Способы представления алгоритмов.
1. Графический (в виде блок-схемы).
2. Словесный, текстовый (в виде последовательности шагов, описывающих действия естественным языком).
3. Программный (в виде программы, полностью или сжато представленной на каком-либо алгоритмическом языке).
Наиболее наглядным считается графический способ. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т.п.) соответствует геометрическая фигура, представленная в виде блочного символа. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий.
|
|
|
Таблица 1 – Символы блок-схем алгоритмов
| Процесс | 
| Выполнение операций или групп операций, в результате которых изменяется значения, форма представления или расположение данных. |
| Решение |  
| Выбор направления выполнения алгоритма или программы в зависимости от некоторых переменных условий |
| Модификация | 
| Выполнение операций, меняющих команды ил группу команд, т.е. изменяющий программу |
| Предопределенный процесс |  
| Использование ранее созданных и отдельно описанных алгоритмов и программ |
| Ручной ввод | 
| Ввод данных оператором в процессе обработки при помощи устройства, непосредственно сопряжённого с вычислительной машиной |
| Дисплей | 
| Ввод-вывод данных в случае, если непосредственно подключенное к процессору устройство воспроизводит данные и позволяет оператору вносить изменения в процессе их обработки |
| Документ | 
| Ввод-вывод данных, носителем которых служит бумага. |
| Линия потока | 
| Указание последовательности связей между символами |
| Соединитель | 
| Указание связи между прерванными линиями потока, связывающими символы |
| Пуск-остановка | 
| Начало, конец, прерывание процесса обработки данных или выполнения программы |
| Комментарий | 
| Связь между элементом схемы и пояснением |
| Межстраничный соединитель | 
| Указание связи между разъединительными частями схем алгоритмов и программ, расположенных на разных листах. |
Продолжение таблицы 1
|
|
|
Размеры символов должны удовлетворять соотношению b=1,5a, рис. 1. На этом же рисунке продемонстрирован пример использования символа «комментарий».
|
Рис. 1 Фрагмент блок-схемы алгоритма
Таблица 2 – Унифицированные структуры
| Следование |
| Полное ветвление |
| Цикл с параметром |
Продолжение таблицы 2
         
 
| Цикл с предусловием | ||
         
  
| Цикл с постусловием |
В зависимости от употребляемых унифицированных структур алгоритмы программных модулей, составляющих программный комплекс, могут быть линейными, разветвляющимися, циклическими и сложными.
Этапы решения задач на ЭВМ.
1. Постановка задачи
2. Анализ и исследование задачи, модели
3. Разработка алгоритма
4. Программирование
5. Тестирование и отладка
6. Анализ результатов решения задачи и уточнение в случае необходимости математической модели с повторным выполнением этапов 2-5
7. Сопровождение программы
В данном учебном пособии на примерах решения конкретных задач рассматриваются этапы решения на ЭВМ с первого по четвертый. На практических занятиях при выполнении заданий необходимо представить этапы решения с первого по шестой. Для иллюстрации этапов решения задач на ЭВМ (1-3) рассмотрим следующую задачу.
Задача 1.
1. Составить алгоритм приближенного вычисления квадратного корня 
с заданной точностью 
методом Ньютона.
2. Очередное значение корня 
вычисляется по формуле 
n=1, 2, …при условии, что задано начальное значение корня 
Первое значение корня будет равно 
, второе – 
и т.д. Корень можно считать вычисленным с заданной точностью , если модуль очередного уточнения корня | 
.
3. Блок-схема алгоритма на рис. 2.
Рис. 2 Алгоритм вычисления квадратного корня методом Ньютона.
Дата добавления: 2016-01-03; просмотров: 18; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!