Logo GenDocs.ru


Поиск по сайту:  


Лекции по информатике - файл 1.doc


Лекции по информатике
скачать (1270.5 kb.)

Доступные файлы (1):

1.doc1271kb.16.11.2011 02:47скачать

содержание

1.doc

1   2   3   4   5   6   7   8   9   ...   15
Реклама MarketGid:
^

Понятие алгоритма. Свойства и классы алгоритмов. Формы представления алгоритмов



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


Алгоритм — точное и понятное предписание исполнителю совершить последовательность действий, направленных на решение поставленной задачи.


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

^ Основные свойства алгоритмов следующие:

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

Дискpетность (прерывность, раздельность) — т.е. алгоpитм должен пpедставлять пpоцесс pешения задачи как последовательное выполнение пpостых (или pанее оп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. Реального времени – результат должен быть получен к определенному времени.

Примеры алгоритмов:





m

n




30

18




12

18




12

6

d=

6

6


1. Алгоритм Эвклида

d=НОД(m,n)


Алгоритм:

шаг 1: Ввести два целых положительных числа.

шаг 2: Если числа равны, то взять в качестве ответа первое, и на этом закончить

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

шаг 3: Определить большее из двух.

шаг 4: Заменить большее число на разность

большего и меньшего чисел.

шаг 5: Перейти к шагу 2.


2. Алгоритм решения линейного уравнения

ax+b=0


  1. x=-b/a, a0;

  2. a=0 и b0 – решений нет;

  3. a=0 и b=0 – решений бесконечное множество


шаг 1: Ввести a и b.

шаг 2: Если a=0, перейти к шагу 4.

шаг 3: Вычислить x=-b/a и закончить выполнение алгоритма.

шаг 4: Если b=0, перейти к шагу 6.

шаг 5: Решений нет. Закончить выполнение алгоритма.

шаг 6: Любое x – решение. Закончить выполнение алгоритма.

Формы представления алгоритмов:

Словесный способ не имеет широкого распространения по следующим причинам:

* такие описания строго не формализуемы;

* страдают многословностью записей;

* допускают неоднозначность толкования отдельных предписаний.

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

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




Блок Пуск-останов. Начало, конец алгоритма, вход и выход в подпрограмму

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

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

Блок Документ. Вывод результатов на печать

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

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

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

Рассмотрим базовые конструкции:

Псевдокод

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

начало

ввод a, b

если a=0, то если b=0 то вывод

«Любое х решение»

иначе вывод

«Решений нет»

все-если

иначе начало

x=-b/a

вывод х

конец

все-если

конец



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

В группу языков низкого уровня входят машинные языки и языки символического кодирования: (Автокод, Ассемблер).

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

Машинно-ориентированные языки – это языки, наборы операторов и изобразительные средства которых существенно зависят от особенностей ЭВМ (внутреннего языка, структуры памяти и т.д.).

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

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

Среди процедурных языков выделяют в свою очередь структурные и операционные языки. В структурных языках одним оператором записываются целые алгоритмические структуры: ветвления, циклы и т.д. В операционных языках для этого используются несколько операций. Широко распространены следующие структурные языки: Паскаль, Си, Ада, ПЛ/1. Среди операционных известны Фортран, Бейсик, Фокал.

К непроцедурному программированию относятся функциональные и логические языки.

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

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

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

Языки описания сценариев, такие как Perl, Python, Rexx, Tcl и языки оболочек UNIX, предполагают стиль программирования, весьма отличный от характерного для языков системного уровня. Они предназначаются не для написания приложения с нуля, а для комбинирования компонентов, набор которых создается заранее при помощи других языков. Развитие и рост популярности Internet также способствовали распространению языков описания сценариев. Так, для написания сценариев широко употребляется язык Perl, а среди разработчиков Web-страниц популярен JavaScript.


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

1   2   3   4   5   6   7   8   9   ...   15

Реклама:





Скачать файл (1270.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru