Алгоритмизация. Алгоритмизация и программирование учебник. Учебник для спо В. В. Трофимов, Т. А. Павловская под ред. В. В. Трофимова. М. Издатель ство Юрайт, 2018. 137 с. (Серия Профессио нальное образование)
 Скачать 315.03 Kb.
|
|
В. В. Трофимов, Т. А. Павловская ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ УЧЕБНИК ДЛЯ СПО Под редакцией В. В. Трофимова Рекомендовано Учебно-методическим отделом среднего профессионального образования в качестве учебника для студентов образовательных учреждений среднего профессионального образования Москва Юрайт 2018 Книга доступна в электронной библиотечной системе biblio-online.ru УДК 681.3(075.32) ББК 32.81я723 Т76 Авторы: Трофимов Валерий Владимирович — доктор технических наук, про- фессор, заслуженный деятель науки Российской Федерации, заведующий кафедрой информатики факультета информатики и прикладной матема- тики Института экономики Санкт-Петербургского государственного эко- номического университета, профессор кафедры информатики и приклад- ной математики — 1 факультета компьютерных технологий и управления Санкт-Петербургского нацио нального исследовательского университета информационных технологий, механики и оптики; Павловская Татьяна Александровна — профессор, кандидат техни- ческих наук, работала в должности профессора на кафедре информатики Санкт-Петербургского государственного экономического университета. Рецензенты: Песоцкая Е. В. — доктор экономических наук, профессор Санкт- Петербургского государственного экономического универститета; Стельмашонок Е. В. — доктор экономических наук, профессор Санкт- Петербургского государственного инженерно-экономического универси- тета; Гаспариан М. С. — доктор экономических наук, профессор. Т76 Трофимов, В. В. Основы алгоритмизации и программирования : учебник для СПО / В. В. Трофимов, Т. А. Павловская ; под ред. В. В. Трофимова. — М. : Издатель- ство Юрайт, 2018. — 137 с. — (Серия : Профессио нальное образование). ISBN 978-5-534-07321-8 В учебнике, представляющем собой один из модулей дисциплины «Информатика», рассмотрены модели решения функцио нальных и вычис- лительных задач, алгоритмизация и программирование, языки программи- рования высокого уровня, технологии программирования. Соответствует актуальным требованиям Федерального государствен- ного образовательного стандарта среднего профессио нального образова- ния и профессио нальным требованиям. Для студентов образовательных учреждений среднего профессио- нального образования, обучающихся по экономическим специальностям, преподавателей, специалистов организаций любого уровня и сферы хозяй- ствования. УДК 681.3(075.32) ББК 32.81я723 ISBN 978-5-534-07321-8 © Трофимов В. В., Павловская Т. А., 2010 © ООО «Издательство Юрайт», 2018 Все права защищены. Никакая часть данной книги не может быть воспроизведена в какой бы то ни было форме без письменного разрешения владельцев авторских прав. Правовую поддержку издательства обеспечивает юридическая компания «Дельфи». Оглавление Предисловие ...................................................................................5 Глава 1. Основы алгоритмизации .......................................... 7 1.1. Понятие алгоритма и его свойства........................................................8 1.2. Методы разработки алгоритмов .........................13 Глава 2. Основные понятия языка высокого уровня .......... 18 2.1. Эволюция и классификация языков программирования .............................................19 2.2. Программа, порядок ее разработки и исполнения .......................................................31 2.3. Языки высокого уровня: алфавит, синтаксис, семантика ............................................................36 2.4. Концепция типа данных .....................................38 2.5. Линейные программы .........................................45 Глава 3. Интегрированные среды программирования ...... 51 3.1. Обзор возможностей интегрированных сред ....52 3.2. Написание, запуск, отладка и корректировка программы ..............................52 Глава 4. Структурное программирование ........................... 62 4.1. Базовые конструкции структурного программирования и их реализация в виде управляющих конструкций языка ......................63 4.2. Программирование условий: условный оператор, оператор выбора ................................64 4.3. Программирование циклов ................................69 4.4. Средства организации модульности в языках высокого уровня .............76 Глава 5. Структуры и типы данных ...................................... 88 5.1. Абстрактные типы данных: стек, линейный список, двоичное дерево .....................................89 Оглавление 4 5.2. Реализация динамических структур средствами языков высокого уровня ..................92 Глава 6. Парадигмы и технологии программирования ... 102 6.1. Парадигмы программирования ...........................................103 6.2. Понятие программного продукта .....................105 6.3. Обзор современных технологий разработки программного обеспечения. Понятие о UML ...106 6.4. Введение в объектно‑ориентированное программирование ...........................................120 Вопросы для самоконтроля .................................................. 133 Литература ............................................................................. 135 Новые издания по дисциплине «Информатика» и смежным дисциплинам ...................................................... 136 4 Предисловие Предисловие Алгоритмизация и программирование — один из модулей дисци- плины «Информатика». Материал учебника подобран таким обра- зом, чтобы в нем содержались ответы на большинство вопросов, предлагаемых на экзамене. Как показал опыт проведения интер- нет-экзамена среди студентов экономических специальностей, вопросы по данному модулю вызывают наибольшие трудности. Поэтому материал модуля дан максимально подробно и изложен по принципу «от простого к сложному». Дополнительный материал дан в минимальном объеме и предназначен только для облегче- ния усвоения основного. После изучения материалов учебника студент должен освоить: трудовые действия владения навыками составления программ на ПАСКАЛе, содержащих подпрограммы; необходимые умения составлять программы на одном из языков структурного про- граммирования; описывать и использовать объекты в программах на ПАСКАЛе; необходимые знания понятия интегрированной среды программирования; целей, принципов и базовых конструкций структурного про- граммирования; управляющих операторов языка ПАСКАЛЬ, реализующих базовые конструкции; понятия «парадигма программирования», «технология про- граммирования»; общих представлений о современных технологиях создания программного обеспечения; моделей жизненного цикла разработки программного обес- печения. Учебник предназначен для студентов СПО экономических (гума- нитарных) специальностей и преподавателей, осуществляющих 5 Предисловие подготовку к экзамену, проводимому в Интернете. Он может быть полезен и школьникам выпускных классов, готовящимся к посту‑ плению в вузы с углубленным изучением информатики. Учебник может быть использован аспирантами гуманитарных специально‑ стей, самостоятельно изучающими данный раздел информатики. Специалисты организаций любого уровня и сферы хозяйствова‑ ния тоже могут здесь найти для себя полезный материал, позво‑ ляющий повысить уровень их квалификации. ГЛАВА 1 Основы алгоритмизации Задачи главы 1. Изучить понятие алгоритма. 2. Изучить свойства алгоритма. 3. Рассмотреть типы алгоритмических моделей. 4. Освоить способы описания алгоритмов. 5. Получить представление о методах разработки алгоритмов. После изучения главы 1 бакалавр должен: знать • современные возможности реализации алгоритмов; • принципы построения алгоритмов; уметь • составлять блок-схемы алгоритмов; • составлять программы на алгоритмическом языке высокого уровня; • работать в интегрированной среде изучаемых языков программи‑ рования; владеть • практическими навыками разработки и реализации алгоритмов обработки различных данных. Глава 1. Основы алгоритмизации 8 1.1. Понятие алгоритма и его свойства Алгоритмом называют точное предписание, которое задается вычислительному процессу и представляет собой конечную после‑ довательность обычных элементарных действий, четко опреде‑ ляющую процесс преобразования исходных данных в искомый результат. Приведенная фраза представляет собой не определение, а объяснение сути, поскольку понятие алгоритма является фунда‑ ментальным и не может быть выражено через другие, поэтому его следует рассматривать как неопределяемое. В качестве примера алгоритма приведем алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух нату‑ ральных чисел. Вот одна из возможных формулировок этого алго‑ ритма, описанная по шагам: 1) присвоить переменным X и Y значения, НОД которых ищется; 2) если X > Y, то перейти на шаг 5; 3) если X < Y, то перейти на шаг 6; 4) здесь X = Y. Выдать Х в качестве результата. Конец работы; 5) заменить пару (Х, Y) парой (Х – Y, Y) и вернуться на шаг 2; 6) заменить пару (Х, Y) парой (Х, Y – Х) и вернуться на шаг 2. Выяснение того, какие объекты и действия над ними следует счи‑ тать точно определенными, какими возможностями обладают ком‑ бинации элементарных действий, что можно и чего нельзя сделать с их помощью, — все это предмет теории алгоритмов и формальных систем, которая первоначально возникла в рамках математики и стала важнейшей ее частью. Как указывал В. А. Успенский, самым главным открытием в науке об алгоритмах, безусловно, было открытие самого понятия алгоритма в качестве новой и отдельной сущности. Вычисления протекают во времени и в пространстве. Каждый шаг алгоритма выполняется за какое‑то конечное время. Для раз‑ мещения данных необходимо пространство — память. Рассмот‑ рим основные свойства алгоритма. Каждый алгоритм имеет дело с дан‑ ными — входными, промежуточными и выходными. Свойства алгоритма 1.1. Понятие алгоритма и его свойства 9 Конечность. Понимается двояко: во‑первых, алгоритм состоит из отдельных элементарных шагов, или действий, причем множе‑ ство различных шагов, из которых составлен алгоритм, конечно. Во‑вторых, алгоритм должен заканчиваться за конечное число шагов. Если строится бесконечный, сходящийся к искомому реше‑ нию процесс, то он обрывается на некотором шаге и полученное значение принимается за приближенное решение рассматривае‑ мой задачи. Точность приближения зависит от числа шагов. Элементарность (понятность). Каждый шаг алгоритма дол‑ жен быть простым, чтобы устройство, выполняющее операции, могло выполнить его одним действием. Дискретность. Процесс решения задачи представляется конеч‑ ной последовательностью отдельных шагов, и каждый шаг алгоритма выполняется за конечное (не обязательно единичное) время. Детерминированность (определенность). Каждый шаг алго‑ ритма должен быть однозначно и недвусмысленно определен и не дол‑ жен допускать произвольной трактовки. После каждого шага либо указывается, какой шаг делать дальше, либо дается команда оста‑ новки, после чего работа алгоритма считается законченной. Результативность. Алгоритм имеет некоторое число вход‑ ных величин — аргументов. Цель выполнения алгоритма состоит в получении конкретного результата, имеющего вполне опреде‑ ленное отношение к исходным данным. Алгоритм должен оста‑ навливаться после конечного числа шагов, зависящего от дан‑ ных, с указанием того, что считать результатом. Если решение не может быть найдено, то должно быть указано, что в этом слу‑ чае считать результатом. Массовость. Алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исход‑ ные данные могут выбираться из некоторой области, которая назы‑ вается областью применимости алгоритма. Эффективность. Одну и ту же задачу можно решить по‑раз‑ ному и соответственно за разное время и с различными затратами памяти. Желательно, чтобы алгоритм состоял из минимального числа шагов и при этом решение удовлетворяло бы условию точ‑ ности и требовало минимальных затрат других ресурсов. Точное математическое определение алгоритма затрудняется тем, что интерпретация предусмотренных предписаний не должна Глава 1. Основы алгоритмизации 10 зависеть от выполняющего их субъекта. В зависимости от своего интеллектуального уровня он может либо не понять, что имеется в виду в инструкции, либо интерпретировать ее непредусмотрен‑ ным образом. Можно обойти проблему интерпретации правил, если наряду с формулировками предписаний описать конструкцию и принцип действия интерпретирующего устройства. Это позволяет избе‑ жать неопределенности и неоднозначности в понимании одних и тех же инструкций. Для этого необходимо задать язык, на кото‑ ром описывается множество правил поведения, либо последова‑ тельность действий, а также само устройство, которое может интер‑ претировать предложения, сделанные на этом языке, и выполнять шаг за шагом каждый точно определенный процесс. Оказывается, что такое устройство (машину) можно выполнить в виде, кото‑ рый остается постоянным независимо от сложности рассматри‑ ваемой процедуры. В настоящее время можно выделить три основных типа универ‑ сальных алгоритмических моделей. Они различаются исходными посылками относительно определения понятия алгоритма. Первый тип связывает понятие алгоритма с наиболее традици‑ онными понятиями математики — вычислениями и числовыми функциями. Второй тип основан на представлении об алгоритме как о некотором детерминированном устройстве, способном выпол‑ нять в каждый отдельный момент лишь весьма примитивные опера‑ ции. Такое представление обеспечивает однозначность алгоритма и элементарность его шагов. Кроме того, такое представление соот‑ ветствует идеологии построения компьютеров. Основной теоре‑ тической моделью этого типа, созданной в 1930‑х гг. английским математиком Аланом Тьюрингом, является машина Тьюринга. Третий тип — это преобразования слов в произвольных алфа‑ витах, в которых элементарными операциями являются подста‑ новки, т.е. замены части слова (под словом понимается последо‑ вательность символов алфавита) другим словом. Преимущества этого типа моделей состоят в его максимальной абстрактности и возможности применить понятие алгоритма к объектам произ‑ вольной (необязательно числовой) природы. Примеры моделей третьего типа — канонические системы американского матема‑ тика Эмиля Л. Поста и нормальные алгоритмы, введенные совет‑ ским математиком А. А. Марковым. 1.1. Понятие алгоритма и его свойства 11 Модели второго и третьего типа довольно близки и отлича‑ ются в основном эвристическими акцентами, поэтому не случайно говорят о машине Поста, хотя сам Пост такое название не вводил. Запись алгоритма на некотором языке представляет собой про‑ грамму. Если программа написана на специальном алгоритмиче‑ ском языке (например, на ПАСКАЛе или БЕЙСИКе), то говорят об исходной программе. Программа, написанная на языке, кото‑ рый непосредственно понимает компьютер (как правило, это дво‑ ичные коды), называется машинной, или двоичной. Любой способ записи алгоритма подразумевает, что всякий описываемый с его помощью предмет задается как конкретный представитель некоторого класса объектов, которые можно опи‑ сывать данным способом. Средства, используемые для записи алгоритмов, в значитель‑ ной мере определяются тем, кто будет исполнителем. Если исполнителем будет человек, запись может быть не пол‑ ностью формализована, на первое место выдвигаются понятность и наглядность. В этом случае можно использовать словесную форму записи или схемы алгоритмов. Для записи алгоритмов, предназначенных для исполнителей‑ав‑ томатов, необходима формализация, поэтому в таких случаях при‑ меняют формальные специальные языки. Преимущество формаль‑ ного способа записи состоит в том, что он дает возможность изучать алгоритмы как математические объекты; при этом формальное описание алгоритма служит основой, позволяющей интеллекту‑ ально охватить этот алгоритм. Для записи алгоритмов используют самые разнообразные сред‑ ства. Выбор средства определяется типом исполняемого алгоритма. Выделяют следующие основные способы записи алгоритмов: вербальный — алгоритм описывается на человеческом языке; символьный — алгоритм описывается с помощью набора символов; графический — алгоритм описывается с помощью набора гра‑ фических изображений. Общепринятыми способами записи алгоритма являются графи‑ ческая запись с помощью схем алгоритмов (блок‑схем) и символь‑ ная запись с помощью какого‑либо алгоритмического языка. Глава 1. Основы алгоритмизации 12 Для описания алгоритма с помощью схем изображают связан‑ ную последовательность геометрических фигур, каждая из кото‑ рых подразумевает выполнение определенного действия алгоритма. Порядок выполнения действий указывается стрелками. В схемах алгоритмов используют следующие типы графичес‑ ких обозначений. Начало и конец алгоритма обозначают с помощью одноимен‑ ных символов (рис. 1.1). Начало Конец Рис. 1.1. Обозначения начала и конца алгоритма Шаг алгоритма, связанный с присвоением нового значения некоторой переменной, преобразованием некоторого значения с целью получения другого значения, изображается символом «процесс» (рис.1.2). S Рис. 1.2. Обозначение процесса Выбор направления выполнения алгоритма в зависимости от некоторых переменных условий изображается символом «реше‑ ние» (рис. 1.3). P Рис. 1.3. Обозначение решения Здесь Р означает предикат (условное выражение, условие). Если условие выполнено (предикат принимает значение ИСТИНА), 1.2. Методы разработки алгоритмов 13 то выполняется переход к одному шагу алгоритма, а если не выпол‑ нено, то к другому. Имеются примитивы для операций ввода и вывода данных, а также другие графические символы. В настоящий момент они определены стандартом ГОСТ 19.701—90 (ИСО 5807—85) «Еди‑ ная система программной документации. Схемы алгоритмов, про‑ грамм, данных и систем. Условные обозначения и правила выпол‑ нения». Всего сборник ЕСПД содержит 28 документов. По схеме алгоритма легко составить исходную программу на алгоритмическом языке. В зависимости от последовательности выполнения действий в алгоритме выделяют алгоритмы линейной, разветвленной и цик‑ лической структуры. В алгоритмах линейной структуры действия выполняются пос‑ ледовательно одно за другим. В алгоритмах разветвленной структуры в зависимости от выполнения или невыполнения какого‑либо условия производятся различные последовательности действий. Каждая такая последо‑ вательность действий называется ветвью алгоритма. В алгоритмах циклической структуры в зависимости от выпол‑ нения или невыполнения какого‑либо условия выполняется повто‑ ряющаяся последовательность действий, называющаяся телом цикла . Вложенным называется цикл, находящийся внутри тела другого цикла. Итерационным называется цикл, число повторе‑ ний которого не задается, а определяется в ходе выполнения цикла. Одно повторение цикла называется итерацией. 1.2. Методы разработки алгоритмов 1 Ключевым подходом в алгоритмизации является сведение задачи к подзадачам. Это естественно, так как предстоит превратить один шаг в последовательность элементарных шагов. Само это прео‑ бразование также может состоять из нескольких этапов, на кото‑ рых единственный шаг разбивается на несколько более простых, но еще не элементарных. Эти более простые шаги соответствуют 1 Использованы материалы сайта http://it.kgsu.ru (автор — Т. А. Никифорова). Глава 1. Основы алгоритмизации 14 частным задачам (подзадачам), совокупное решение которых при‑ водит к решению исходной задачи. Различные методы разработки алгоритмов отличаются тем, на какие подзадачи производится разбиение и как эти подзадачи соотносятся между собой. Хотя общепринятой классификации мето‑ дов разработки алгоритмов нет, тем не менее некоторые общие соображения на этот счет могут быть высказаны. Любая задача может быть сформулирована как функция пре‑ образования исходных данных в выходные данные: f (X) = Y.Как исходные данные, так и функция могут быть достаточно слож‑ ными. Например, X — число, вектор, текст на каком‑либо языке, БД, рисунок, информация. То же можно сказать и о выходных дан‑ ных. Функция может быть суммой чисел, тригонометрической фун‑ кцией, корнем уравнения, переводом текста с русского на англий‑ ский язык, раскраской полутонового рисунка и т.д. Разбивая задачу на подзадачи, можно: разбивать исходные и выходные данные на части или упрощать их; производить деком‑ позицию функции, т.е. превращать ее в суперпозицию более про‑ стых. Под разбиением данных понимается разделение структуры данных на части, например разделение вектора из десяти компонентов на два век‑ тора по пять компонентов или разделение текста на предложе‑ ния. Под упрощением данных понимаются такие ситуации, когда, например, X — число и его нельзя разбить на части, но его можно разложить, скажем, на сумму X = X 1 + X 2 так, что результаты f(X 1 ), f (X 2 ) отыскиваются проще, чем f(X). При разработке алгоритма может использоваться отдельно пер‑ вый подход, отдельно второй подход или оба подхода совместно. Разложение задачи в последователь‑ ность разнородных подзадач иногда называют методом «разделяй и властвуй». В этом методе обычно выделяется относительно небольшое число подзадач. Например: задача — выполнить программу на компью‑ тере; подзадачи — ввести исходный текст программы; транслиро‑ вать программу в машинные команды; подсоединить к машинному коду стандартные процедуры из библиотеки; загрузить программу Разбиение данных Разложение задачи на подзадачи 1.2. Методы разработки алгоритмов 15 в оперативную память; запустить процесс выполнения; завершить процесс выполнения программы. Результаты решения первой подзадачи становятся исходными данными для второй подзадачи и т.д. Таким образом, здесь исполь‑ зован второй подход в чистом виде (декомпозиция функции, задание ее в виде суперпозиции более простых). Заметим также, что такая суперпозиция может быть задана последовательным соединением машин Тьюринга. На алгоритмическом языке этот метод может быть выражен записью последовательно вызываемых процедур. Важный частный случай предыдущего метода — разложение задачи в последовательность однородных подзадач приобре‑ тает новое качество за счет того, что задача P сводится к n экзем‑ плярам более простой задачи R и к простой задаче Q, объединяю‑ щей n решений. Пример Вычислим скалярное произведение двух векторов — A и B: S:=0; {Задача Q — подготовка места для суммирования.} for i:= 1 to n do S:=S+A[i]*B[i]; {Задача R — перемножение компонент и суммиро‑ вание.} Этот алгоритм использует разбиение исходных данных на части — отдельные компоненты векторов. Однородность подзадач позволяет значительно сократить длину текста алгоритма за счет применения операторов повторения. Ите‑ рация на уровне крупных подзадач или отдельных небольших опе‑ раторов встречается в большинстве реальных алгоритмов и служит основным источником эффективного использования компьютера по сравнению с другими вычислительными средствами (например, непрограммируемым калькулятором). Рекурсия —это сведение задачи к самой себе. Задача так же, как и в пре‑ дыдущем методе, сводится к более простой. Но эта более простая задача имеет ту же формулировку, что и исходная, с той лишь раз‑ ницей, что решаться она должна для более простых исходных дан‑ ных. Это чистый вариант упрощения исходных данных. Рекурсия |