73730

Основні поняття алгоритмізації та програмування

Лекция

Информатика, кибернетика и программирование

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

Украинкский

2014-12-19

543.5 KB

3 чел.

НАЦІОНАЛЬНА АКАДЕМІЯ СЛУЖБИ БЕЗПЕКИ УКРАЇНИ 

Навчально-науковий інститут інформаційної безпеки

Кафедра інформаційних систем і технологій

В.Д. КОЗЮРА

ОСНОВНІ ПОНЯТТЯ АЛГОРИТМІЗАЦІЇ ТА ПРОГРАМУВАННЯ

(Лекція № 1)

Спеціальність 6.1701.03 – Управління інформаційною безпекою

Модуль 1. Основи алгоритмізації та програмування

Тема № 1. Етапи вирішення завдань на ЕОМ. Основи алгоритмізації

(Час – 2 години)

Форма навчання: денна

Лекція розглянута і схвалена на засіданні кафедри

Протокол № ___ від «___» ___________ 2011 року

Київ – 2011


Тема лекц
ії:

«Основні поняття алгоритмізації та програмування»

ПЛАН

Вступ

  1.  Предмет, мета та завдання дисципліни
  2.  Етапи вирішення завдань на ЕОМ
  3.  Алгоритми, їх властивості та засоби подання

Висновки

ЛІТЕРАТУРА

  1.  Ставровский А.Б. Первые шаги в программировании. Самоучитель. – М.: «Вильямс», 2003. с. 16-26.
  2.  Иванова Г.С. Основы программирования: Учебник для вузов. - 2-е изд., перераб. и доп. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. с. 12-24.


ВВЕДЕНИЕ

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

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

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

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

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


1. ПРЕДМЕТ, МЕТА ТА ЗАВДАННЯ ДИСЦИПЛІНИ

Навчальна дисципліна «Технології програмування» є нормативною, яка відноситься до фундаментальних, професійно-орієнтованих дисциплін при підготовці фахівців за спеціальністю 6.170103 «Управління інформаційною безпекою».

Навчальна дисципліна «Технології програмування» передбачає ознайомлення з теоретичними та практичними аспектами автоматизації обробки даних шляхом реалізації алгоритмів їх обробки у вигляді комп’ютерних програм, які розроблюються з використанням сучасних методів і засобів (структурних і об’єктно-орієнтованих технологій програмування). Вона забезпечує підготовку студентів до використання сучасних засобів обчислювальної техніки як при вивченні інших дисциплін, так і у своїй майбутній професійній діяльності.

Предметом навчальної дисципліни є:

  •  алгоритми вирішення прикладних завдань;
  •  мова та середовище програмування Delphi;
  •  методи та засоби сучасних технології програмування (структурного та об’єктно-орієнтованого).

Мета викладання дисципліни «Технології програмування» – вивчення теоретичних основ сучасних технологій програмування і придбання практичних навичок їх реалізації.

Завдання вивчення дисципліни:

  •  формування систематизованого уявлення про мови програмування, концепції та моделі, що покладені в основу сучасних технологій програмування;
  •  вивчення основ проектування програмного забезпечення, використання сучасних технологій структурного і об'єктно-орієнтованого програмування;
  •  придбання навичок розробки алгоритмів і програм, тестування програмних продуктів, які функціонують під управлінням сучасних операційних систем;
  •  отримання практичної підготовки при виборі та застосуванні технологій програмування для завдань автоматизації обробки інформації;

В результаті вивчення дисципліни студенти повинні:

Знати:

  •  основні етапи технологічного циклу розробки програмної системи та сфери застосування технологій проектування і розробки програмних продуктів;
  •  методики програмування – структурне і об'єктно-орієнтоване програмування;
  •  технологічні засоби розробки програмного забезпечення: інструментальне  ередовище розробки, засоби підтримки проекту, відладчики;
  •  методи налагодження, тестування і документування програм.

Вміти:

  •  використовувати інструментальні засоби програмування;
  •  проектувати програмне забезпечення;
  •  розробити і створити програму середньої складності із застосуванням принципів структурного і об'єктно-орієнтованого програмування;
  •  виконувати налагодження і тестування програм на стадії розробки.

Тематичний план вивчення дисципліни наведений у табл. 1.1.

Таблица 1.1.

Назва теми

Кількість годин

В

Л

ЛЗ

ПЗ

СР

Семестр 3

Модуль 1. Основи алгоритмізації та програмування

1

Тема № 1. Етапи вирішення завдань на ЕОМ. Основи алгоритмізації

8

2

2

-

4

2

Тема № 2. Огляд сучасних технологій програмування

8

2

-

2

4

3

Тема № 3. Основи мові  програмування Delphi

20

4

4

4

8

Модуль 2. Технологія структурного програмування

4

Тема № 4. Програмування даних статичної структури

16

2

4

2

8

5

Тема № 5. Засоби роботи з файлами та даними динамічної структури

20

2

4

4

10

Модуль 3. Технологія об’єктно-орієнтованого програмування

6

Тема № 6. Програмування в середовищі Delphi

22

4

4

-

14

7

Тема № 7. Тестування та налагодження програм

14

2

2

4

6

 

Усього годин

108

18

20

16

54

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

Підсумковий контроль: залік.

При вивченні дисципліни «Технології програмування» може бути використана наступна література.

