Мытник Н.П. Основы компьютерного программирования
Подождите немного. Документ загружается.
1.Определение алгоритма. Свойства алгоритмов. Способы описания
алгоритма. Базовые структуры схемы алгоритма. Структурированные
схемы и их построение.
Алгоритм. Конечная последовательность команд исполнителю для выполнения
некоторой работы или решения задачи.
Создание алгоритма, пусть даже самого простого – процесс творческий. Он доступен
исключительно живым существам, а долгое время считалось, что только человеку. Другое
дело – реализация уже имеющегося алгоритма. Ее можно поручить субъекту или объекту,
который не обязан вникать в существо дела, а возможно, и не способен его понять. Такой
субъект или объект принять называть формальным исполнителем.
Каждый алгоритм создается в расчете на вполне конкретного исполнителя. Те
действия, которые может совершить исполнитель, называются его допустимыми
действиями. Совокупность допустимых действий образуют систему команд
исполнителя. Алгоритм должен содержать только те действия, которые допустимы для
данного исполнителя.
Свойства алгоритма. Разработать алгоритм решения задачи означает разбить
задачу на последовательно выполняемые шаги, причем результаты выполнения
предыдущих этапов могут использоваться при выполнении последующих. При этом
должны быть четко указаны как содержание каждого шага, так и порядок выполнения
шагов, т.к. компьютер – формальный исполнитель.
Свойства:
1. Понятность – каждая команда должна быть понятна исполнителю, т.е. входить в
систему команд исполнителя.
2. Дискретность (прерывность, раздельность) – алгоритм должен представлять
процесс решения задачи как последовательное выполнение простых (или ранее
определенных шагов). Каждое действие, предусмотренное алгоритмом,
исполняется только после того, как закончилось исполнение предыдущего.
3. Определенность (детерминированность) – каждое правило алгоритма должно
быть четким, однозначным. Кроме того, в алгоритмах недопустимы также
ситуации, когда после выполнения очередной команды алгоритма исполнителю
неясно, какая из команд алгоритма должна выполняться на следующем шаге.
Благодаря этому свойству выполнение алгоритма носит механический характер и
не требует никаких дополнительных указаний или сведений о решаемой задаче.
4. Результативность Смысл этого требования состоит в том, что при точном
исполнении всех предписаний алгоритма процесс должен прекратиться за
конечное число шагов и при этом должен получиться определённый результат.
Вывод о том, что решения не существует - тоже результат.
5. Массовость – алгоритм должен решать любую задачу из того класса задач, для
решения которых он разработан. При этом исходные данные могут выбираться из
некоторой области, которая называется областью применимости алгоритма.
Например, алгоритм решения квадратного уравнения должен решать любое
квадратное уравнение.
Пример. Дано трехзначное число. Найти сумму его цифр. С этой задачей каждый
справится очень быстро. Суть программирования состоит в том, чтобы научить
формального исполнителя – компьютер, решить эту задачу.
Процедура подготовки и решения задачи на ЭВМ - достаточно сложный и
трудоемкий процесс, состоящий из следующих этапов:
1. Анализ задачи;
2. Разработка и обоснование алгоритма;
3. Выбор и обоснование наборов тестов;
4. Описание разрабатываемых алгоритмов;
5. Выбор представления данных;
6. Кодирование программы(написание программы на языке программирования);
7. Тестирование и отладка;
8. Составление отчета;
Анализ - это исследование объектов или явлений, путем изучения составляющих его
элементов.
Анализ задачи позволяет установить:
Что является входом и выходом будущего алгоритма, при этом следует явно
описывать класс входных данных.
Выделить основные решения между входными и выходными данными.
Выделить модули необходимые для выполнения задачи и определить методы их
решений.
Класс входных данных определяется наложением ограничений. Определение
отношений между входными и выходными данными определяется математической
постановкой решаемой задачи. Содержание постановки задачи - это определение
правильности конечных результатов, т.е. чем содержательней и правильнее поставим
задачу, тем больше вероятность, что программа будет написана правильно, т.е. она будет
делать то, что от нее требуется.
Математическая постановка задачи дает ответ на 4 вопроса:
1. Что дано?
2. Что требуется?
3. Какие результаты будут считаться правильными?
4. Какие данные будут считаться допустимыми?
В разделе Дано - Перечисляются все исходные данные.
В разделе Требуется - Перечисление всех выходных данных с указанием их
названий и математического обозначения.
В разделе 3 - Устанавливается система математических утверждений, связывающая
входные и выходные данные с объяснением каждой записи.
В разделе 4 - Устанавливается система математических утверждений,
накладывающих ограничения на область допустимых исходных данных.
Сценарий работы программы
Сценарий представляет собой описание внешних формул при выполнении
программы.
Сценарий должен разрабатываться после анализа и постановки задачи, в некоторых
случаях после алгоритма.
Требования к сценарию:
1. Простота, т.е.:
2. подсказка на экране
3. сложно сделать ошибку
4. фиксация кадра - смена кадра должна происходить не сразу
5. обычно любая операция должна выполняться после запроса
6. В сценарии описываются:
7. форма ввода исходных данных
8. форма вывода результатов
9. контроль прохождения программы и промежуточного результата при отладке и
если это необходимо
Пример:
Сценарий программы нахождения наиболее удаленных точек.
1. На экран выводится: Введите общее количество точек
2. В ответ пользователь вводит число N
3. N раз на экране повторяется:
Введите координаты i-ой точки x="
Ввод координаты Xi;
К выведенной строке дописывается Y=
Ввод Yi
На экране выводится наиболее удаленные друг от друга точки с координатами
(<Xa>,<Ya>) и (<Xb>,<Yb>)
Данный сценарий не включает контроля ограничения на входные данные.
Выбор представления данных (ВПД)
ВПД - является одним из важных этапов представления программы. В одних случаях
ВПД является решающим и определяет алгоритм. Данные можно разделить на три типа:
1. Входные данные
2. Промежуточные
3. Выходные данные
Входные и выходные данные определяются интерфейсом с пользователем.
Интерфейс - внешнее представления данных. Промежуточные данные определяются
алгоритмом. Входные и выходные данные могут быть представлены в виде внешней и
внутренней формулы. Внешние данные определяются удобством взаимодействия
пользователя с программой, а внутренние удобством для программирования.
Для описания алгоритмов существует множество способов. Основные способы
описания следующие:
- словесный;
- алгоритмический язык;
- схема;
- псевдокод.
Под схемой программы будем понимать графическое представление
последовательности шагов алгоритма, которое наглядно показывает очередность и
взаимосвязь операций, осуществляемых в алгоритме на каждом его шаге.
Иначе говоря, схема программы служит для графического изображения структуры
алгоритма. Любая схема содержит набор геометрических фигур или блоков.
Последовательность действий указывается с помощью стрелок, соединяющих отдельные
блоки.
Основные блоки, используемые при изображении схемы программы:
Блок, обозначающий начало или конец алгоритма.
Функциональный блок.
Логический блок.
Блок, обозначающий операции ввода-вывода.
Изображение цикла
2.Линейные и разветвляющиеся структуры. Циклические структуры.
Типы циклов. Предопределенные процессы. Рекурсия.
Базовые алгоритмические структуры. Используя исходные элементы блок-схем
можно собрать более крупные кирпичики, которые называют базовыми структурами.
Базовые структуры (конструкции):
- следование;
- ветвление (полное и не полное);
- повторение (цикл с предусловием или постусловием);
- вход;
-выход.
Каждая базовая структура имеет один вход и один выход. Схемы основных базовых
алгоритмических структур:
Следование Повторение (Цикл )
т е л о ц и к л а
Ветвление (полное)
у с л о в и е
о п е р а т о р 1 о п е р а т о р 2
д а н е т
Выбор (оператор switch)
у с л о в и е
о п е р а т о р 1
н е т
о п е р а т о р
n + 1
о п е р а т о р 2
о п е р а т о р 3
о п е р а т о р n
3.Модульные программы. Классические методы проектирования
модульных программ
Программирование вообще можно определить как проектирование, кодирование и
тестирование программы.
Структурное программирование это проектирование, написание и тестирование
программы в соответствии с заранее определенной дисциплиной.
Раньше хорошими программистами считали тех, кто писал весьма хитроумные
программы, которые занимали минимум основной памяти и выполнялись за кратчайшее
время. Это было естественно, потому что в старое доброе время основная память была
более дорогой, машины были намного медленнее, чем сегодня. Результатом хитроумного
кодирования оказывались программы, которые трудно было (если не совершенно
невозможно) понять другим лицам. Программисты зачастую сами признавали, что свою
собственную программу они с трудом понимают уже через полгода, а то и через месяц.
Фактически каждая написанная программа впоследствии модифицируется при изменении
внешних требований или для ликвидации ошибок. Изменения, вносимые в запутанную
программу, еще больше усложняют ее понимание впоследствии. Подобные программы
получили название BS-программ (Bowl of Spaghetti блюдо спагетти), так как при попытке
разобраться в них необходимо нарисовать нечто напоминающее блюдо спагетти.
На некотором этапе развития программного обеспечения выяснилось, что разработка
сложных алгоритмов и соответствующих им программ становится практически
неуправляемой. Резко ухудшилась читаемость программ, снизилась эффективность
программ и их надежность, усложнилось тестирование программ, и в итоге, увеличилось
время разработки и стоимость программного продукта.
Исходя из этих проблем, лучшие программисты 70-х годов Э.Дейкстра и Н.Вирт
разработали строгие правила разработки программ, которые получили название
“Методология структурного программирования”. Они рассматривают программу
(алгоритм) как совокупность иерархических модулей, которые позволяют четко
структурировать программу, что улучшает ее понимание программистами, позволяет
выполнять математическое доказательство ее корректности и тем самым повысить
надежность функционирования программ и сократить срок их разработки.
Основные стандарты структурного программирования:
1. Алгоритм (программ) должна разделяться на независимые части,
называемые модулями.
2. Модуль имеет одну входящую и одну выходящую точку.
3. Модуль – это независимый блок, который физически и логически отделен от
других модулей.
4. Каждый модуль начинается с комментария, объясняющего его назначение,
назначение переменных, передаваемых в модуль и из него, модулей, которые
его вызывают, и модулей, которые вызываются из него.
5. В модуле используются только базовые управляющие конструкции
(ветвление, повторение, следование, вход, выход).
6. Вложенность операторов IF не должна быть более трех.
В 1966 году Бом и Якопини доказали следующую теорему: любую блок-схему с
одним входом и одним выходом можно построить, используя базисное множество
базовых структур (следование, ветвление, цикл-пока).
Блок-схема называется структурированной, если она построена на основе
базисного множества базовых структур.
Для построения структурированных блок-схем была разработана специальная
технология, которая называется пошаговой детализацией. Пошаговая детализация
представляет собой процесс дробления задачи на модули, т.е. исходя из общей задачи,
вычленяются подзадачи, устанавливаются логические связи между ними. После этого
переходят к уточнению выделенных подзадач. Этот процесс детализации продолжается до
уровня позволяющего достаточно легко реализовать подзадачу на выбранном языке
программирования.
При пошаговой детализации используется принцип замещения, который состоит в
замене любого функционального блока (прямоугольника) блок-схемы некоторой базовой
структурой (следование, ветвление, повторение) из исходного базисного множества.
Достоинство пошаговой детализации состоит в том, что она позволяет разработчику
алгоритма упорядочить свои рассуждения.
Пример. Построить структурированную блок-схему алгоритма для вычисления
функции
1 - 2 x , е с л и х < 0 ;
1 , е с л и 0 < = x < 1 ;
2 x - 5 , е с л и x > = 1 .
y =
На первом шаге задачу представим в виде одного блока, в котором запишем кратко
условие задачи.
в ы ч и с л и т ь y
На втором шаге функциональный блок преобразуем в развилку, где выделено
вычисление Y при x<0.
п р о д о л ж е н и е
и с с л е д о в а н и я
x и
в ы ч и с л е н и е y
y = 1 - 2 x
x < 0
д а н е т
На последнем шаге функциональный блок предыдущей схемы заменяем развилкой.
н а ч а л о
в в о д х
x < 0
y = 1 - 2 x x < 1
y = 1 y = 2 x - 5
в ы в о д х
к о н е ц
В итоге выполнения нескольких шагов мы получили структурированную блок-схему
алгоритма решения задачи.
4.Нисходящая и восходящая разработка алгоритмов.
Первое важное правило состоит в том, чтобы сначала продумать задачу, которую
необходимо решить. Как только мы хорошо поймем задачу и способ решения задачи
будет нами будет полностью и во всех деталях продуман, само проектирование окажется
быстрым и легким.
Распространенной ошибкой являются попытки начать писать программу до того, как
будет уяснена полная постановка задачи. Основная причина, по которой следует
воздержаться от преждевременного начала программирования, состоит в том, что
обдумывание задачи и поиск метода ее решения должны проводиться в терминах,
наиболее адекватных самой этой задаче. Эти термины чаще всего далеки от синтаксиса
применяемого языка программирования и могут быть утверждениями на естественном
языке и схемами.
Исходная формулировка способа решения задачи должна быть в конечном итоге
преобразована в алгоритм и программу, но этот процесс преобразований млжет оказаться
нелегким.
Нисходящая разработка алгоритма. Суть нисходящей разработки (нисходящего
проектирования, проектирования сверху вниз) состоит в пошаговой декомпозиции
(разложении) задачи на точно определенные подзадачи.
Формальных критериев декомпозиции не существует, поэтому процесс, особенно для
нестандартных задач, является в большой степени творческим и требует навыка и опыта.
Парадоксальным на первый взгляд, но наиболее конструктивным критерием выделения
подзадач является такой: каждая подзадача должна быть сформулирована кратко, точно и
емко («Найти сумму..», «Проверить наличие элементов …» и т.д.).
Процесс разработки является иерархическим. На каждом уровне проектирования
полагаем, что каждая выделенная подзадача реализуема, и, не интересуясь деталями этой
реализации, рассматриваем ее как единое обобщенное действие, называемое абстракцией.
Подзадача некоторого уровня раскрывается на следующем, также путем разложения на
подзадачи – и т.д., до получения подзадач, алгоритм решения которых можно
непосредственно записать на языке программирования.
Ниже приведена общая схема нисходящего проектирования.
На любом уровне проектирования одни элементы алгоритма уже доведены до
исполнительного уровня и могут быть закодированы, другие же представлены в виде
абстракций. Нисходящая отладка представляет собой постепенный процесс отладки
такого незавершенного кода программы на каждом уровне.
В основе ее лежит тот факт, что любая подзадача связана с остальными только своим
интерфейсом, т.е. совокупностью получаемых ею входных данных и передаваемых
дальше выходных данных. Можно взять некоторый тест и вместо операций по решению
подзадачи вставить операции, формирующие соответствующие тесту выходные значения.
Совокупность таких операций называется заглушкой (или имитатором).
Заглушка должна только получить входные данные подзадачи и напрямую
сформировать результаты согласно тесту, поэтому тексты заглушек должны быть
максимально простыми. Подставив вместо подзадач заглушки, мы будем иметь, с одной
стороны, законченную с точки зрения компьютера программу; с другой стороны, ее
результаты работы на рассматриваемом тесте не будут отличаться от результатов
итоговой программы.
Такой процесс отладки дает на каждом уровне два важных результата:
Исходная задача,
абстракция А0
Подзадача
А0.k
Подзадача
А0.2
Подзадача
А0.1
0-й уровень:
исходная задача
1-й уровень: подзадачи
задач 0-го уровня
(абстракции 0-го уровня)
..........
Уровень подзадач,
реализуемых в языке
программирования
(исполнительный)
...........
..
...................................................
................
Общая схема нисходящей разработки
- возможность отладки уже готовых частей программы;
- возможность отладки взаимодействия подзадач, т.е. логики передачи данных между
ними.
При этом то, что уже отлажено, далее меняться не должно, и все усилия можно
сосредоточить на раскрытии еще не решенных подзадач.
Восходящая разработка алгоритма ("снизу-вверх").. Восходящее
программирование - методика разработки программ, при которой крупные блоки
собираются из ранее созданных мелких блоков. Восходящее программирование
начинается с разработки ключевых процедур и подпрограмм, которые затем постоянно
модифицируются.
"Восходящая" разработка характеризует так называемое исследовательское
программирование, когда система строится вокруг ключевых компонентов и программ,
которые создаются на ранних стадиях проекта, а затем постоянно модифицируются.
Отсутствие четкого плана, минимальное управление проектом, большое число
сторонних территориально удаленных разработчиков, свободный обмен идеями и
кодами — все это атрибуты нового программирования. Об особенностях
исследовательского программирования написано немало статей. Так, швейцарские
профессора А.Киральф, К.Чен и Й.Нивергельт выделили следующие важные моменты:
1. разработчик ясно представляет направление поиска, но не знает заранее, как далеко
он сможет продвинуться к цели;
2. нет возможности предвидеть объем ресурсов для достижения того или иного
результата;
3. разработка не поддается детальному планированию, она ведется методом проб и
ошибок;
4. такие работы связаны с конкретными исполнителями и отражают их личностные
качества.
5.Понятие жизненного цикл объекта и абстракции для его
представления
● Жизненный цикл программного обеспечения – это весь процесс его создания и
применения от начала до конца. Этапы жизненного цикла и удельный вес общих затрат на
каждый из этапов приведены на рисунке
Требования
пользователя
1
2
3
5
4
Сопровождение
6
Определение
требований-
спецификаций
Проектирование
Кодирование
Отладка и
тестирование
Документирование
Решение
пользователю