Тема урока: «Алгоритм и его формальное исполнение»

Этапы урока

Содержание этапа

Техника организации

Организация

Подготовка учащихся к уроку, проверка присутствующих на уроке

Мотивация

Объяснение темы, цели, плана проведения занятий

Формирование новых понятий, сравнительная характеристика

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 позволяет работать только в режиме интерпретатора.

Слайд 2

Слайд 3

Слайд 4

Слайд 5

Слайд 6

Слайд 7

Слайд 8

Слайд 9

Слайд 10

Слайд 11

Слайд 12

Слайд 13

Слайд 14

Слайд 15

Слайд 16

Подведение итогов

Домашнее задание

Чему вы научились за сегодняшний урок?

§ 4.1, стр.105-112, составить блок-схему решения квадратного уравнения №4.1, стр.108.

Слайд 17