Основна

  1.  Архангельский А.Я. Программирование в Delphi 7. – М.: ООО «Бином-Пресс», 2003. – 1152 с.
  2.  Бобровский С.И. Delphi 7: Учебный курс. – СПб.: Питер, 2004. – 736 с.
  3.  Вирт Н. Алгоритмы и структуры данных: Пер. с англ. – М.: Мир, 1989. – 360 с.
  4.  Гагарина Л.Г., Кокорева Е.В., Виснадул Б.Д. Технология разработки программного обеспечения: учебное пособие / Под ред. Л.Г. Гагариной. – М: ИД «ФОРУМ»: ИНФРА-М, 2008. – 400 с.
  5.  Галисеев Г.В. Программирование в среде Delphi 7. Самоучитель. – М.: «Вильямс», 2004. – 288 с.
  6.  Голицина О.Л., Партыка Т.Л., Попов И.И. Языки программирования: Учебное пособие. – М.: ФОРУМ: ИНФРА-М, 2008. – 400 с.
  7.  Голицина О.Л., Попов И.И. Основы алгоритмизации и программирования: Учебное пособие. 3-е изд., испр. и доп. – М.: ФОРУМ, 2008. – 432 с.
  8.  Жоголев Е.А. Технология программирования. – М.: Научный мир, 2004. – 216 с.
  9.  Культин Н.Б. Основы программирования в Delphi 7. – СПб.: БХВ-Петербург, 2003. – 608 с.
  10.  Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0. – 8-е изд. – К.: ВЕК+, СПб.: КОРОНА принт, 2004. – 464 с.
  11.  Ставровский А.Б. Первые шаги в программировании. Самоучитель. – М.: Издательский дом «Вильямс», 2003. – 368 с.
  12.  Фленов М.Е. Библия Delphi: – 3-е изд., перераб. и доп. – СПб.: БХВ-Петербург, 2011. – 688 с.

Додаткова

  1.  Бакнелл Дж.М. Фундаментальные алгоритмы и структуры данных в Delphi: Пер. с англ. – СПб.: ООО»ДиаСофтЮП», 2003. – 560 с.
  2.  Вирт Н. Алгоритмы + структуры данных = программы: Пер. с англ. – М.: Мир, 1985. – 406 с.
  3.  Дарахвелидзе П.Г., Марков Е.П. Программирование в Delphi 7. – СПб.: БХВ-Петербург, 2003. – 784 с.
  4.  Иванова Г.С. Основы программирования: Учебник для вузов. - 2-е изд., перераб. и доп. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. — 416 с.
  5.  Иванова Г.С. Технология программирования: Учебник для вузов. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. – 320 с.
  6.  Красиков И.В., Красикова И.Е. Алгоритмы. Просто как дважды два. – М.: Эксмо, 2007. – 256 с.
  7.  Культин Н.Б. Delphi в задачах и примерах. – СПб.: БХВ-Петербург, 2003. – 288 с.
  8.  Макконнелл Дж. Основы современных алгоритмов: Пер. с англ. 2-е доп. изд. – М.: Техносфера, 2004. – 368с.
  9.  Макконнелл С. Совершенный код. Мастер-класс: Пер. с англ. – М.: Издательско-торговый дом «Русская Редакция»; СПб.: Питер, 2005. – 896 с.
  10.  Павловская Т.А. Паскаль. Программирование на язіке вісокого уровня: Учебник для вузов. – СПб.: Питер, 2007. – 393 с.
  11.  Парижский С.М. Delphi. Учимся на примерах/ Под ред. Ю.А. Шпака. – К.: "МК-Пресс", 2005. – 216с.
  12.  Парижский С.M. Delphi. Tолько практика/ Под ред. Ю.А. Шпака. – K.: "МК-Пресс", 2005. – 208c.
  13.  Пестриков В.М., Маслобоев А.Н. Delphi на примерах. – СПб.: БХВ-Петербург. 2005. – 496 с.
  14.  Попов В.Б. Паскаль и Делфи. Самоучитель. – СПб.: Питер, 2004. – 544 с.
  15.  Семакин И.Г., Шестаков А.П. Основы программирования: Учебник. — М.: Мастерство, 2002. – 432 с.
  16.  Ставровский А.Б. Первые шаги в программировании. Самоучитель. – М.: «Вильямс», 2003.
  17.  Сухарев М.В. Основы Delphi. Профессиональный подход. – СПб.: Наука и Техника, 2004. – 600 с.
  18.  Фаронов В.В. Delphi 2005. Язык, среда, разработка приложений. – СПб.: Питер, 2005. – 560 с.
  19.  Хомоненко А.Д. и др. Delphi 7. Наиболее полное руководство/Под общ. ред. А.Д. Хомоненко. – СПб.: БХВ-Петербург, 2008. – 1216 с.
  20.  Шелест В.Д. Программирование. – СПб.: БХВ-Петербург, 2002. – 592 с.
  21.  Шпак Ю.А. Delphi 7 на примерах/ Под ред. Ю.С. Ковтанюка – К.: Издательство Юниор, 2003. – 384 с.

Інші джерела

