- •Билет 1. Базовые понятия программирования. Действие, процесс, алгоритм, программа.
- •Билет 2. Функциональная структура эвм. Основные устройства эвм, их функциональные характеристики.
- •1972Г – Дейкстра – Книга о базисе и структурированном программировании.
- •Выбор из нескольких альтернатив. Реализация в Pascal.
- •Документирование программы:
- •1. Постановка задачи (спецификация задачи: в спецификации различают две существенно разные ее части: функциональную и эксплуатационную спецификацию.
- •Классификация алгоритмов внутренней сортировки
- •Концепция структурного программирования:
- •Локализация и исправление ошибок в системе отладки
- •Метод деления пополам.
- •Мобильность программ, отличие турбо паскаля от стандартного
- •Надежность программы, организация надежного ввода.
- •Основные декомпазиционные структуры программ
- •Основные правила композиции структурированных программ.
- •Основные стратегии проектируемых алгоритмов
- •Основные действия при отладке
- •Побочный эффект
- •1. Использовать процедуры с параметрами (чистые процедуры), за исключением явных случаев, когда параметры не нужны. Доводы в пользу использования чистых процедур:
- •2. Глобальные переменные в процедуре целесообразно использовать в след. Основных случаях:
- •Правила записи программируемого модуля
- •Скалярные типы данных в языке Pascal.
- •Структурные уровни яп
- •Массивы.
- •Функциональное и структурное тестирование
- •Характеристика восходящих и нисходящих способов отладки
- •Цель и содержание отладки:
- •Чистые процедуры. Правила и способы подстановки параметров
- •Эффективность программы
Основные правила композиции структурированных программ.
Структурированные алгоритмы - это алгоритмы, которые строятся с использованием только трех правил композиции вычислительных действий (3 управляющие структуры):
- последовательные действия (следование);
- альтернативные действия (выбор);
- повторяемые действия (цикл).
Ограничение этими тремя правилами обеспечивает разработку алгоритмов и программ, удовлетворяющих принципу Э.Дейкстры, согласно которому текстуальная упорядоченность программ должна совпадать с порядком их выполнения.
Структурированные алгоритмы и программы легко понимаемы, модифицируемы, в них легче находить ошибки, по ним легче производить анализ правильности программ.
Управляющие структуры образуют базис. Базис Дейкстры: следование, выбор, цикл «пока». Базис Вирта: следование, выбор, цикл «до». Св-ва базиса:
- независимость (каждая из базисных структур не может быть представлена комбинацией 2-х других);
- полнота (любой алгоритм может быть осуществлен с помощью них);
- эквивалентность базисов (следование и выбор сохраняются, а циклы «до» и «пока» взаимозаменяемы).
Основные стратегии проектируемых алгоритмов
Существуют две основные стратегии проектирования алгоритмов: восходящее ("снизу-вверх") и нисходящее ("сверху-вниз") проектирование.
Стратегия "снизу-вверх" основана на принципе наименьших усилий и кажется более естественной. Смысл ее заключается в следующем.
Выделяются те части алгоритма, которые уже можно программировать, и о которых известно, что они точно "понадобятся". Эти части программируются как отдельные модули и отлаживаются. Потом из них, как из строительных блоков, собираются программы-блоки более высокого уровня проектирования, и, наконец, вся программа. Число таких уровней зависит от размера и сложности задачи.
Привлекательность восходящего проектирования заключается в том, что не нужно думать обо всей программной системе и соединении модулей до тех пор, пока этого не протребуется. Наиболее существенный недостаток такой стратегии известен как "проблема интерфейса": при сборке модули системы могут оказаться несогласованными по ряду крупных или мелких деталей. Например, запрограммированный (и локально отлаженный) математический метод не удовлетворяет некоторым требованиям задачи (точности, времени выполнения и т.д.). Несогласование модулей обнаруживается к концу работы над системой, когда она практически завершена. Это откладывает завершение работы на неопределенный срок и препятствует плановой работе над системой.
Альтернативной стратегией является стратегия проектирования алгоритмов "сверху-вниз". Еще на заре программирования эта стратегия использовалась интуитивно суперпрограммистами, являясь залогом их успешной работы. В стратегии заключена идея постепенного раскрытия деталей проектируемой программы по мере движения от общей цели, сформулированной на самом высоком уровне в условии задачи, к уровню объектов, выраженных в терминах "понятных машине".
- Преимущества нисходящей стратегии:
1. Дает лучшее понимание объектов проектирования, так как на каждом шаге выделяются основные понятия, а детали "упрятываются".
2. Делает более простым процесс модификации программы и сокращает
время отладки.
3. Упрощает доказательство корректности программы.
- Трудности нисходящей стратегии.
1. На ранних стадиях должна быть проделана интеллектуальная работа главным программистом, прежде чем программа будет распараллеливаться для всех программистов проекта.
2. Имеется специфика в отладке "сверху-вниз", когда приходится отлаживать программные модули, полностью не завершенные.
Реально процесс проектирования не является простой схемой "сверху-вниз". Иногда приходится вернуться к предыдущему уровню и произвести коррекцию проекта. Умелое сочетание обеих стратегий и составляет искусство проектирования