Алгоритмизация и программирование
Учебное пособие С. А. Канцедала «Алгоритмизация и программирование» представляет собой комплексный образовательный ресурс, предназначенный для формирования базовых компетенций в области разработки программного обеспечения. Книга охватывает путь от теоретических основ логического мышления до практической реализации сложных алгоритмов на языке высокого уровня.
Теоретический фундамент: природа алгоритмов
Автор начинает с глубокого анализа понятия алгоритма, определяя его как детерминированную последовательность действий, приводящую к решению задачи. В работе подробно рассматриваются свойства алгоритмов: дискретность, результативность и массовость. Особое внимание уделяется анализу временной сложности. Канцедал классифицирует алгоритмы на полиномиальные (эффективные) и экспоненциальные, вводя читателя в проблематику классов P и NP. Это позволяет студентам не просто писать код, но и оценивать его производительность и масштабируемость еще на этапе проектирования.
Архитектура ЭВМ и низкоуровневая логика
Для понимания того, как программный код взаимодействует с «железом», в пособии приводится детальный обзор устройства компьютера. Рассматриваются принципы фон Неймана, иерархия памяти (от регистров процессора до долговременных накопителей) и система команд. Автор демонстрирует переход от машинных кодов к символьному программированию (ассемблеру), наглядно показывая, как работают указатели команд, стеки и прерывания. Этот раздел критически важен для формирования понимания того, как высокоуровневые конструкции языка Pascal трансформируются в электрические сигналы и операции над байтами.
Методология структурного программирования
Центральное место в книге занимает концепция структурного программирования «сверху вниз». Канцедал настаивает на использовании базовых управляющих структур: следования, ветвления и циклов. На многочисленных примерах (от вычисления факториала до решения систем линейных уравнений методом Гаусса) демонстрируется, как разбиение сложной задачи на подзадачи упрощает отладку и повышает надежность кода. Автор подробно разбирает работу с различными типами данных: скалярными переменными, массивами, строками и записями, а также вводит понятие динамической памяти и указателей.
Практикум на языке Turbo Pascal 7.0
Выбор Turbo Pascal в качестве базового языка обусловлен его строгой типизацией и прозрачной структурой, что идеально подходит для обучения. В пособии детально описана среда программирования, правила синтаксиса и стандартные библиотеки (модули Crt, Graph, System). Читатель учится работать с текстовыми и типизированными файлами, организовывать ввод-вывод и создавать собственные программные модули. Отдельная глава посвящена графическим возможностям языка, включая построение графиков функций и основы компьютерной анимации.
Современный программный ландшафт
Завершает пособие обзор системного и прикладного программного обеспечения. Автор дает краткую характеристику операционным системам семейства Windows, описывает принципы работы глобальной сети Internet и протоколов TCP/IP. Также рассматриваются популярные пакеты прикладных программ (Microsoft Office, AutoCAD, Mathcad), что помогает студенту сориентироваться в инструментарии, используемом в профессиональной инженерной и научной деятельности.
Таким образом, книга С. А. Канцедала является фундаментальным руководством, которое не только обучает синтаксису конкретного языка, но и закладывает методологическую базу для дальнейшего освоения объектно-ориентированного программирования и современных ИТ-технологий. Пособие сочетает в себе академическую строгость изложения с практической направленностью, предлагая большое количество задач для самостоятельного решения.
- Среднее профессиональное образование
- 08.02.15: Информационное моделирование в строительстве
- 09.02.01: Компьютерные системы и комплексы
- 09.02.02: Компьютерные сети
- 09.02.03: Программирование в компьютерных системах
- 09.02.04: Информационные системы (по отраслям)
- 09.02.05: Прикладная информатика (по отраслям)
- 09.02.06: Сетевое и системное администрирование
- 09.02.07: Информационные системы и программирование
- 09.02.08: Интеллектуальные интегрированные системы
- 09.02.09: Веб-разработка
- 10.02.02: Информационная безопасность телекоммуникационных систем
- 10.02.03: Информационная безопасность автоматизированных систем
- 10.02.04: Обеспечение информационной безопасности телекоммуникационных систем
- 10.02.05: Обеспечение информационной безопасности автоматизированных систем
- 27.02.01: Метрология
- 55.02.01: Театральная и аудиовизуальная техника (по видам)
АЛГОРИТМИЗАЦИЯ И ПРОГРАММИРОВАНИЕ С.А. Канцедал Допущено Министерством образования и науки Российской Федерации в качестве учебного пособия для студентов учреждений среднего профессионального образования, обучающихся по группе специальностей «Информатика и вычислительная техника» Москва ИД «ФОРУМ» — ИНФРА-М 202
УДК 519.6(075.32) ББК 32.973-018я723 К19 Канцедал С.А. К19 Алгоритмизация и программирование : учебное пособие / C.А. Канцедал. — Москва : ИД «ФОРУМ» : ИНФРА-М, 2026. — 352 с. — (Среднее профессиональное образование). ISBN 978-5-8199-0727-6 (ИД «ФОРУМ») ISBN 978-5-16-013490-1 (ИНФРА-М, print) ISBN 978-5-16-100506-4 (ИНФРА-М, online) В учебнике рассмотрены основы проектирования технологических процессов, а также технологического оснащения применительно к производству летательных аппаратов. Описаны специфика этой отрасли машиностроения, технологическая подготовка серийного производства и методика разработки оптимального варианта технологических процессов. Приведены основные положения о надежности и технологичности машин, описаны методы их достижения. Указаны основные направления обеспечения экономической эффективности технологических процессов — снижения себестоимости машин, увеличения производительности труда и сроков окупаемости капитальных вложений на технологическое оснащение. Для студентов учреждений среднего профессионального образования по специальности «Производство летательных аппаратов». УДК 519.6(075.32) ББК 32.973-018я723 Р е ц е н з е н т ы: зав. кафедрой «Информатика и программное обеспечение вычислительных систем» Московского государственного института электронной техники (технического университета), доктор технических наук, профессор Л.Г. Гагарина; зав. кафедрой «Программное обеспечение вычислительной техники» Житомирского государственного технологического университета, кандидат технических наук А.М. Данильченко ISBN 978-5-8199-0727-6 (ИД «ФОРУМ») ISBN 978-5-16-013490-1 (ИНФРА-М, print) ISBN 978-5-16-100506-4 (ИНФРА-М, online) © Канцедал С.А., 2014 © ИД «ФОРУМ», 2014
Предисловие Программирование для компьютеров — это профессиональное занятие, состоящее в разработке программ обработки информации на электронных вычислительных машинах (ЭВМ). На заре интенсивного строительства и использования ЭВМ — в США в середине 1940-х, а в СССР в середине 1950-х годов прошлого столетия — специалистов, составляющих программы для компьютеров, стали называть программистами. Следует однако отметить, что этот вид деятельности возник значительно раньше, когда более чем сто пятьдесят лет назад первые две программы для аналитической счетной машины Ч. Бебиджа составила Ада Лавлейс, дочь поэта Байрона, известный в то время математик. В память об этой женщине и этом событии универсальный язык программирования, созданный по заказу военного ведомства США в начале 80-х годов прошлого столетия, был назван Ада. Программирование как занятие сочетает в себе и элементы ремесла, и элементы творчества, что, впрочем, свойственно многим профессиям. Возможность творческого подхода обусловлена прежде всего тем, что для одной и той же задачи обработки информации можно составить разные программы. Каждая из этих программ является плодом как воображаемого метода решения задачи, так и разнообразных манипуляций элементарными действиями — командами компьютера. Именно эти обстоятельства порождают возможность при составлении программы проявить фантазию, нетривиальную логику, специфику мышления и другие черты, свойственные творческим процессам. В то же время программист ограничен конечным набором четких, однозначно выполняемых команд компьютера, применение которых строго оговорено и не допускает никаких других толкований. Поэтому, располагая методом решения задачи и правильно применяя эти команды, всегда можно составить какую-либо программу, что и вносит рутину в процесс программирования. В настоящее время программированию для компьютеров учат в общеобразовательных и специализированных математических
школах, средних и высших учебных заведениях, на специальных начальных курсах и курсах повышения квалификации специалистов. Объем материала по дисциплине напрямую зависит от объема выделенных часов, который в разных учебных заведениях различен. Безусловно, профессиональные программисты после изучения указанной дисциплины не могут быть подготовлены, однако базис профессионализма, по нашему убеждению, должен быть заложен. С нашей точки зрения, для того чтобы стать прикладным программистом, по крайней мере средней руки, начинающий специалист должен уметь: 1) решать задачи из различных областей математики, физики, механики, статистики и др. и самое главное четко и ясно записывать ход их решения; иными словами — уметь составлять алгоритмы решения задач; 2) знать устройство и принцип работы современного компьютера, четко представлять, что такое программа на языке компьютера, где она хранится и как им выполняется; 3) знать один или несколько алгоритмических языков программирования, т. е. языковых средств, которые используются для составления программ, а также уметь пользоваться соответствующими системами программирования — инструментами, которые непосредственно предназначены для составления и тестирования программ на компьютере с использованием того или иного языка; 4) накопить достаточно большой опыт составления, отладки и тестирования программ (не менее 150—300 задач) из различных областей науки, техники, экономики и других сфер человеческой деятельности. Как приблизиться к выполнению перечисленных требований, с определенной степенью полноты изложено в настоящем учебном пособии. Оно предназначено для учащихся средних специальных заведений, выпускники которых обучаются по специальности 2202 «Автоматизированные системы обработки информации и управления», а также 2203 «Программное обеспечение вычислительной техники и автоматизированных систем». Предисловие
Глава 1 АЛГОРИТМЫ И АЛГОРИТМИЗАЦИЯ 1.1. Определение и представление алгоритмов Слово алгоритм происходит от имени узбекского математика эпохи Возрождения аль-Хорезми, который в IX в. н. э. установил правила четырех арифметических действий над числами в десятичной системе счисления. В Европе эти правила получили название «алгоризм». Затем это слово постепенно преобразовалось в слово «алгоритм» и стало собирательным названием правил, которые применялись не только для выполнения арифметического счета. В течение длительного времени термин «алгоритм» употребляли преимущественно математики, описывая правила решения различных задач. При этом они пользовались так называемым интуитивным понятием алгоритма как способа описания порядка решения той или иной задачи с помощью конечного набора однозначных математических действий. На этом пути были получены ставшие теперь известными правила поиска корней квадратных и кубических уравнений, решения систем линейных и нелинейных уравнений, дифференцирования и интегрирования функций и многие другие правила вычислений. Более того, известна попытка Г. Лейбница найти общий алгоритм решения любых математических задач [1]. Вместе с тем, решая различные задачи, математики столкнулись с рядом неразрешимых проблем, т. е. задач, для которых не удавалось построить решающий их алгоритм. Широко известной из них стала проблема П. Ферма. Существуют ли натуральные числа x, y, z, для которых при целом n 2 справедливо равенство x y z n n n ? Были известны и другие задачи, в частности из области геометрии: о квадратуре круга, удвоении куба и др. [2]. Это побудило математиков более глубоко подойти к
обоснованию сущности алгоритмов и прежде всего формальным, т. е. математическим путем. Основные результаты теории алгоритмов были получены в 30—50-х годах ХХ в. Э. Черчем, А. Тьюрингом, А. Постом, А. Колмогоровым, А. Марковым. Введенные в рассмотренные модели алгоритмов (алгоритмические модели), машины А. Тьюринга, А. Поста дали возможность устанавливать алгоритмическую разрешимость проблемы путем построения соответствующих машин логического действия. Это дало возможность более конструктивно подходить к поиску решения неразрешимых проблем, весьма часто акцентируя внимание на частных ее случаях. Широкое употребление слова «алгоритм» обязано буму кибернетики — науки об управлении и связи в живом и машине, который пришелся на 50-е годы ХХ в. Слово «алгоритм» стало настолько популярным, что его начали применять в различных случаях, весьма далеких от вычислений. Например, алгоритмами стали называть рецепты приготовления и приема лекарств, перехода пешеходом улицы с интенсивным движением транспорта, завязывания шнурков на ботинках и т. п. Дело дошло до абсурда. Появились дикие словосочетания типа «алгоритм изобретения», что означает ни что иное, как конец изобретательства (творческой деятельности). Оставляя в стороне подобного рода алгоритмы, сосредоточим внимание лишь на тех из них, которые описывают решение задач обработки информации на ЭВМ. Построение таких алгоритмов должно удовлетворять ряду принципов. Первое, что следует отметить, — алгоритм применяется к исходным данным и выдает результаты. Иными словами, он имеет информационный вход и выход. Кроме того, в ходе выполнения алгоритма получаются промежуточные результаты, которые могут использоваться в дальнейшем. Таким образом, каждый алгоритм выполняет операции с данными — входными, промежуточными и выходными. Данные должны быть четко определены и отделены от «не данных». Примерами данных, с которыми работают алгоритмы, предназначенные для ЭВМ, являются числа, формулы, векторы, матрицы смежности графов, чертежи, рисунки, фотографии. Не данными являются, например, «хорошая книга» или «логическое утверждение». С этими «не данными» алгоритм работать не будет до тех пор, пока они не будут представлены в форме подходящих данных.
Для универсальности представления данных в алгоритмах используются специальные алфавиты — конечные наборы символов, из которых конструируются слова и предложения. Поэтому считается, что вход алгоритмов — это слова разной длины, определенные в конечном алфавите. Каждый символ алфавита имеет стандартный код определенной длины, занимающий не более восьми двоичных разрядов. В современных ЭВМ символы кодируются при вводе их в ЭВМ с клавиатуры или со сканера. Введенные в компьютер данные размещаются в памяти. Память является дискретной, состоящей из отдельных ячеек. Каждая ячейка может вмещать один символ. Так, что, например, слово ALFA для своего размещения потребует четыре ячейки. Таким образом, физической единицей памяти является ячейка. На логическом уровне единица памяти называется байт. Алгоритм состоит из отдельных элементарных шагов. Причем количество этих шагов должно быть конечно. Это значит, что после выполнения этих шагов алгоритм должен прекратить выполнять действия, т. е. остановиться. Если действия повторяются бесконечно, говорят, что алгоритм зацикливается. Последовательность шагов алгоритма должна быть детерминированной (определенной). Это означает, что после каждого шага либо указывается, какой шаг выполнять дальше, либо дается команда остановки, после этого действия алгоритма считаются законченными. Алгоритм должен удовлетворять условию результативности, т. е. после выполнения конечного количества шагов он должен выдавать правильный результат решения той или иной информационной задачи. Суммируя все перечисленные требования, которым должны удовлетворять алгоритмы обработки информации на ЭВМ, введем следующие определения. Определение 1.1. Алгоритм — это конечная последовательность детерминированных арифметических и логических действий над исходными и промежуточными данными задачи обработки информации, выполнение которых приводит к правильному ее решению, т. е. получению требуемых выходных данных. При этом под исходными данными понимаются только те наборы данных, для которых имеет смысл решаемая задача. По существу алгоритм, определенный на этих данных, преобразует их 1.1. Определение и представление алгоритмов
из исходного вида в результирующую форму, т. е. однозначно ставит результат в соответствие исходным данным. Иными словами, с каждым алгоритмом связана функция, которую он вычисляет. С точки зрения современной практики алгоритм существует только тогда, когда по нему составлена программа для ЭВМ, правильно решающая задачу. Поэтому критерием алгоритмичности некоторой задачи является возможность ее запрограммировать. В настоящее время применяются три способа представления алгоритмов: графический (в виде блок-схем), текстовый (в виде последовательности шагов, описывающих действия естественным языком), программный (в виде программы, полностью или сжато представленной на каком-либо алгоритмическом языке). Графический способ считается наиболее наглядным. Для обозначения различных действий в нем используются специальные геометрические фигуры. С помощью овала показывают начало и конец действий алгоритма. Параллелограмм используется для обозначения ввода исходных данных в память компьютера и вывода результатов решения задачи из него. Прямоугольник применяют для обозначения вычисления выражений, ромб — для показа операций сравнения величин. Согласно последовательности действий фигуры соединяют линиями со стрелками. В результате этого получают орграф с истоком и стоком. Вершинам этого графа соответствуют шаги, ребрам — переходы между шагами. Начальная вершина — исток — указывает начало действий, конечная его вершина — сток — определяет конец действий. Эти вершины являются фиктивными и вводятся специально для показа полноты алгоритма. Определение 1.2. Орграф, вершины которого отображают шаги алгоритма, а дуги — переходы между шагами, называется блок-схемой алгоритма. Важной особенностью блок-схем алгоритмов является то, что связи между вершинами графа не зависят от того, элементарные ли шаги отображены его вершинами или это объединения нескольких шагов (блоки). Поэтому блок-схема алгоритма может быть представлена предельно укрупненно: начало, ввод исходных данных, все действия, вывод результатов, конец действий. Такое представление алгоритма — стандартный прием при разработке программ методом структурного программирования.
При всей наглядности блок-схем алгоритмов они представляют собой достаточно грубое описание действий и отображают лишь связи по управлению, а не по информации. Они не содержат сведений ни о данных, ни о требуемой памяти и, что весьма часто, не содержат последовательности элементарных шагов. По существу, блок-схемы — это средства описания детерминизма алгоритма. Как сообщалось раньше, текстовое представление алгоритмов средствами естественного языка подразумевает пошаговое описание действий. При этом после каждого шага указывается, какой шаг выполнять дальше. Вместе с тем существует соглашение: если шаги алгоритма выполняются в естественном порядке (без пропуска и возвращения назад), переход к очередному шагу может не указываться. Текстовое описание алгоритма так же, как и его блок-схема, не содержит сведений о данных, памяти и может быть представлено весьма укрупненно. Оно лишь требует меньше места для записи алгоритмов. Представление алгоритмов в виде укрупненной программы — индивидуальный продукт каждого автора, который описывает алгоритм. Как правило, для этих целей используются фрагменты каких-либо алгоритмических языков. В описании обычно указываются начальные шаги (инициализация переменных), основные шаги, переходы и циклы, а также обозначаются результаты решения задачи. Полное представление алгоритма в виде программы, возможно, лишь для весьма элементарных и коротких программ. Для иллюстрации описанных методов представления алгоритмов рассмотрим следующую задачу. Необходимо составить алгоритм приближенного вычисления квадратного корня x a с заданной точностью методом Ньютона. Этот метод состоит в том, что очередное значение корня xn вычисляется по реккурентному соотношению x x a x x n n n n 1 1 1 1 2 , n 1, 2, ... при условии, что задано начальное значение корня x0. Тогда первое значение корня будет равно x x a x x 1 0 0 0 1 2 , второе — x2 x1 1 2 1 1 a x x и т. д. Корень будем считать вычисленным 1.1. Определение и представление алгоритмов
с заданной точностью , если модуль очередного уточнения корня 1 2 1 x x n n . Блок-схема алгоритма решения этой задачи приведена на рис. 1.1. Рис. 1.1. Блок-схема алгоритма вычисления квадратного корня методом Ньютона