Електронні видання (зберігаються на сервері комп'ютерного класу)

  1.  Иллюстрированный самоучитель по практике программирования.
  2.  Практика программирования.
  3.  Иллюстрированный самоучитель по Delphi 7 для начинающих.
  4.  Иллюстрированный самоучитель по Delphi 7 для профессионалов.
  5.  Иллюстрированный самоучитель по Турбо Паскалю.


2. ЕТАПИ ВИРІШЕННЯ ЗАВДАНЬ НА ЕОМ

2.1. Основные этапы процесса разработки программы

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

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

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

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

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

В процессе разработки программ можно выделить следующие этапы (рис. 2.1):

  1.  постановка задачи – определение требований к программному продукту;
  2.  анализ – осуществление формальной постановки задачи и определение методов ее решения;
  3.  проектирование – разработка структуры программного продукта, выбор структур для хранения данных, построение и оценка алгоритмов подпрограмм и определение особенностей взаимодействия программы с вычислительной средой (другими программами, операционной системой и техническими средствами);
  4.  реализация – составление программы на выбранном языке программирования, ее тестирование и отладка.
  5.  модификация – выпуск новых версий программного продукта.

Рис. 2.1. Основные этапы процесса разработки программы

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

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

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

В результате согласования между заказчиком и исполнителем всех перечисленных вопросов составляют техническое задание в соответствии с ДСТУ 19.201-78, которое служит основанием для дальнейшей работы.

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

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

Пример 1. Разработать программу, которая по заданным длинам сторон прямоугольника определяет его площадь.

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

Математические абстракции для представления исходных данных – некие изменяемые значения – переменные. 

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

Модель задачи можно представить в виде:

S = a × b,

где S – площадь; a, b – длины сторон.

Результат получают перемножением аргументов.

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

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

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

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

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

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

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

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

Различают последовательности действий (вычислений) линейной, разветвленной и циклической структуры.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Язык программирования – формальный язык связи человека с ЭВМ, предназначенный для описания данных (информации) и алгоритмов (программ) их обработки на ЭВМ.

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

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

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

  •  обозримость;
  •  удобство в использовании;
  •  эффективная реализация.

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

  •  машинные языки – языки программирования, воспринимаемые аппаратной частью компьютера (машинные коды). К подобным языкам относится система команд любой ЭВМ;
  •  машинно-ориентированные языки – языки программирования, отражающие структуру конкретного типа компьютера (автокоды, ассемблеры);
  •  процедурно-ориентированные языки – языки программирования высокого уровня, не зависящие от архитектуры компьютера и предназначенные для описания алгоритмов решения определенного класса задач (Фортран, Кобол, Алгол, Паскаль, Ада, Бейсик, С, С++ и др.);
  •  проблемно-ориентированные языки – языки программирования, ориентированные на решение задач в определенной предметной области (Лисп и Пролог – системы искусственного интеллекта, экспертные системы, Симкскрипт и Симула – моделирование параллельно протекающих во времени и взаимодействующих друг с другом процессов, и др.);
  •  интегрированные системы программирования (Borland Delphi, Borland С++ Builder, Visual Basic for Windows и др.).

На рис. 2.3 представлена схема процесса подготовки программы к выполнению.

Рис. 2.3. Схема процесса подготовки программы к выполнению

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

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

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

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

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

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

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

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

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

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

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

Системы программирования включают:

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

Инструментальная среда пользователя представлена специальными средствами, встроенными в пакеты прикладных программ, такими, как:

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

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

Рис. 2.4. Процесс выполнения программы (а) и ее отладки с помощью отладчика (б)

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

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

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

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

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

Причинами выпуска новых версий являются:

  •  необходимость исправления ошибок, выявленных в процессе длительной эксплуатации;
  •  необходимость совершенствования, например, улучшения интерфейса или расширения состава выполняемых функций;
  •  изменение среды (появление новых технических средств и/или программных продуктов).

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

2.2. История развития языков и систем программирования

Программирование для компьютеров появилось в ХІХ веке, когда графиня Ада Лавлейс (1815-1852), дочь известного английского поэта Байрона, разрабатывала программы для аналитической машины Чарльза Бэббиджа.

История развития компьютеров показывает, что аппаратные средства возникли несколько раньше, чем появились языки программирования. Первые компьютеры программировались вручную, путем установки переключателей и перемычек на специальных стендах, т.е. «команды» физически объединялись в программу. В частности на первой в мире ЭВМ ENIAC (США), запущенной в эксплуатацию в 1945 г., для ввода команд использовалось более 6000 тумблеров и переключателей. На подготовку машины к вычислению одной баллистической таблицы уходило два дня работы.

С изобретением оперативной памяти машинные программы, представленные в двоичном коде, стали записываться в нее. Но отдельные «шаги» программы приходилось вводить с помощью двоичного, а позднее 16-ричного или 8-ричного кода.

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

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

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

В 1951 г. Грейс Хоппер со своей группой (компания «Ремингтон Рэнд») занялась разработкой системы, которая могла бы быстро выполнять работу, связанную с организацией подпрограмм, выделением памяти компьютера, преобразованием команд ассемблера в машинные. Хоппер назвала эту транслирующую программу компилятором.

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

Наиболее активный период разработки языков и систем программирования приходится на 60-е годы XX века. За это десятилетие в мире родилось более  тысячи разнообразных языков, как универсальных, так и специализированных, но выжили и доросли до XXI века немногие, в том числе Fotran, Basic, Algol, Cobol, Simula, Lisp и их потомки. Родословная основных языков программирования приведена на рис. 2.5.

Рис. 2.5. Родословная основных высокоуровневых языков программирования

Фортран (FORmula TRANslatorпереводчик формул) был разработан в середине 50-х годов программистами фирмы IBM под руководством Джона Бэкуса. Его основное предназначение – выполнение естественнонаучных и математических расчетов. Сильной стороной языка всегда оставалась высокая степень переносимости исходного кода между различными платформами (как существующими, так и будущими), обеспечивающая долговечность программ. Фортран неизменно опережал своих конкурентов и по быстродействию программ, и по их компактности благодаря высокой эффективности исполняемого кода. Это объясняется как многолетней отработкой алгоритмов компилятора, так и применением более простых конструкций языка.

Гордостью Фортрана всегда была и остается богатая коллекция самых разнообразных библиотек (прежде всего, математических). Одна из наиболее популярных — IMSL фирмы Visual Numerics — включает свыше тысячи процедур математической и статистической обработки данных и фактически является стандартом на самых различных компьютерных платформах.

Кобол (CОmmon Business Oriented Languageобщий язык, ориентированный на деловые задачи) был разработан в 1960 г. совместными усилиями правительства США и производителей компьютеров. Основной целью было создание языка, который могли бы легко понимать деловые люди, профессионально не связанные с программированием. Структура и словарь этого языка весьма близки к обычному английскому языку. Вся программа делится на четыре различные секции, каждая из которых содержит определенный тип описаний (назначение программы; характеристики компьютера, для которого она написана; тип используемых данных; выполняемые команды). Синтаксис Кобола моделирует синтаксис предложений английского языка.

Алгол (ALGOrithmic Languageалгоритмический язык) — язык программирования высокого уровня, для которого существуют три последовательно сменявших друг друга версии: Алгол-58, Алгол-60, Алгол-68. Язык предназначен для записи алгоритмов, которые строятся в виде последовательности процедур, применяемых для решения поставленной задачи.

Алгол подразделяется на три уровня:

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

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

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

На основе накопленного опыта в середине 60-х годов специалистами фирма IBM создается ПЛ/1 (Programming Language Oneязык программирования, первый) — универсальный машинно-независимый язык программирования достаточно высокого уровня с широким набором средств для эффективного описания вычислительных процессов, задач обработки данных, обработки символьной информации, процессов моделирования, решения логических задач, исследования логических схем, решения задач в реальном масштабе времени и даже для разработки систем математического обеспечения. Важная особенность языка — его модульность, т.е. возможность образовывать специализированные (для конкретной области применения) подмножества языка различной сложности путем отбрасывания ненужных для данных приложений средств. Эта особенность облегчила использование языка и повысила эффективность работы соответствующих трансляторов.

В 60-70-е годы появляются проблемно-ориентированные языки программирования высокого уровня.

Язык Лисп (LISt Processing, — обработка списков) широко применяется для исследований в области искусственного интеллекта. Отличительной особенностью языка является использование цепной адресации: каждый член списка содержит информацию о самом себе в виде непосредственного значения или адреса и адрес следующего члена списка. Язык удобен для обработки информации, содержание и объем которой заранее не определены, и для реализации рекурсивных процедур.

Пролог (PROgramming in LOGicпрограммирование в логике) – язык программирования высокого уровня непроцедурного типа, разработанный в 1972 г. Аланом Колмари из университета в Лумини (Марсель). При работе с ним программистам не требуется расписывать шаг за шагом процедуры — достаточно просто определить множество фактов и установить отношения между ними, например, что «Телега» и «Автомобиль», квалифицируются как нечто, называемое «Средство_Передвижения», и что это «Средство_Передвижения» имеет что-то, что называется «Колеса». С помощью этих соотношений процедуры, уже встроенные в язык, получают логический вывод о том, что, скажем, «Автомобиль» имеет «Колеса». Эта особенность делает Пролог очень удобным для написания экспертных систем.

Форт (FORTHчетвертый) – высокоуровневый язык программирования четвертого поколения. Идея создания языка принадлежит Чарльзу Муру, разработавшего его в конце 60-х - начале 70-х годов как персональное средство повышения производительности труда. Форт стал более широко применяться в задачах управления после того, как Мур использовал его для реализации программы, предназначенной для управления радиотелескопом Аризонской обсерватории. Программы на языке Форт предельно кратки и занимают совсем немного места в памяти. Несколько ключевых слов этого языка — просто знаки препинания, поэтому программы работают очень быстро, но одновременно это затрудняет их чтение и сопровождение.

В конце 70-х – начале 80-х годов была предпринята очередная попытка создания универсального языка программирования. По инициативе и при содействии Министерства обороны США в 1979 г. специалистами фирмы CII Honeywell Bull под руководством Ж.Ишбиа создается язык Ада (Ada), предназначенный, прежде всего, для разработки больших программных систем реального времени для встроенных и управляющих ЭВМ. В 1983 г. он был принят как стандарт ANSI.

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

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

Одним из первых таких языков явился Бейсик (Beginners All-Purpose Symbolic Instruction Codeуниверсальный символический код для начинающих) — язык программирования, ориентированный на диалоговую работу. Он был разработан в середине 60-х годов профессорами Дартмутского колледжа Джоном Кемени и Томасом Курцом. Бейсик сравнительно несложен для изучения и подходит для разработки коротких и простых программ. В 70-х годах он завоевал всеобщее признание вследствие своей компактности и пригодности для первых персональных компьютеров с их ограниченным объемом памяти.

Язык Паскаль (Pascal), получившим свое название в честь французского математика 17 века Блеза Паскаля, был разработан швейцарским профессором Никлаусом Виртом, одной из принципиальных целей которого было «разработать язык, пригодный для изучения программирования как систематической дисциплины, которая исходит из определенных фундаментальных понятий, ясно и естественно отраженных в языке». Описание языка было опубликовано в ноябре 1970 г. в техническом отчете Швейцарского федерального технологического института ETH (Eidgenoessische Technische Hochschule). В самом начале 1971 г. отчет был перепечатан в первом номере журнала Acta Informatica и стал доступен широкому кругу программистов.

В основе Паскаля лежит язык Алгола 60, а также его разновидности, созданные в 60-х годах: Алгол W и Алгол 68. По построению язык Паскаль проще своих предшественников и позволяет осваивать структурное программирование. С середины 70-х годов он стал основным среди языков, применяемых в обучении.

Огромную роль в массовом распространении Паскаля сыграла компания Borland International, создавшая в 1983 г. Turbo-среду разработки (автором Turbo Pascal является датчанин Андерс Хейльсберг). Это был значительный шаг вперед в облегчении процесса программирования. Удобство визуальных средств в сочетании с тесной интеграцией инструментария стали для сотен тысяч программистов большим подспорьем.

Turbo Pascal видоизменялся едва ли не с каждой версией среды разработки: в версии 3.0 появилась встроенная графика, в версии 4.0 — модули, в версии 5.5 — средства объектно-ориентированного программирования. Начиная с версии Turbo Pascal 7.0 (1993 г.) язык был переименован в Borland Pascal. На его основе был разработан язык Object Pascal, вначале реализованный в системе программирования Turbo Vision, а затем в системе объектно-ориентированного визуального программирования Delphi.

Система Borland Delphi используется для профессиональной разработки реальных программ. Она является одной из наиболее популярных систем, реализующих так называемую быструю разработку приложений (программ), или RAD (Rapid Application Development). Такие системы содержат обширные библиотеки подпрограмм, которые обеспечивают отображение на экране (визуализацию) результатов работы программы и решение других задач, значительно повышая эффективность работы программистов.

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

Основой архитектуры Delphi является объектно-ориентированная компонентная модель, реализованная в виде библиотеки компонент VCL (Visual Components Library), которая является общей для Delphi и C++Builder.

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

Для создания больших программных комплексов широко используется язык Си (С), первоначально разрабатываемый как язык системного программирования для ОС UNIX. Его разработал в 1972 г. Деннис Ричи, специалист по системному программированию фирмы «Белл телефон лабораторис». Простота, эффективность и переносимость сделали Си одним их наиболее распространенных языков программирования 70-80-х годов.

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

C++ (Си с классами) – язык программирования высокого уровня. Название С++, введенное Риком Масситти в 1983 г., указывает на эволюционную природу перехода к нему от языка Си (++ — это операция приращения в Си, который сохранен как подмножество). Еще одним источником послужил язык Simula-67: из него была позаимствована концепция класса (вместе с производными классами и функциями-членами). Это было сделано, чтобы способствовать модульности благодаря использованию виртуальных функций.

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

Широкой распространенности языка послужило создание Borland С++ Builder – интегрированного пакета, предоставившего программистам уникальное сочетание визуальной среды быстрой разработки приложений с традиционными средствами программирования на языке C++. Благодаря поддержке стандарта XML, упрощающего обмен данными через Web, C++ Builder позволяет быстро создавать различные Web-приложения.

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

В 1990 г. разработчик ПО компании Sun Microsystems Патрик Нотон, которому надоело поддерживать сотни различных интерфейсов программ, используемых в компании, представил руководству Sun письмо, в котором раскритиковал разрабатываемую в тот момент архитектуру ПО NeWS. Обращение вызвало одобрение как у высшего руководства компании, так и у всех ведущих инженеров. Была создана команда ведущих разработчиков с кодовым названием Green, которая занялась разработкой единого средства взаимодействия между различными бытовыми устройствами (видеомагнитофонами, проигрывателями лазерных дисков, стереосистемами и т.п.), реализованными на разных процессорах. Новый объектно-ориентированный язык программирования был назван Дуб (Oak).

В это время Sun Microsystems анонсировала систему Mosaic, которая легла в основу World Wide Web, с чего началось бурное развитие Интернет. Нотон предложил использовать Oak в создании Internet-приложений. Вскоре был написан Oak-компилятор и Oak-браузер «WebRunner». В 1995 г. компания Sun Microsystems объявила о новом продукте, переименовав его в Java. К основным особенностям языка Java следует отнести:

  •  простоту (учитывая то, что многие программисты хорошо знакомы с языком С++, Java, насколько это возможно, приближен к нему);
  •  безопасность – средства безопасности, встроенные в язык, позволяют создавать приложения, на которые сложно «напасть» извне; в сетевых средах приложения защищены от вторжения неавторизованного кода, пытающегося внедрить вирус или разрушить файловую систему;
  •  надежность – большое внимание уделено проверке программ на этапе компиляции, за которой следует динамическая проверка на этапе выполнения;
  •  объектно-ориентированность – программисты могут использовать стандартные библиотеки объектов, обеспечивающие работу с устройствами ввода/вывода, сетевые функции, методы создания графических пользовательских интерфейсов;
  •  многопоточность – реализация механизма поддержки параллельных процессов-потоков;
  •  высокая производительность – достигается за счет использования оптимизированного байт-кода, легко переводимого в машинный код;
  •  переносимость – программы на Java остаются неизменными на любой платформе. Архитектурная независимость и переносимость ПО обеспечивается виртуальной машиной Java (Java Virtual MashineJVM) — абстрактной машиной, для которой компилятор Java генерирует код. Специальные реализации JVM для конкретных аппаратных и программных платформ предоставляют уже конкретную виртуальную машину. JVM базируется на стандарте интерфейса переносимых операционных систем (POSIX);
  •  динамичность – язык разработан специально для подстройки под изменяющееся окружение. Новые программные модули могут подключаться из любых источников, в том числе поставляться по сети.

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

3. АЛГОРИТМЫ, ИХ СВОЙСТВА И СПОСОБЫ ПРЕДСТАВЛЕНИЯ

3.1. Понятие алгоритма и его свойства

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

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

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

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

Понятие алгоритма, раскрывающее его сущность на интуитивном уровне, следующее:

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

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

Единого определения алгоритма не существует. В качестве примера приведем следующие определения:

  •  Алгоритм — конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность (Д.Э.Кнут).
  •  Алгоритм — система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи (А.Колмогоров).
  •  Алгоритм — точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату (А.Марков).
  •  Алгоритм — точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа (Философский словарь / Под ред. М.М.Розенталя).
  •  Алгоритм — строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд (Н.Д.Угринович, учебник «Информатика и информационные технологии»).

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

Формула для нахождения корней квадратного уравнения

также является своеобразной формой записи алгоритма.

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

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

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

  •  Курту Гёделю (1906-1978) — австрийскому логику, математику и философу математики, наиболее известному сформулированной и доказанной им теоремой о неполноте;
  •  Алану Тьюрингу (1912-1954) — английскому математику, логику, криптографу. Предложенная им в 1936 г. абстрактная вычислительная «Машина Тьюринга» позволила формализовать понятие алгоритма и до сих пор используется во множестве теоретических и практических исследований;
  •  Эмилю Посту (1897-1954) — американскому математику и логику, предложившему абстрактную вычислительную машину — машину Поста;
  •  Андрею Маркову (1903)—1979) — советскому математику, основоположнику школы конструктивной математики. Одним из наиболее удачных стандартизованных вариантов алгоритма является введённое им понятие нормального алгоритма.

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

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

