Основы алгоритмизации и программирования. Основы алгоритмизации

• Название: Основы алгоритмизации
• Дата: 14.04.2023
• Размер: 166.5 Kb.
• Имя файла: Основы алгоритмизации и программирования.doc
• Тип: Документы; #1062032

Основы алгоритмизации

Понятие алгоритма и его свойства. Способы записи алгоритмов.

Алгоритм — это точно определенное (формальное) описание способа решения задачи в виде конечной последовательности действий.

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

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

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

• 
  дискретность— представление алгоритма в виде последовательности шагов;
  
• 
  массовость — применимость алгоритма к некоторому множеству исходных данных;
  
• 
  результативность – получение результата за конечное число шагов
  
• 
  однозначность — при повторном применении алгоритма к тем же исходным данным должен быть получен тот же результат.
  

Способы записи алгоритмов:

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

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

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

Преимущество блок-схем – в наглядности алгоритма.

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

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

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

Общая форма Записи алгоритма на псевдокоде

Алгоритм < название >     Начало          < последовательность действий >     Конец

В качестве базовых операций используются:

• 
  операция присваивания вида < переменная > := < выражение >
  
• 
  операция ввода/вывода
  

ввод ( список ввода)
вывод ( список вывода).

Смысл операции присваивания состоит в вычислении результата выражения, стоящего справа от знака “ := “, для конкретных значений входящих в него переменных и присваивании этого результата переменной, стоящей слева от знака “ := “, например:

D := 5

D := D+1

Min := C

При выполнении операции ввода ввод ( A, B, C) переменным из списка ввода A, B и C присваиваются конкретные значения, вводимые с клавиатуры, например:

-5 7 20 {Enter}

В результате в памяти получим:

A = -5, B = 7, C = 20.

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

вывод (A, B, C, 10)

На экране получим:

- 5 7 20 10
Примером псевдокода является алгоритмический язык в русской нотации.

Общая форма Записи алгоритма на алгоритмическом языке:

алг название алгоритма (аргументы и результаты)

дано условия применимости алгоритма

надо цель выполнения алгоритма

нач описание промежуточных величин

| последовательность команд (тело алгоритма)

кон

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

Пример

Пусть заданы длины сторон треугольника. Необходимо вычислить площадь треугольника, используя формулу Герона. Разработку алгоритма полезно начинать с постановки задачи:

Исходные данные:	A, B, C - длины сторон треугольника
Результат:	S - площадь треугольника.
Метод решения:

Запишем алгоритм на псевдокоде, используя дополнительно одну служебную переменную P, уменьшающую время вычислений.
Алгоритм Линейная структура (площадь треугольника)

Начало

ввод (A, B, C)



вывод S

Конец

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

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

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

Классификация алгоритмов

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

	Словесное описание	Алгоритмический язык	Блок-схема
Линейный	алгоритм, в котором все действия выполняются однократно в строго определенной последовательности (базовая структура следование)	действие 1 действие 2 . . . . . . . . . действие n
Ветвящийся	алгоритм, в котором в зависимости от выполнения или невыполнения некоторых условий, выбирается один из нескольких возможных путей вычислительного процесса (базовая структура ветвление). При ветвлении происходит однократный проход по одной из ветвей решения задачи. Признаком ветвящегося алгоритма является наличие операций условного перехода, когда происходит проверка истинности некоторого логического выражения, и, в зависимости от истинности или ложности проверяемого условия, для выполнения выбирается та или иная ветвь алгоритма. Логическое выражение - это выражение, записанное с помощью операций сравнения: <, >, <=, >=, =, <>. При составлении условий можно использовать совокупность связанных между собой условий - составные условия. Для этого используются логические союзы "И" или "ИЛИ", частица "НЕ". .
Структура ветвление существует в 4 вариантах	1) если-то	если условие   то действия все
	2) если-то-иначе	если условие   то действия 1   иначе действия 2 все
	3). выбор	выбор   при условие 1: действия 1   при условие 2: действия 2   . . . . . . . . . . . .   при условие N: действия N все
	4). выбор-иначе	выбор   при условие 1: действия 1   при условие 2: действия 2   . . . . . . . . . . . .   при условие N: действия N   иначе действия N+1 все
Циклический	алгоритм, который при каждом исполнении предписывает многократное выполнение одной и той же последовательности действий – тела цикла(базовая структура цикл).
	цикл пока с предусловием – Серия шагов повторяется до тех пор, пока условие цикла истинно.	нц пока условие   тело цикла (последовательность действий) кц
	цикл "до" с постусловием – серия шагов выполняется до тех пор, пока условие цикла ложно	нц   тело цикла до условие кц
	Цикл «для» (цикл с параметром) – предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне. Цикл "для" используется для ситуаций, когда заранее известно количество повторений некоторых действий.	нц для i от N1 до N2   тело цикла кц

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

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

По способу исполнения выделяют также

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

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

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

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

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


Создание и выполнение программ

Трансляция программ и сопутствующие процессы. Компиляторы и интерпретаторы.

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

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

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

Этапы трансляции:

