Будь умным!


У вас вопросы?
У нас ответы:) SamZan.net

тематика Мухаммеда ибн Муса алХорезми lhorithmi жившего в 783 850 гг

Работа добавлена на сайт samzan.net:

Поможем написать учебную работу

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

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 9.11.2024

1. Алгоритмизация вычислительных процессов.

1.1.Основные определения и понятия
1.2.Изобразительные средства алгоритмов

1.3.Базовые канонические структуры алгоритмов

1.1. Основные определения и понятия.

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

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

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

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

Алгоpитм — заранее заданное понятное и точное пpедписание возможному исполнителю совеpшить определенную последовательность действий для получения решения задачи за конечное число шагов.

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

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

"Исполнитель алгоритма"

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

Исполнителя хаpактеpизуют:

  •  сpеда;
  •  элементаpные действия;
  •  cистема команд;
  •  отказы.

Сpеда (или обстановка) — это "место обитания" исполнителя. Напpимеp, для исполнителя Pобота из школьного учебника [1] сpеда — это бесконечное клеточное поле. Стены и закpашенные клетки тоже часть сpеды. А их pасположение и положение самого Pобота задают конкpетное состояние среды.

Система команд. Каждый исполнитель может выполнять команды только из некотоpого стpого заданного списка — системы команд исполнителя. Для каждой команды должны быть заданы условия пpименимости (в каких состояниях сpеды может быть выполнена команда) и описаны pезультаты выполнения команды. Напpимеp, команда Pобота "ввеpх" может быть выполнена, если выше Pобота нет стены. Ее pезультат — смещение Pобота на одну клетку ввеpх.

После вызова команды исполнитель совеpшает соответствующее элементаpное действие.

Отказы исполнителя возникают, если команда вызывается пpи недопустимом для нее состоянии сpеды.

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

В информатике универсальным исполнителем алгоритмов является компьютер.

Понятие алгоритмизации

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

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

Свойства алгоритма:

1) детерминированность – точность указаний, исключающая их произвольное толкование;

2) дискретность – возможность расчленения вычислительного процесса на отдельные элементарные операции, возможность выполнения которых не вызывает сомнений;

3) результативность – прекращение процесса через определенное число шагов с выдачей искомых результатов или сообщения о невозможности продолжения вычислительного процесса;

4) массовость – пригодность алгоритма для решения всех задач заданного класса.

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

Язык программирования – предназначен для реализации программ на ЭВМ.

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

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

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

            А:= В+С;       {А, В, С – переменные}

            К:=  2;    IF T< 0 THEN . . .

Переменная – это объект, который в ходе выполнения программы может менять свое значение.

Свойства переменной:

1) переменная называется неопределенной до тех пор, пока она не получит значение:

а) вводом извне;

б) занесением константы;

в) занесением значения другой, уже ранее определенной переменной;

2) в каждый момент времени переменная может иметь определенное значение, либо быть неопределенной;

3) последующее значение уничтожает (стирает) предыдущее значение. Выбор (чтение) из переменной и ее использование не изменяют значения переменной.

Предметом курса являются методы и средства составления алгоритмов и программ с целью решения задач на ЭВМ.

Для разработки программ используются системы программирования.

Система программирования – средство автоматизации программирования, включающее язык программирования, транслятор этого языка, документацию, а также средства подготовки и выполнения программ.

Транслятор – это программа, которая переводит с одного языка на другой.

Интерпретатор – это программа, которая сразу выполняет переводимые команды.

Компилятор – это программа, которая переводит конструкции алгоритмического языка в машинные коды.

1.2. Изобразительные средства алгоритмов.

 Основными изобразительными средствами алгоритмов являются следующие способы их записи:

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

Словесный – содержание этапов вычислений задается на естественном языке в произвольной форме с требуемой детализацией.

Рассмотрим пример словесной записи алгоритма. Пусть задан массив чисел. Требуется проверить, все ли числа принадлежат заданному интервалу. Интервал задается границами А и В.

п.1  Берем первое число. К п.2.
  
       п.2  Сравниваем: выбранное число принадлежит интервалу; если да, то на п.3, если нет – к п.6.
  
       п.3  Все элементы массива просмотрены? Если да, то на п.5, если нет – то на п.4.
          п.4
 Выбираем следующий элемент. На п.2.         
          п.5
 Печать сообщения: все элементы принадлежат интервалу. На п.7.
          п.6
 Печать сообщения: не все элементы принадлежат интервалу. На п.7.
          п.7
 Конец. 

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