1. Детерминированность (определенность) — однозначность результата процесса при заданных исходных данных. Благодаря этому свойству выполнение алгоритма носит механический хаpактеp и не требует никаких дополнительных указаний или сведений о решаемой задаче.

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

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

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

3.2. Способы представления алгоритмов

На практике наиболее распространены следующие формы представления алгоритмов:

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

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

Пример 2. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел (алгоритм Эвклида).

Алгоритм можно описать так:

  1.  Задать два числа.
  2.  Если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма.
  3.  Определить большее из чисел.
  4.  Заменить большее из чисел разностью большего и меньшего из чисел.
  5.  Повторить алгоритм с шага 2.

Этот алгоритм применим к любым натуральным числам и должен приводить к решению поставленной задачи. Например:

а)

А

В

б)

А

В

225

125

13

4

225–125 = 100

125

13–4 = 9

4

100

125–100 = 25

9–4 = 5

4

100–25 = 75

25

5–4 = 1

4

75–25 = 50

25

1

4–1 = 3

50–25 = 25

=       25

1

3–1 = 2

1

=   21 = 1

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

Словесный способ не имеет широкого распространения, так как такие описания:

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

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

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

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

В таблице 3.1 приведены часто употребляемые графические примитивы в схемах алгоритмов.

Таблица 3.1. Графические примитивы схем алгоритмов

