Тема 1 Паскаль: Формализация и алгоритмизация вычислительных процессов


Лекция Р_1.

Тема: Формализация и алгоритмизация вычислительных процессов

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

План лекции

1.  Этапы решения задачи.

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

3.  Алгоритм и его свойства.

4.  Основные типы алгоритмов.

1. Этапы решения задачи.

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

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

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

Математическая формулировка задачи завершается выбором метода ее решению.

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

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

Четвертый этап — программирование, то есть запись составленного алгоритма на языке программирования.

В современном программировании существует несколько подходов к программированию: структурное (детальное), модульное и объектно-ориентированное программирование.

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

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

Модульное программирование использует методологию, ориентированную на обработку. Его основные признаки:

— каждый модуль реализует одну и только одну независимую функцию;

— каждый модуль имеет единую точку ввода-вывода;

— размер модуля нужно минимизировать;

— каждый модуль может быть записан на языке программирования разработчиком или программистом и может быть протестирован отдельно;

— вся программа состоит из протестированных модулей и поэтому именно легко проверяется.

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

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

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

Читать  Одномерные массивы – Понятие массива и его свойства, инициализация массива

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

Пятый этап — тестирование и отладка программы — это проверка правильности работы программы на компьютере и исправления найденных в ней ошибок.

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

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

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

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

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

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

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

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

В зависимости от способа перевода с входного языка (языка программирования) трансляторы делятся на Компиляторы и Интерпретаторы.

В компиляции процессы трансляции и выполнения программы разделены во времени. Интерпретатор осуществляет трансляцию и немедленное выполнение каждого оператора исходной программы. Исходный язык программирования называется На языке высокого уровня относительно машинного языка — Языка низкого уровня.

Читать  Введение и вывод значений величин | Составляющие алгоритма обработки величин

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

3. Алгоритм и его свойства.

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

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

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

Пример 1.вычислить

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

1.  Выполнить вычитание 92 — 32 и запомнить результат (60).

2.  Выполнить сложение 309 + 51 и запомнить результат (360).

3.  Выполнить деления 360: 60 и запомнить результат (6).

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

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

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

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

Рассмотрим таких исполнителей: человека, работа и компьютер.

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

2.  Количество команд для механических исполнителей значительно меньше. Например: вперед, направо, налево — это допустимые команды работа. Робот не выполняет таких команд, как есть или пить.

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

4.  Команды, которые не может выполнить исполнитель, называются недопустимо.

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

1.  словесный;

2.  формульный;

3.  графический;

4.  алгоритмической языке.

Рассмотрим общий вид алгоритма.

Алгоритму даем название, команды нумеруем. Название пишем с большой буквы. Итак, алгоритм будет выглядеть так:

Алгоритм. Название

1.  Команда 1.

2.  Команда 2.

3.  Команда 3.

N. Команда n.

Читать  Лекция Паскаль 5 – Понятие операции и выражения, Арифметические и строчные операции

Пример 2. Составим алгоритм перехода улицы.

Алгоритм Переход

1.  Посмотреть налево.

2.  Если нет препятствия, то идти до середины улицы,

Иначе пропустить машины,

Идти к середине улицы.

3. Посмотреть направо.

4. Если нет препятствия, то завершить переход,

Иначе пропустить машины,

Завершить переход.

Рассмотрите алгоритм. Команды 1 и 3 называть простыми, а 2 и 4 — составными.

Вопрос. Можно ли в алгоритме поменять любые две команды местами, будет новый алгоритм правильным?

3.3. Характеристики алгоритмов.

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

Неопределенность. Например, возникнет в алгоритме 1, если в знаменателе будет записано: 92 — 92 (деление на ноль не допустимо).

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

Алгоритм 1 конечный. Он состоит из трех действий. Каждое действие реализуется конечным количеством элементарных арифметических операций. Бесконечное количество действий предусматривает правило перевода некоторых обыкновенных дробей, таких как 5/3, в бесконечные десятичные дроби.

Результативность алгоритма. Алгоритм результативный, если он дает результаты (которые могут оказаться и неправильными). Приведенные выше алгоритмы являются результативными.

Правильность алгоритма. Алгоритм правильный, если его выполнение обеспечивает достижение цели.

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

Формальность алгоритма. Алгоритм формальный, если его могут выполнить не один, а несколько исполнителей с одинаковыми результатами. Это свойство еще называют однозначностью алгоритма.

Приведенные алгоритмы удовлетворяют это условие. Их могут выполнить многие исполнители.

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

Алгоритм 1 не массовым. Алгоритм Переход является массовым: так нужно переходить все улицы.

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

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

