Проектирование корректных структурированных программ: Пер. с англ./М.: Радио и связь, 1984. - 264 с., ил.
1 р. 50 к.
™f^ посвящена основам структурного программирования и методам доказательства корректности программ. Обобщены результаты исследований, на которых базируется современная методология проектирования программ сверху вниз. Изложение ориентировано на язык Паскаль. Даны практические рекомендации и примеры проек-тирования программ. F«C*.
Для широкого круга читателей: от начинающих программистов до специалистов в области кибернетики и вычислительной техники, для студентов и аспирантов при изучении методологии программирования
ПРЕДИСЛОВИЕ К РУССКОМУ ИЗДАНИЮ
Каждый из нас в детстве учился на волшебника. Действительно, иначе как колдовством, трудно было считать непостижимое умение решать арифметические задачи. Недаром великий хорезмиец IX в. Мухаммед аль-Хо-резми, которому мы обязаны словами "алгоритм" и "алгебра" и который научил людей систематически составлять и решать квадратные уравнения, имел-в своем полном имени, напоминающем нынешний листок по учету кадров, вставку "аль-Маджуси", т.е. "из магов".
И правда, детскому уму с его конкретным и мгновенным видением мира было трудно вчитываться в микроновеллы о поездах, мчащихся навстречу друг другу, или о трубах, зачем-то одновременно вливающих и выливающих воду из бассейна. Ему было трудно извлечь из этой смеси слов и цифр таинственный ПЛАН, который шаг за шагом приближал бы к желанному ответу. Чувствовалось, что бы ни говорил учитель - план надо УГАДАТЬ, при этом самое трудное — начать.
Каждый знает, каким замечательным открытием оказывалось такое великолепное по своей простоте и могуществу правило. Представь, что то, о чем спрашивается "сколько", у тебя есть. Обозначь это "сколько" буквой х, перепиши условие задачи, при этом замени слова "сложить", "умножить", "равно", "больше" уже знакомыми знаками, а потом забудь про трубы и поезда, километры и килограммы. То, что получится, называется "уравнениями". И тогда начинается новая игра, со своими тайнами и заботами, на основе другого упорядоченного, строгого, но достоверного математического знания.
Искусство программирования, как оно развивалось до последнего времени, во многом напоминает волшебство решения арифметических задач. И там и здесь надо угадать план, и там и здесь труднее всего начать, потому что если знаешь как сделать первый шаг, то эта же схема верна и для каждого следующего. Надо только уметь видеть, как влияет первый шаг на формулировку задачи.
Книга С. Алагича и М. Арбиба пытается научить читателя составлять и решать уравнения для программ. Она тоже начинается с правила: предположим, что программа у тебя есть, обозначь ее как-то и запиши, какими свойствами обладают ее аргументы и соответствующие им результаты; то, что получится, и есть уравнение для программы. Язык программирования при этом становится списком правил, показывающих-, какие свойства связывают "аргументы" и "результаты" каждого элементарного кусочка программы — оператора.
ОГЛАВЛЕНИЕ
Стр.
Предисловие к русскому изданию.........:........................3
Предисловие авторов к русскому изданию............................5
Предисловие...............................................6
Глава 1. Введение в проектирование сверху вниз.......................8
1.1. Идея проектирования сверху вниз...............................8
1.2. Пример: наибольший общий делитель над..........................9
1.3. Язык программирования и машинный язык.........................15
Глава 2. Основные композиции действий и их правила вывода.............19
2.1. Соотношения для корректности программ.........................19
2.2. Логические выражения и выражения языка Паскаль...................23
2.3. Правила вывода для простых операторов..........................30
2.4. Составные и условные операторы..............................31
2.5. Операторы итерации.......................................36
2.6. Основные правила вывода................................... 39
2.7. Использование основных правил вывода..........................40
2.8. Корректное завершение алгоритмов.............................48
Библиографические замечания...................................52
Упражнения...............................................53
Глава 3. Типы данных.................................... . . 56
3.1. Введение..............................................56
3.2. Основы теории множеств.................................... 58
3.3. Скалярные и простые типы..................................62
3.4. Массивы, записи и файлы....................................72
3.5. Обработка массивов.......................................87
3.6. Обработка файлов и записей..................................93
3.7. Работа с множествами в Паскале..............................102
Библиографические замечания..................................108
Упражнения. ...........................,..................108
Глава 4. Разработка программ с доказательством их корректности.........112
4.1. Введение.............................................112
4.2; Квадраты и палиндромы................................... 113
4.3. Сортировка массивов и фалов............................... 120
4.4. Работа с множествами...................................... 137
Библиографические замечания.................................. 147
Упражнения.......•.'...;................................. 147
Глава 5. Процедуры и функции................................148
5.1- Процедуры и блочная структура.............•.................148
5.2. Функции и доказательство их корректности.......................159
5.3. Доказательство корректности процедур.........................166
Библиографические замечания.................................. 176
Упражнения..............................................177
263
Глава 6. Рекурсия........................................180
6.1. Введение.............................................180
6.2. Проектирование и корректность рекурсивных процедур...............186
6.3. Рекурсивные типы данных.................................. 195
6.4. Рекурсивные алгоритмы и рекурсивные структуры данных.............206
Библиографические замечания.....................,............209
Упражнения..............................................210
Глава 7. Использование goto в программировании....................215
7.1. Операторы goto.........................................215
7.2. Правила вывода для операторов goto...........................219
7.3. Выходы типа возврат и алгоритм Find........................... 223
7.4. Выходы в связи с неудачей и алгоритм Lookup.....................229
7.5. Циклы с выходами в середине...............................232
Библиографические замечания..................................238
Упражнения..............................................239
Приложение 1. Синтаксис Паскаля................................241
Приложение 2. Правила вывода.................................255
Список литературы.........................................258
Список литературы, переведенной на русский язык.....................262
Список дополнительной литературы..............................262
Цена: 150руб.