Название примитива

Обозначение и пример заполнения

Пояснение

Процесс

Вычислительное действие или последовательность действий

Решение

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

Модификация

Начало циклического процесса

Предопределенный процесс

Вычисления по подпрограмме, стандартной подпрограмме

Ввод-вывод

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

Пуск-останов

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

Документ

Вывод результатов на печать

Комментарий 

Связь между элементом схемы и пояснением

Узел

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

Ссылка на другую страницу

Обозначение связи между различными частями схемы алгоритма, размещенных на разных страницах

Линия потока

Обозначение последовательности связей между символами

Основные правила составления схемы алгоритма сводятся к следующему:

  1.  Графические примитивы соединяются между собой линиями потока, которые для каждого шага алгоритма указывают возможных преемников.
  2.  Внутри примитива дается краткое описание соответствующего шага.
  3.  Любой шаг или поток можно сопроводить пояснением с помощью «Комментария».
  4.  Примитивам присваиваются порядковые номера, проставляемые в разрыве линии контура в левом верхнем углу изображения.
  5.  Линии потока проводятся параллельно линиям внешней рамки схемы. Направление линии потока сверху вниз и слева направо принято за основной. Если они не имеют изломов, их можно не помечать стрелками. В остальных случаях их направление обязательно помечается стрелкой. Линию потока, как правило, подводят к середине символа.
  6.  Расстояние между параллельными линиями потока должно быть не менее 3 мм, а между другими символами – не менее 5 мм.
  7.  Линию потока можно обрывать, используя на месте обрыва «Узел» в пределах одной страницы или «Ссылка на другую страницу», если надо указать переход на другую страницу.
  8.  Размеры примитивов фиксированы. Если через b обозначить ширину элемента, а через а его высоту, то размер b = 1,5а, причем а должно принимать значения 10, 15, 20 мм. Допускается увеличивать размер а на величину, кратную 5.