Пример 3. Составим алгоритм решения линейного уравнения.

Запишем линейное уравнение в общем виде:

Аx + b = c.

Метод решения описывает формула

Х =

Эту формулу можно рассматривать как алгоритм, который применим для любых чисел a, b и с, где а ¹ 0.Поэтому он является массовым.

4. Основные типы алгоритмов.

4.1. Блок-схемы.

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

1.  Операция обработки, присваивание

2. Операция ввода-вывода

3. Операция проверки условий

4. Вывод на печать

5. Конец и начало программы

В литературе можно встретить и другие фигуры.

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

Читать  Таблица и ее элементы, табличные величины

Блок-схемы алгоритмов принято читать слева направо и сверху вниз. В блок-схемах преобладают вычислительные и логические блоки: первые вычисляют по формулам (их изображают прямоугольниками с указанием характера вычислений), а вторые — проверяют некоторые условия. Указания об исчислении задают по-разному. Алгоритм любой задачи заключается в предельные символы (овалы) «начало» и «конец». Первым в алгоритме выполняется блок к которому ведет стрелка от блока «начало»; заканчивается вычислительный процесс блоком «конец». Таким образом, линия потока выходит из символа «начало» и входит в блок «конец». Между этими двумя блоками размещаются все остальные блок-схемы. Никаких строгих правил разбиения алгоритма на отдельные блоки при построении схем не существует. В блоки можно выделять выполнения отдельных арифметических операций, вычисления по формулам и даже отдельные алгоритмы, которые решают более узкие классы задач. На следующих этапах алгоритмизации некоторые из блоков можно подробнее детализировать, оформив их в виде отдельных схем.

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

4.2. Типы алгоритмов.

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

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

Рис.1

ИИ. Линейные алгоритмы (следования).

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

Пример 1. Рассмотрим алгоритм Утро.

Алгоритм Утро.

1.  Встать в 6 часов

2.  Выполнить гимнастические упражнения.

3.  Умыться.

4.  Позавтракать.

5.  Выйти из дома в 7 часов.

Это пример линейного алгоритма.

ИИИ. Разветвленные алгоритмы.

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

Пример 2. Составить схему алгоритма начисления подоходного налога П, когда известно, что
П = 0, если Z £ 60,
0,082 * Z, если 60 <Z £ 100,
0,082 * 100 + 0,13 * (Z — 100), если Z> 100,

Где П — подоходный налог, Z — заработная плата.

Решение. В зависимости от значения заработной платы Z подоходный налог П можно вычислить по одной из трех веток. Строя алгоритм, надо воспользоваться двумя последовательными разветвлениями в двух напряках: сначала отделим первый случай (Z £ 60) от двух следующих, а затем — второй от третьего, проверяя условие Z £ 100 (рис.2)

Читать  Лекция Паскаль 7 – Виды операторов цикла, Поиск суммы и произведение последовательности чисел

IV. Циклические алгоритмы.

Циклические алгоритмы позволяют получить результат многократным повторением определенной последовательности действий, называются Циклом.Если число повторений цикла задано, то такие циклы называют Арифметическими. Если количество повторений цикла заранее неизвестно, а определяется только в процессе применения алгоритма, то такие циклы называют Итерационными.

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

Пример 4. Вычислить значение суммы

S = 1 + 2 2 + 3 2 + 4 2 + … + n 2.

Решение. В этом алгоритме операторы 2-3 подготавливают вычислительную часть цикла (операторы 4-5) для выполнения первого вычисления. Они составляют подготовительную часть циклического алгоритма. Операторы 4-5 в процессе применения алгоритма выполняются n раз и дают возможность вычислить искомую сумму S. При каждом выполнении цикла значение переменной k увеличивается на единицу, а значение S — на k 2.Проверка окончания цикла выполняется с помощью оператора условного перехода путем сравнения числового значения счетчика цикла k с заданным числом n — эталоном цикла. Выполнение цикла повторяется до выполнения условия k = n (рис. 3).

Цикл может быть двух видов: цикл Пока, цикл К.

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

В цикле К функциональный блок А размещается к проверке логического условия Р. В этом случае тело цикла выполняется хотя бы один раз (рис.5).

Цикл Пока цикл К  Рис. 4 Рис. 5

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

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

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

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

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

Вспомогательные алгоритмы (подпрограммы).

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

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

Пример: Алгоритм день

1.  Выполнить алгоритм Утро.

2.  Выполнить алгоритм Техникум.

3.  Выполнить алгоритм Вечер.

[Всего голосов: 3    Средний: 5/5]