Реферат на тему: Алгоритмы

Изложение нового материала – просмотр презентации «Алгоритм и его формальное исполнение», конспектирование:

Здравствуйте меня зовут Степан Александрович, сегодня я проведу у вас урок.

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

Формальное исполнение алгоритма. Из приведённых выше свойств алгоритма вытекает возможность его формального выполнения. Это означает, что алгоритм можно выполнять, не вникая в содержание поставленной задачи, а только строго выполняя последовательность действий, описанных в алгоритме.

Какие виды алгоритмов вы знаете? Приведите примеры?

Алгоритмы бывают трех основных видов, которые и являются базовыми при написании программ.

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

  Второй тип — разветвляющийся алгоритм; такой, в котором выполняются те или иные действия в зависимости от выполнения или невыполнения некоего условия. Пример из жизни — правило перехода улицы по светофору. Если горит красный — стоим, если горит зеленый — идем.

  Третий тип — циклический алгоритм; такой, в котором присутствуют повторяющиеся действия с какой-либо изменяющейся величиной, так называемым параметром. Пример — колка дров. Берем полено — колем топором, берем второе полено и т. д., пока поленья не закончатся, и эта работа нам не надоест.

 Каждый алгоритм создаётся автором (человеком или группой людей) и рассчитан  для выполнения конкретным исполнителем.

Исполнитель алгоритма — это человек или какое-либо устройство(компьютер или робот).

Алгоритм должен быть составлен таким образом, чтобы

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

Свойства алгоритма и его исполнители

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

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

1. Высыпать в емкость содержимое пакетика.

2. Налить в емкость 200 мл горячей воды.

3. Тщательно перемешать.

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

Результативность – получение из исходных данных результата за конечное число шагов.

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

Пример:

Алгоритм покраски забора:

1. Взять краску;
   
2. Покрасить забор.
   

Забор красится до тех пор, пока не закончится краска или забор, т.е. пока не будет выполнена покраска забора до конца.

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

Детерминированность (определённость) – Исполнитель должен выполнять команды алгоритма в строго определенной последовательности.

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

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

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

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

Блок-схемы алгоритмов

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

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

Элементы блок-схем

Выполнение алгоритмов компьютером

Алгоритм, записанный на «понятном» компьютеру языке программирования, называется программой.

На заре компьютерной эры, в 40-50-е годы XX века, программы писались на машинном языке и представляли собой очень длинные последовательности нулей и единиц. Составление и отладка таких программ являлись чрезвычайно трудоемким делом. Программы на машинных языках были машинно-зависимыми, т. е. для каждой ЭВМ необходимо было создавать свою собственную программу, так как в ней в явной форме учитывались аппаратные ресурсы ЭВМ.

Ассемблер. В начале 50-х годов XX века были созданы языки программирования, которые называются ассемблерами. Вместо одних только нулей и единиц программисты теперь могли пользоваться операторами (MOV, ADD, SUB и т. д.), которые были похожи на слова английского языка. Для преобразования текста программы на ассемблере в понятный компьютеру машинный код использовался компилятор, который загружался в оперативную память ЭВМ. Программы на ассемблере были также машинно-зависимыми, т. е. ассемблеры для различных процессоров существенно различались между собой.

Языки программирования высокого уровня. С середины 50-х годов XX века начали создаваться первые языки программирования высокого уровня. Эти языки были машинно-независимыми, так как использовали универсальную компьютерную логику и не были привязаны к типу ЭВМ. Однако для каждого языка и каждого типа ЭВМ должны были быть разработаны собственные компиляторы, которые загружались в оперативную память. Одним из первых языков программирования высокого уровня был созданный в 1964 году известный всем Бейсик (Basic).

С конца 50-х годов XX века начали создаваться языки программирования, которые позволили программистам перейти к структурному программированию. Отличительной чертой этих языков было использование операторов ветвления, выбора и цикла и отказ от хаотического использования оператора goto. Такие языки позволяют легко кодировать основные алгоритмические структуры. Наибольшее влияние на переход к структурному программированию оказал ALGOL (АЛГОЛ), а затем Pascal (назван его создателем Виртом в честь великого физика Блеза Паскаля. Компания Microsoft создала язык QBasic, а в настоящее время язык Basic встроен в интегрированную офисную систему OpenOffice.org.

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

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

• язык Object Pascal был разработан компанией Borland на основе языка Pascal. После создания интегрированной среды разработки система программирования получила название Delphi, а свободно распространяемая версия — Turbo Delphi;

• язык Visual Basic был создан корпорацией Microsoft на основе языка QBasic для разработки приложений с графическим интерфейсом в среде операционной системы Windows;

• язык Gambas был создан по аналогии с языком Visual Basic для разработки приложений с графическим интерфейсом в среде операционной системы Linux.

Java. В 90-е годы XX века в связи с бурным развитием Интернета был создан язык Java, обеспечивающий межплатформенную совместимость. На подключенных к Интернету компьютерах с различными операционными системами (Windows, Linux, Mac OS и др.) могли выполняться одни и те же программы. Исходная программа на языке Java компилируется в промежуточный код, который исполняется на компьютере встроенной в браузер виртуальной машиной.

Платформа .NET. В настоящее время многие программисты выбирают интегрированную систему программирования Visual Studio .NET, разработанную корпорацией Microsoft. Эта система предоставляет возможность создавать приложения в различных системах объектно-ориентированного программирования, в которых для создания программного кода используются объектно-ориентированные языки программирования (Visual Basic .NET, Visual C#, Visual J#, Turbo Delphi и др.).

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

Программы-трансляторы с языков программирования бывают двух типов: интерпретаторы и компиляторы. Интерпретатор — это программа, которая обеспечивает последовательный «перевод» команд программы на машинный язык с одновременным их выполнением. Поэтому при каждом запуске программы на выполнение эта процедура повторяется. Достоинством интерпретаторов является удобство отладки программы (поиска в ней ошибок), так как возможно «пошаговое» ее исполнение, а недостатком — сравнительно малая скорость выполнения.

Компилятор действует иначе, он переводит весь текст программы на машинный язык и сохраняет его в исполняемом файле (обычно с расширением ехе). Затем этот уже готовый к исполнению файл, записанный на машинном языке, можно запускать на выполнение. Достоинством компиляторов является большая скорость выполнения программы, а недостатком большинства из них — трудоемкость отладки, так как невозможно пошаговое выполнение программы.

Системы объектно-ориентированного программирования Visual Basic и Gambas позволяют работать как в режиме интерпретатора, так и в режиме компилятора. На этапе разработки и отладки программы используется режим интерпретатора, а для получения готовой исполняемой программы — режим компилятора.

Система алгоритмического программирования OpenOffice.org Basic позволяет работать только в режиме интерпретатора.