Составление схем алгоритмов регламентируется двумя стандартами:

  •  ДСТУ 19.002-80 соответствует международному стандарту ИСО 2636-73 и определяет правила составления схем алгоритмов;
    •  ДСТУ 19.003-80 соответствует международному стандарту ИСО 1028-73 и регламентирует использование графических примитивов.

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

На рис. 3.1 показана схема алгоритма Эвклида нахождения НОД.

Пример 3. Необходимо составить алгоритм вычисления суммы элементов вектора , т.е.

.

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

Si := Si-1 + ai; S0 = 0; i := 1, 2, ..., n,

где Si — текущее значение суммы;

Si-1 — предыдущее ее значение;

S0 — начальное значение суммы;

ai — значение текущего элемента вектора.

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

Схема алгоритма приведена на рис. 3.2. Поясним ее.

1. Схема начинается с символа «Пуск-останов». Каждый вычислительный процесс имеет начало, и это отображается на схеме.

2. Начальные данные вводятся в память компьютера. Для обозначение этой операции используется символ «Ввода-вывода», внутри которого указываются, какие элементы вводятся.

3. Сумме присваивается начальное значение, равное нулю (S:=0). Это означает пересылку 0 в область памяти, предназначенную для накопления суммы. Операция на схеме отображается символом «Процесс». Принятое обозначение суммы S расшифровывается символом «Комментарий».

