Лекция по "Информатике"

алгоритм алгоритм Евклида;

начало 

пока первое число не равно второму

повторять

начало 

если числа равны

то стоп все;

иначе определить большее из двух чисел;

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

конец;

взять первое число в качестве ответа

конец

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

Языки программирования

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

Однако на практике в качестве исполнителей алгоритмов используются специальные автоматы — электронные  вычислительные машины (ЭВМ). Поэтому  алгоритм, предназначенный для исполнения на ЭВМ, должен быть записан на языке, “понятном” ЭВМ. И здесь на первый план выдвигается необходимость  точной записи команд, не оставляющей  места для произвольного толкования их исполнителем. Следовательно, язык для записи алгоритма должен быть формализован. Такой язык принято  называть языком программирования, а запись алгоритма на этом языке — программой для ЭВМ.

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

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

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

 

 

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

Универсальные языки высокого уровня обеспечивают создание различных программ (задач), например Алгол, Си, ПЛ/1 и т.д..

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

Объектно-ориентированные  языки четвертого поколения (4GL — forth-generation language) и программирование основаны на создании модели системы, как совокупности объектов и использует следующие базовые понятия: класс, объект, событие, свойства объекта, метод обработки. Первым языком программирования этой группы был - Симула-67. В настоящее время к этим языкам относятся - С++, Visual Basic, Java Script и динамический HTML и другие современные языки программирования.

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

Например, интересна эволюция языка программирования BASIC. Он был  задуман как универсальный язык для начинающих (по аналогии с BASIC ENGLISH, — подмножеством английского  языка, выделенным для обучения иностранцев). Первые версии (или “диалекты”) этого  языка содержали небольшое количество самых необходимых команд и предусматривали  только режим интерпретации. Однако современные варианты языка BASIC не только не уступают по возможностям многим “грандам” (типа С), но иногда и превосходят  их. Например, Visual Basic используется в  суперсовременных системах, основанных на так называемой технологии “клиент-сервер”. Одновременно BASIC стал своеобразным “эсперанто”  в мире информационной технологии. На этом языке часто пишутся примеры  программ или их фрагментов в книгах, статьях, инструкциях к программным  продуктам.

Фирма Microsoft использует Visual Basic для расширения функций своих  программных продуктов. Уже в  пакете Microsoft Office для Windows 3-х пользователям  и программистам предлагались диалекты Word Basic и Access Basic, а ныне в Microsoft Office предусмотрен универсальный язык Visual Basic for Applications (VBA — Visual Basic для приложений). Ранее  этот язык использовался только в Excel 5.0. С помощью VBA можно создавать  собственные программные модули, собственные интерфейсы для офисных  приложений Word, Excel, Access.

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

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

Программа-интерпретатор всегда работает совместно с исходным текстом. Она разбирает каждую инструкцию исходного текста (интерпретирует ее) и немедленно исполняет (т. е. файл на машинном языке не создается). Программа в режиме интерпретации работает гораздо медленнее, чем такая же программа в машинном коде. Это связано с тем, что каждую инструкцию приходится разбирать во время выполнения (а не заранее, как при компиляции). Многие инструкции в программе выполняются многократно, — и при каждом выполнении интерпретируются заново. Поэтому всюду, где возможно, стремятся заменить режим интерпретации режимом компиляции. Правда, интерпретация имеет и свои преимущества: с ее помощью проще отлаживать программу. Иногда пользуются режимом “псевдокомпиляции”: ускоряют интерпретацию за счет предварительного запоминания тех или иных элементов разобранных команд в памяти машины.

Современное программирование существенно отличается от технологии разработки программ для старых ЭВМ. Среди относительно новых особенностей и направлений этой технологии:

• применение объектно-ориентированных языков;
• визуальное программирование (т. е. сборка экранной формы с помощью мыши из готовых “полуфабрикатов ” - объектов);
• быстрая разработка приложений (RAD — Rapid Applications Development);
• программирование с использованием функций API Windows (Applications Programming Interface — интерфейс прикладного программирования);
• базы данных и многопользовательские приложения (т. е. приложения, с которыми одновременно работает несколько пользователей) и многие другие.

Подробно языки программирования не будут рассмотрены в данном курсе.

СТРУКТУРЫ АЛГОРИТМОВ

Несмотря на существование  множества языков программирования, все они, как правило, содержат

• средства описания данных,
• арифметические операторы (подобные с = а+Ь),
• средства управления
• средства организации циклов,
• средства ввода и вывода информации.

Многие языки пользуются похожими принципами организации программ, но —разным синтаксисом.

Алгоритмы строятся из некоторых  жестких структур, состоящих из отдельных  базовых элементов.

Простые команды

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

Значение переменной величины может быть изменено с помощью  команды присваивания. Например, команда x:=1 означает, что переменной x присваивается значение 1, а команда y:=y+1 — что переменной y присваивается значение, которое на 1 больше ее прежнего значения.

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

ввод(x, у)

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

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

Составные команды

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

Команда следования

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

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

Команда ветвления

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

Действия, указанные после  служебных слов то и иначе, могут быть простыми или составными командами. При исполнении команды ветвления выполняется только одно из действий: если условие соблюдено, то выполняется действие 1, в противном случае — действие 2.

В том случае, когда условие  соблюдено, продолжение исполнения алгоритма происходит по стрелке  “+”, в противном случае — по стрелке “—”.

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

Команда повторения (цикл)

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

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

Рассмотрим два типа команды  повторения.

 

+ --

 

+

 

Схема цикла с  предусловием

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

 

- +

Схема цикла с  постусловием

 

Команда повторения с постусловием выполняется аналогично, только условие проверяется после выполнения команды, а повторение выполнения команды происходит в том случае, когда условие не соблюдено, т. е. повторение производится до соблюдения условия (поэтому этот тип цикла называют также циклом “до”).

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

СТРУКТУРНОЕ ПРОЕКТИРОВАНИЕ

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

Алгоритмы большой сложности  обычно представляются с помощью  схем двух видов: обобщенной и детальной.

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

Детальная схема описывает содержание каждого элемента обобщенной схемы с использованием управляющих структур блок-схемы или псевдокода.

Существует несколько  методов проектирования:

• нисходящее (сверху-вниз)
• восходящее (снизу-вверх)
• смешанное, использующее два предыдущих метода.

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

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