- •Интернет, как источник информации для разработки пакета программ для курса программирования и основы алгоритмизации
- •Гл2. Интернет, как источник информации для разработки пакета программ для курса программирования и основы алгоритмизации
- •Глава 1 Cправка языков программирования
- •§1 Справка языков программирования
- •§2 Историческая справка развития Delphi
- •Целевая платформа
- •История языка
- •Компиляторы
- •Синтаксис языка Операторы
- •Выражения
- •Типы данных
- •Объекты
- •§3 Обзор методов алгоритмов
- •1.3. Основные этапы полного построения алгоритма
- •2.Построение модели
- •3.Правильность алгоритма
- •4.Реализация алгоритма
- •5.Анализ алгоритма и его сложности
- •§4 Программа Delphi, обьектно-ориентированное программирование
- •Краеугольные камни ооп Формула объекта
- •Природа объекта
- •Объекты и компоненты
- •Классы объектов
- •Три кита ооп
- •Объекты
- •Конструкторы и деструкторы
- •Свойства Понятие свойства
- •Методы получения и установки значений свойств
- •Свойства-массивы
- •Свойство-массив как основное свойство объекта
- •Методы, обслуживающие несколько свойств
- •§5 Общая структура пакета программирования и алгоритмитизации
- •1. Алгоритмизация и алгоритмы
- •1.1 Понятие алгоритмизации и алгоритмов
- •1.2 Свойства алгоритмов
- •2. Программирование
- •2.1 Понятие программирования
- •2.2 Понятие компьютерной программы
- •§6 Инструкция для Программы htm2chm
- •Введение
- •Эволюция средств разработки Web приложений в Delphi Средства разработки Internet-приложений §1. Средства разработки Internet-приложений из состава Borland Kylix
- •§2 Средства разработки Internet-приложений из состава Borland Delphi 6
- •§3. Форматы приложений для web
- •§5. Разработка web приложения
- •П2. Использование шаблонов
- •§6. Первый проект
- •П2 Использование tAdapter
- •П3. Работа с базами данных
- •§7. Использование Web Services
- •П2. Протокол soap
- •П3. Разработка сервера Web Services в Delphi6
- •П4. Описание интерфейса сервера
- •П5. Реализация методов сервера
- •П6. Создание проекта приложения Web Services в Delphi
- •П7. Разработка клиента Web Services в Delphi6
- •Заключение
3.Правильность алгоритма
Доказательство правильности алгоритма — это один из наиболее трудных, а иногда и особенно утомительных этапов создания алгоритма.
Вероятно, наиболее распространенная процедура доказательства правильности программы — это прогон ее на разных тестах. Если выданные программой ответы могут быть подтверждены известными или вычисленными вручную данными, возникает искушение сделать вывод, что программа «работает». Однако этот метод редко исключает все сомнения; может существовать случай, в котором программа не сработает.
Мы предложим следующую общую методику доказательства правильности алгоритма. Предположим, что алгоритм описан в виде последовательности шагов, скажем, от шага 0 до шага т. Постараемся предложить некое обоснование правомерности для каждого шага. В частности, может потребоваться лемма об условиях, действующих до и после пройденного шага. Затем постараемся предложить доказательство конечности алгоритма, при этом будут проверены все подходящие входные данные и получены все подходящие выходные данные.
Пример. Алгоритм ETS настолько прост, что его правильность легко доказать. Поскольку проверяется каждый тур, должен быть проверен и тур с минимальной стоимостью; как только до него дойдет очередь, он будет запомнен. Он не будет отброшен — это может случиться только в том случае, если существует тур с меньшей стоимостью. Алгоритм должен закончить работу, так как число туров, которые нужно проверить, конечно. Подобный метод доказательства известен как «доказательство исчерпыванием»; это самый грубый из всех методов доказательства.
Подчеркнем тот факт, что правильность алгоритма еще ничего не говорит о его эффективности. Исчерпывающие алгоритмы редко бывают хорошими во всех отношениях.
4.Реализация алгоритма
Как только алгоритм выражен, допустим, в виде последовательности шагов и мы убедились в его правильности, настает черед реализации алгоритма, т. е. написания программы для ЭВМ.
Этот существенный шаг может быть довольно трудным. Во-первых, трудность заключается в том, что очень часто отдельно взятый шаг алгоритма может быть выражен в форме, которую трудно перевести непосредственно в конструкции языка программирования. Например, один из шагов алгоритма может быть записан в виде, требующем целой подпрограммы для его реализации. Во-вторых, реализация может оказаться трудным процессом потому, что перед тем, как мы сможем начать писать программу, мы должны построить целую систему структур данных для представления важных аспектов используемой модели. Чтобы сделать это, необходимо ответить, например, на такие вопросы:
Каковы основные переменные?
Каких они типов?
Сколько нужно массивов и какой размерности?
Имеет ли смысл пользоваться связными списками?
Какие нужны подпрограммы (возможно, уже записанные в памяти)?
Каким языком программирования пользоваться?
Конкретная реализация может существенно влиять на требования к памяти и на скорость алгоритма.
Другой аспект построения программной реализации —• это программирование сверху - вниз. Объяснение этого понятия будет дано в разд. 2.1, а пока укажем, что программирование сверху - вниз — это подход к разработке и реализации, который состоит в преобразовании алгоритма в такую последовательность все более конкретизированных алгоритмов, что окончательный вариант представляет собой
программу для ЭВМ.
Сделаем одно важное замечание. Одно дело — доказать правильность конкретного алгоритма, описанного в словесной форме. Другое дело — доказать, что данная машинная программа, предположительно являющаяся реализацией этого алгоритма, также правильна. Таким образом, необходимо очень тщательно следить, чтобы процесс преобразования правильного алгоритма (в словесной форме) в машинную программу «заслуживал доверия».
Советуем читателю снова рассмотреть алгоритм ETS в свете обсуждения в данном подразделе и постараться построить его по этапам, как было предложено, пока вы не получите машинную программу.