4. Индексу i, определяющему порядковый номер элемента, присваивается значение 1. При i = 1 происходит обращение к первому элемента вектора, т.е. а1.

5. К сумме S (на первом шаге i = 1, S = 0 и ai = а1) прибавляется значение элемента вектора ai (S := S + ai). В области памяти S записывается новое значение суммы.

6. С увеличением значения i на 1 (i = i + 1) определяется порядковый номер следующего элемента вектора.

7. Количество элементов вектора равно n. Отсюда, операция суммирования S := S + ai должна повторяться n раз, для чего осуществляется проверка: продолжать вычисление суммы или нет. Для выбора направления вычислений применяется символ «Решение». Внутри него указывается проверка условия i <= n. Если значение i не превысило своего максимального значения n, то операция вычисления суммы повторяется (переход к шагу 5), в противном случае осуществляется переход к шагу 8.

8. Осуществляется вывод полученной суммы S. Эта операция отображается на схеме символом «Ввода-вывода», внутри которой указывается, что именно выводится.

9. Схема заканчивается символом «Пуск-останов».

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

Пример 4. Рассмотрим алгоритм вычисления корней квадратного уравнения .

1. Ввести исходные данные a, b, c.

2. Вычислить .

3. Если d 0, то

  •  ;
    •  ;
      •  ;
      •  Вывести результаты на печать;
      •  Конец вычислений.

иначе

  •  Вывести сообщение «Действительных корней нет»;
    •  Конец вычислений.

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

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

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

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

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

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

Ввести А, В 

цикл-пока А ≠ В 

если А > В 

то А := А - В 

иначе В := В - А

все-если

все-цикл

Вывести А

Конец алгоритма.

Рис. 3.3. Алгоритм Евклида на псевдокоде

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

Следовательно, язык для записи алгоритмов должен быть формализован. Такой язык принято называть языком программирования, а запись алгоритма на этом языке — программой для компьютера.

Вид алгоритма Евклида, представленного в виде программы на языке Pascal, приведен на рис. 3.4.

Program Evklid;

Var A,B: integer;

Begin

Writeln(‘Input A,B’);

Readln(A,B);

While A<>B do

 If A>B Then A:=A-B

        Else B:=B-A;

Writeln(‘A=’,A);

Readln;

End.

Рис. 3.4. Алгоритм Евклида на языке Pascal

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

ВЫВОДЫ

  1.  Предмет учебной дисциплины «Технологии программирования» составляют алгоритмы решения прикладных задач, язык и среда программирования Delphi. Целями дисциплины являются: формирование у студентов понимания принципов функционирования программного обеспечения ЭВМ, навыков создания программных продуктов с использованием современных средств разработки, изучение технологии использования визуальных средств программирования.
  2.  Программа – это упорядоченная последовательность команд (инструкций) компьютера для решения конкретной задачи. Программный продукт (изделие) – это комплекс взаимосвязанных программ для решения определенной проблемы (задачи) массового спроса, подготовленный к реализации как любой вид промышленной продукции. Процесс создания программы включает постановку задачи, ее анализ, разработку алгоритма ее решения на этапе проектирования, собственно программирование на этапе реализации и модификацию программы по результатам эксплуатации.
  3.  Языки программирования разделяются на машинные, машинно-ориентированные, процедурно-ориентированные, проблемно-ориентированные, интегрированные системы программирования. Современная тенденция развития языков программирования заключается в улучшении функций, реализуемых существующими языками и в создании интегрированных визуальных объектно-ориентированных сред программирования.
  4.  Алгоритм – это точно определенное правило действий, для которого задано указание, как и в какой последовательности это правило необходимо применять к исходным данным задачи, чтобы получить ее решение за конечное число шагов. Алгоритм характеризуется рядом свойств, к которым относятся: детерминированность, дискретность, массовость и результативность. Алгоритм может представлен словесно, графически, аналитически, псевдокодом или на языке программирования.