Формульно-словесный – задание инструкций с использованием математических символов и выражений в сочетании со словесными пояснениями.

Например, требуется вычислить площадь треугольника по 3 сторонам.

п.1 – вычислить полупериметр треугольника  p=(a+b+c)/2. К п.2.

п.2 – вычислить  

К п.3.

п.3 – вывести  S , как  искомый результат и прекратить вычисления. 

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

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

Блок-схемы могут быть традиционные и структурированные.

Основные символы блок-схем:

- ввод-вывод;

- процесс  (выполнение операций или группы операций);

- решение (выбор направления);

- модификация (организация цикла);

 

- линии потока

- пуск-останов (начало, конец программы). 

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

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

 Запись алгоритма в виде псевдокода:

 

Языки программирования  - изобразительные средства для непосредственной реализации программы на ЭВМ. Программа – алгоритм, записанный в форме, воспринимаемой ЭВМ.

Каждая машина имеет свой собственный язык (машинный язык) и может выполнять программы только на этом языке. Это последовательность машинных команд. Писать программы на машинном языке очень сложно и утомительно. Для повышения производительности труда программистов применяются искусственные языки программирования. Но при этом требуется перевод программы, написанной на таком языке, на машинный язык. Этот перевод выполняет транслятор. Наиболее часто встречающимся транслятором интерпретирующего типа является транслятор с языка Бейсик, где команды читаются, преобразуются и выполняются сразу. Итогом работы такого транслятора являются требуемые результаты.

Транслятор с Паскаля – компилирующего типа. Текст на исходном языке переводится в текст на машинном языке и получается так называемый объектный модуль. Затем объектный модуль должен быть обработан программой Редактором межпрограммных связей и только после этого программа будет готова к выполнению.

 1.3. Базовые канонические структуры алгоритмов.

 Доказано, что любую программу можно написать с использованием трех управляющих структур:

            - следования, или последовательности операторов;
            - развилки, или условного оператора;
            - повторения, или оператора цикла.

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

1) следование

   A;  B;

        Действия А и В могут быть:
            - отдельным оператором;
            - вызовом с возвратом некоторой процедуры;
            - другой управляющей структурой.

2) развилка

  IF  P  then  A  else  B;

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

  IF  P  then  A ;

3) повторение

цикл – пока

 

 

 

 

While  P do  A  ;

Действие А будет повторяться до тех пор, пока значение предиката будет оставаться истинным. Поэтому в действии А должно изменяться значение переменных, от которых зависит Р. В противном случае произойдет зацикливание. Вычисление предиката производится до начала выполнения действия А, и может случиться так, что действие А не будет выполняться ни разу.

циклдо

  Repeat  A  until  P;

Повторение типа  Repeat until всегда выполняется хотя бы 1 раз. Действие А перестает выполняться, как только предикат становится истинным.

          4) выбор – переключатель case (обобщение развилки), структура, облегчающая программирование без ущерба для ясности программы. Структура выбор полезна в том случае, когда требуется выбрать одну из нескольких альтернатив.  

 

В зависимости от значения  Р выполняется одно из действий А, В, …Z. После чего происходит переход к выполнению следующей управляющей структуры.




1. Региональное промышленное производство эффект кислородного голодания
2. реферат дисертації на здобуття наукового ступеня кандидата медичних наук Київ 2001Дисертацією
3. Курсовая работа- Проектирование малоэтажного здания
4. Основные этапы и особенности проведения аудита денежных средств
5. Тема 3 Анализ формы 3
6. Разрушение экологии
7. По теме- Реорганизация юридических лиц г
8. тематическим ожиданием 075 мин
9. ГУДОК Гудок ежедневная федеральная транспортная газета
10. Изобразительная деятельность дошкольников, ее использование в подготовке к обучению в школе
11. Развитие социального интеллекта младших школьников
12. Избранное. М. Согласие 1999 OCR Бычков М
13. то еще помнит некоторые расценки ктото с трудом припоминает а ктото уже даже смутно помнит как выглядели
14. Римский театр
15. медицинское оснащение
16. Товароведная характеристика колбасных изделий.html
17. тематики и физики Отчет по дисциплине Дискретная математика Тема реферата- Фундаментальные понятия ди
18. Методы управления на предприятии
19. Отчет по лабораторной работе 6 Исследование микроклимата производственных помещений В
20. Перетворювач опір - тривалість імпульсу