1. 
   Синтаксический анализ – проверка на соответствие формальным правилам, содержащимся в языке программирования
   
2. 
   Семантический анализ – (семантика – смысловая сторона языка) – поиск ошибок определенного рода, например, не описаны переменные и т.д.
   

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

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

Компилятор переводит в машинный код исходный текст программы целиком. Поэтому достоинство компиляторов — быстродействие и автономность получаемых программ. Компиляторами являются Turbo Pascal, С++, Delphi.

Таким образом, интерпретация в разработке программ – процесс непосредственного покомандного выполнения программы без предварительной компиляции, «на лету». Интерпретация связана с получением переменными значений в процессе работы программы. Режим интерпретации можно использовать для отладки программ на языке высокого уровня.

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

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

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

Средства создания программ

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

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

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

3. Редактор связей (LINKER) - для сборки нескольких откомпилированных модулей в одну программу (исполнимый код).

Исполнимый код — это законченная программа, которую можно запустить на любом компьютере, где установлена операционная система, для которой эта программа создавалась. Как правило, итоговый файл имеет расширение .ЕХЕ или .СОМ.

4. Библиотеки функций — для подключения стандартных функций к программе. Такие функции содержатся в библиотеках - файлах со стандартным расширением .LIB или .TPL, которые поставляются вместе с компилятором

5. Отладчик (DEBUGGER) – инструментальное средство для поиска и исправления ошибок.

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

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

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

Основные этапы компьютерного решения задач

1. 
   Постановка задачи. Основное требование к постановке задачи – достаточное количество информации для решения задачи. Очень часто постановка задачи выполняется не программистом, а некоторым Заказчиком. Программист является Исполнителем заказа. От него требуется добиться от Заказчика полной информации о решаемой задаче.
   
2. 
   Моделирование и формализация задачи.
   

Формализация — это замена реального объекта или процесса его формальным описанием, т. е. его информационной моделью.

Информационная модель — это описание объекта моделирования.

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

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

Моделирование – исследование объектов познания (предметов, процессов или явлений) путем построения и изучения их моделей.

3. 
   Разработка алгоритма - представляет собой реализацию идеи решения задачи.
   

Основные принципы разработки алгоритма:

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

5. 
   Тестирование программы – процесс поиска ошибок в программе. Для этого либо используют специальные средства отладки программ, имеющиеся в интегрированной среде языка программирования, либо временно добавляют в программу команды вывода промежуточных значений.
   
6. 
   Отладка программы – процесс устранения ошибок
   
7. 
   Документирование программы – подготовка документов, сопровождающих программный продукт. Эти документы описывают то, как работает программа и/или то, как её использовать.
   
8. 
   Эксплуатация программы, интерпретация и анализ результатов. В сложных программах может быть недостаточно тестирования для устранения всех ошибок. Очень час-то они обнаруживаются на стадии эксплуатации заказчиком. 
   

Языки программирования
Классификация языков программирования

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



Рис. 1. Общая классификация языков программирования
Процедурные (алгоритмические) языки предназначены для однозначного описания алгоритмов; для задачи процедурные языки требуют в той или иной форме явно записать процедуру ее решения.

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

Широко распространены следующие структурные языки: Паскаль, Си, Ада, ПЛ/1.

Среди операционных известны Фортран, Бейсик, Фокал.

2. Непроцедурные (декларативные) языкипрограммирования ориентированы не на разработку алгоритма решения задачи, а на систематическое и формализованное описание задачи с тем, чтобы решение следовало из составленного описания.

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

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

Примеры функциональных языков: Haskell –чистый функциональный, LISP (Джон МакКарти), APL — язык программирования, оптимизированный для работы с массивами.

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

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

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

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

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

Примером такого языка может служить язык программирования визуального общения Object Pascal. К наиболее современным объектно-ориентированным языкам программирования относятся C++ и Java.

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

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

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

Семантика языка программирования – это совокупность значений (смысл) всех конструкций языка.

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


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

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

Если язык программирования ориентирован на конкретный тип процессора и учитывает его особенности,то он называется языком программирования низкого уровня (операторы языка близки к машинному коду и ориентированы на конкретные команды процессора).

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

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

Языки программирования высокого уровня значительно ближе и понятнее человеку, нежели компьютеру. Языки программирования высокого уровня (ЯПВУ) являются машинно-независимыми языками.

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

Поколения языков программирования

1-поколение: языки, созданные в нач. 50-х годов (первый язык ассемблера: одна инструкция – одна строка)

2-е поколение: кон.50-нач 60-х гг. – разработан символический ассемблер, появилось понятие переменной (полноценный язык программирования).

3-е поколение: 60-е гг. – появились универсальные языки высокого уровня, которые применяются и по сей день. (Фортран, Алгол, COBOL).

4-е поколение: с нач.70-х гг. – по сей день: языки высокого уровня, ориентированные на специализированные области применения и предназначенные для реализации крупных проектов (Pascal, C++, Perl)

5-е поколение: сер. 90-х гг.: системы автоматич. создания прикладных программ с помощью визуальных средств разработки, без знания программирования. (Си Шарп, XML)