Контрольные вопросы

  1.  Что такое программа?
    1.  Из каких этапов состоит процесс создания программы?
    2.  Что такое язык программирования и чем он задается?
    3.  Как классифицируются языки программирования?
    4.  Что такое алгоритм и какими свойствами он должен обладать?
    5.  В каких формах может быть представлен алгоритм?
    6.  Как словесно описывается алгоритм и в чем состоят недостатки такого представления?
    7.  Какие графические примитивы используются в схемах алгоритмов?
    8.  В каких случаях используется аналитическая запись алгоритмов?
    9.  В чем заключается представление алгоритма псевдокодом?

Задачи

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

где Р — подрядная (сдельная) расценка за единицу продукции;

Вф — фактический заработок;

П — премия;

Вд — сверхплановый заработок;

Рд — надбавка к расценке.

  1.  Составьте схему алгоритма определения максимального элемента вектора  и его порядкового номера.
  2.  Составьте схему алгоритма вычисления бесконечной суммы

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

  1.  Составьте схему алгоритма вычисления суммы элементов заданной матрицы А(5, 3):

.

Задание на самостоятельную работу

  1.  Изучите материал лекции, представленный в электронной форме.
  2.  Ответьте на контрольные вопросы и решите задачи.
  3.  Изучить Приложения 1, 2 лабораторного занятия № 1 «Алгоритмизация базовых структур».

* Название «алгоритм» произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi), жившего в 783-850 гг. В своей книге «Об индийском счете» он изложил правила записи натуральных чисел с помощью арабских цифр и правила действий над ними «столбиком». В XII веке эта книга была переведена на латынь и получила широкое распространение в Европе.


Постановка задачи

Анализ

Проектирование

Реализация

Модификация

a

b

x = (cd)*e

a < b

Да

Нет

i = 1,50,2

Расчет параметров

Ввод

A, B, C

ачало

Печать

а, с

5

Рис. 3.1. Схема алгоритма Евклида

Рис. 3.2. Схема алгоритма вычисления суммы элементов вектора а

  1.  

 

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

74012. Международные отношения в Европе в предвоенные годы. Политика «умиротворения агрессора» и ее итоги 21.5 KB
  ВОСТОЧНЫЙ ПАКТ проект договора о взаимопомощи между СССР Чехословакией Польшей Финляндией Латвией Эстонией и Литвой против агрессии фашистской Германии. Из крупных держав только СССР не имевший дипломатических отношений с Абиссинией решительно выступил в ее защиту. международные позиции СССР значительно окрепли. явное нежелание Англии и Франции договориться с СССР о коллективной безопасности ставили его в условия полной изоляции перед агрессором.
74013. Комплексная характеристика Второй Мировой войны и ее итогов 27.83 KB
  Ослабла роль Западной Европы в общемировой политике. Главными державами в мире стали СССР и США. Gb и Фр были значительно ослаблены. Война показала неспособность их и других западноевропейских стран содержать огромные колониальные империи. В странах Африки и Азии усилилось антиколониальное движение. В результате войны часть стран смогла добиться независимости: Эфиопия, Исландия, Сирия, Ливан, Вьетнам, Индонезия.
74014. Международные отношения в период «холодной войны» (1946 -1991 гг.) 32.76 KB
  Проблема репараций: Формы репараций с Германии и её союзников были определены на Ялтинской конференции 1945 г На Потсдамской конф-ии 1945г: репарац. претензии СССР будут удовлетворены путём изъятия из вост.зоны Германии и за счёт германских активов, находящихся в Болгарии
74016. Становление, развитие и крах социалистической системы в странах Восточной Европы. Государства региона на современном этапе исторического развития 48.84 KB
  В известной мере этому способствовала внутренняя и внешняя политика правящих кругов СССР. Руководство КПСС оставило в неприкосновенности режим безраздельной власти партийно-государственного аппарата,продолжало сохранять стиль авторитаризма в отношениях
74017. Страны Запада на рубеже XX – XXI вв.: становление и эволюция постиндустриального общества 39.5 KB
  США отменили золотое содержание доллара. А поскольку именно арабские страны являлись основным поставщиком нефти то вскоре они заявили что не будут поставлять нефть странам поддержавшим Израиль это касалось прежде всего США и их союзников в Западной Европе.
74020. Множественность преступлений 43.97 KB
  Множественность преступлений. Понятие множественности преступлений. Понятие единичного преступления и его виды Уголовный закон предусматривает значительное количество норм в соответствии с которыми совершение лицом нескольких преступлений влечет за собой уголовно-правовые последствия существенно повышающие его уголовную ответственность и усиливающие наказание. Множественность преступлений включает в себя в качестве составных элементов несколько единичных единых преступлений.