Главная >> Монографии

Pages: |

| 2 | 3 | 4 | 5 | ... | 6 |

«Издательство Мир Москва 1982 ББК 32.973 М 45 УДК 681.142.2 М45 Мейер Б., Бодуэн К. Методы программирования: В 2–х томах. Т.1. Пер. с франц. Ю.А. Первина. Под ред. и с предисловием А. П. Ершова.–М.: Мир, 1982 356 с. ...»

-- [ Страница 1 ] --

Б. МЕЙЕР, К. БОДУЭН

МЕТОДЫ

ПРОГРАММИРОВАНИЯ

Перевод с французского

Ю. А. ПЕРВИНА

под редакцией

А. П. ЕРШОВА

Издательство «Мир» Москва 1982

ББК 32.973

М 45

УДК 681.142.2

М45 Мейер Б., Бодуэн К.

Методы программирования: В 2–х томах. Т.1. Пер. с франц. Ю.А. Первина. Под ред. и с предисловием А. П. Ершова.–М.: Мир, 1982 356 с.

Монография французских ученых, в которой систематически излагаются основные понятия информатики, обсуждаются трудные проблемы методологии программирования, дается сравнение известных языков программирования: ФОРТРАНа, АЛГОЛа W, ПЛ/1 и др. Изложение сопровождается упражнениями (с решениями).

В русском переводе книга разбита на два тома. В первый том (гл. I–V) наряду с общими сведениями о программировании рассмотрены основные свойства базовых языков программирования и управляющие структуры, а также обсуждаются подпрограммы и структуры данных.

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

ГЛАВА II. ВВЕДЕНИЕ В ЯЗЫКИ ПРОГРАММИРОВАНИЯ

ФОРТРАН, АЛГОЛ W, ПЛ/1

II.1. Основные характеристики

II.1.1. Значения и типы

II.1.1.1. Литеры

II.1.1.2. Строки

II.1.1.3. Логические значения

II.1.1.4. Целые числа

II.1.1.5. Дробные числа («вещественные»)

II.1.1.6. Комплексные числа

II.1.2. Основные объекты: константы, переменные, массивы, выражения

II.1.2.1. Константы

II.1.2.2. Переменные

II.1.2.3. Массивы

II.1.2.4. Выражения

II.1.3. Программы, операторы

II.2. Алгоритмическая нотация

II.3. Введение в ФОРТРАН

II.3.1. История

II.3.2. Значения и типы

II.3.3. Основные объекты языка

II.3.3.1. Константы

II.3.3.2. Переменные. Символические константы

II.3.3.3. Массивы

II.3.3.4. Выражения

II.3.3.5. Обработка строк в ФОРТРАНе

II.3.4. Программы, операторы

II.3.4.1. «Работа» ФОРТРАНа и «программные модули»

II.3.4.2. Физическая форма программы

II.3.4.3. Некоторые операторы

II.4. Введение в АЛГОЛ W

II.4.1. История

II.4.2. Значения и типы

II.4.3. Основные объекты языка

II.4.3.1. Константы

II.4.3.2. Переменные

II.4.3.3. Массивы

II.4.3.4. Выражения

II.4.4. Программы, операторы

II.4.4.1. Физическая форма программы

II.4.4.2. Некоторые операторы

II.5. Введение в ПЛ/1

II.5.1. История

II.5.2. Значения и типы

II.5.3. Основные объекты языка

II.5.3.1. Константы

II.5.3.2. Переменные

II.5.3.3. Массивы

II.5.3.4. Выражения

II.5.4. Программы, операторы

II.5.4.1. Физическая форма программы

II.5.4.2. Некоторые операторы

Библиография

УПРАЖНЕНИЯ

ГЛАВА III. УПРАВЛЯЮЩИЕ СТРУКТУРЫ

III.1. Введение

III.2. Обозначения

III.2.1. Состояние программы

III.2.2. Блок–схемы

III.3. Базовые структуры

III.3.1. Циклы

III.3.1.1. Бесконечный цикл

III.3.1.2. Циклы, управляемые условиями (типа пока и до)

III.3.1.3. Цикл с параметром

III.3.2. Ветвления

III.3.2.1. Альтернатива

III.3.2.2. Многозначное ветвление

III.3.3. Цепочка

III.3.4. Подпрограммы

III.3.5. Композиции базовых структур

III.3.6. Управление с помощью таблиц

III.4. Свойства базовых структур: введение в формальную обработку программ

III.4.1. Введение и обозначения

III.4.2. Свойства цепочки

III.4.3. Свойства альтернативы

III.4.4. Свойства цикла

III.4.5. Заключение

III.5. Представление управляющих структур в ФОРТРАНе, АЛГОЛе W и ПЛ/1

III.5.1. Цепочка

III.5.2. Циклы

III.5.2.1. Бесконечный цикл

III.5.2.2. Циклы пока и до

III.5.2.3. Цикл со счетчиком

III.5.3. Ветвления

III.5.3.1. Альтернатива

III.5.3.2. Многозначные ветвления. Таблицы переходов

III.6. Обсуждение: управляющие структуры и систематическое программирование

БИБЛИОГРАФИЯ

УПРАЖНЕНИЯ

ГЛАВА IV. ПОДПРОГРАММЫ

IV.1. Введение

IV.2. Определения и проблемы обозначений

IV.2.1. Определения

IV.2.2. Определение и вызов; формальные параметры, фактические параметры

IV.2.3. Проблемы обозначений; подпрограммы «операторы» и «выражения»

IV.2.4. Тип подпрограммы

IV.3. Введение в использование подпрограмм в ФОРТРАНе, АЛГОЛе W, ПЛ/1

IV.3.1. Подпрограммы в ФОРТРАНе

IV.3.1.1. Подпрограммы–«выражения»

IV.3.1.2. Подпрограммы–«операторы»

IV.3.1.3. Замечания о подпрограммах ФОРТРАНа

IV.3.2. Подпрограммы в АЛГОЛе W

IV.3.3. Подпрограммы в ПЛ/1

IV.4. Способы передачи информации между программными модулями

IV.4.1. Проблема

IV.4.2. Чистое чтение: передача значением

IV.4.3. Чистая запись, передача результата

IV.4.4. Чтение и запись: значение–результат, адрес, имя

IV.4.5. Передача массивов

IV.4.6. Передача подпрограмм

IV.4.7. Резюме

IV.5. Обобществление данных

IV.5.1. Определение

IV.5.2. Языки блочной структуры

IV.5.3. Методы ФОРТРАНа: понятие общей области

IV.6. Подпрограммы и управление памятью

IV.6.1. Свободные переменные; массивы с фиксированными при выполнении границами...... IV.6.2. Статическое и динамическое распределения

IV.6.3. ФОРТРАН

IV.6.4. АЛГОЛ W

IV.6.5. ПЛ/1

IV.6.6. Реентерабельность. Многократное использование. Побочный эффект

IV.7. Расширения понятия подпрограммы

IV.7.1. Иерархическая структура вызовов подпрограмм

IV.7.2. Пример использования сопрограмм

IV.7.3. Обсуждение и заключение

УПРАЖНЕНИЯ

ГЛАВА V. СТРУКТУРЫ ДАННЫХ

V.1. Описание структур данных

V.1.1. Уровни описания

V.1.2. Функциональная спецификация

V.1.3. Логическое описание; смежность; разделение случаев; перечисление

V.1.4. Физическое представление. Понятие указателя

V.1.4.1. Разделение вариантов, перечисление

V.1.4.2. Соединение

V.1.5. Обсуждение. Проблемы

V.2. Структуры данных и языки программирования

V.2.1. Записи и ссылки в AЛГОЛe W

V.2.2. Структуры и указатели в ПЛ/1

V.2.3. Сравнение АЛГОЛа W и ПЛ/1

V.2.4. Методы ФОРТРАНа

V.3. Множества. Введение в систематику структур данных

V.4. Стеки

V.4.1. Введение. Применения

V.4.2. Функциональная спецификация

V.4.3. Логическое описание

V.4.4. Физическое представление

V.4.4.1. Сплошное представление

V.4.4.2. Цепное представление

V.4.4.3. Конкретное представление стеков в ПЛ/1

V.4.5. Расширение понятия стека

V.5. Файлы

V.5.1. Введение. Применения

V.5.2. Функциональная спецификация

V.5.3. Логическое описание

V.5.4. Физическое представление

V.5.4.1. Цепное представление

V.5.4.2. Сплошное представление

V.5.5. Обобщение: файл с двойным доступом

V.6. Линейные списки

V.6.1. Введение. Применения

V.6.2. Функциональная спецификация

V.6.3. Логическое описание

V.6.4. Физические представления

V.7. Деревья, двоичные деревья

V.7.1. Деревья: определение и применения

V.7.2. Введение в двоичные деревья

V.7.3. Преобразование дерева в двоичное дерево

V.7.4. Функциональная спецификация

V.7.5. Логическое описание

V.7.6. Физическое представление

V.7.6.1. Цепное представление

V.7.6.2. Сплошное представление

V.8. Списки

V.8.1. Введение. Применения

V.8.2. Функциональная спецификация

V.8.3. Логическое описание

V.8.4. Списки, деревья, двоичные деревья

V.8.5. Физическое представление

ФОРТРАН

V.9. Массивы

V.9.1. Функциональная спецификация

V.9.2. Логическое описание

V.9.3. Физическое представление

V.9.4. Представление разреженных массивов

V.9.5. Массивы и языки: дополнения

V.10. Графы

V.10.1. Определения. Графические представления

V.10.2. Физическое представление конечных графов

БИБЛИОГРАФИЯ

ЗАДАЧИ

ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕИЗДАНИЯ

С момента выхода книги прошло уже 30 лет, но, перечитывая ее, понимаешь, что классика бессмертна. Всё, что здесь написано, актуально и по сей день, и будет актуально, пока существует программирование.

В далёком 1983-м году я, 18-тилетним парнем, пришел работать в одно ПКБ. Это была эра большим машин (ЕС ЭВМ, если еще кто помнит). Реальный мир программирования оказался слишком далёким от того, что преподавали в институтах.

Оказалось, что на производстве не перемножали и даже не складывали матрицы! Зато мне выдали распечатки одного САПР на ФОРТРАНе, которые весили килограмм 5–6. В них то я и углубился. Программы были написаны в стиле того времени – идеально выровнены по 7-й колонке, без единого комментария и со всякими интересными трюками, как то GOTO во внутрь цикла и т.п. САПР был не очень популярный, спроса на него не было, и что бы заполнить свободное время, я решил заняться самообразованием и заглянул в техническую библиотеку ПКБ. И среди всевозможных справочников, задачников и учебников по ФОРТРАНу я случайно наткнулся на «Методы программирования».

Эта книга перевернула моё представление о программировании. Всё встало на свои места. Программирование вместо какого–то шаманства превратилось в строгую математическую дисциплину, где действуют свои законы. Находясь под сильным впечатлением от книги и не имея доступа к алголоподобным языкам (на тот момент использовались ФОРТРАН IV, КОБОЛ и ПЛ/1), я даже написал препроцессор для ФОРТРАНа на самом же ФОРТРАНе, который реализовывал все базовые управляющие структуры, описанные здесь (скажу сразу, что символьная обработка на ФОРТРАНе IV – занятие не для слабонервных).

В начале 90-х дни ПКБ были сочтены, пора было менять работу. Книга осталась в библиотеке. После этого я неоднократно возобновлял безуспешные попытки найти ее в продаже. Со второй половины 90-х я стал разыскивать ее в Интернете. В лучшем случае можно было оформить предварительный заказ (без гарантии, что он будет исполнен) на каком-нибудь книжном сайте. И на запрос: «Мейер Б. Бодуэн К. Методы программирования» поисковые службы выдавали тысячи ссылок, но все они были либо сообщениями в форумах, либо (что наиболее распространено) ссылками на литературу в университетских курсах.

Книга на русском языки вышла в 1982 году тиражом всего в 30 000 экземпляров (что для СССР очень мало). Да еще очень ненадёжный переплёт (кто держал эту книгу в руках знают). Так что к этому времени, очевидно, осталось очень мало живых экземпляров.

Судя по всему, переизданием этой книги с 82-го года не занималось ни одно издательство. Сейчас книжные магазины ломятся от литературы по информатике, но, к сожалению, там очень проблематично найти книги, подобные этой. Зато масса книг типа «Освой Java за 21 день», «C/C++ для хакеров», «Delphi изнутри» и т.д., где тщательно рассматриваются возможности получить доступ к private полям классов, создания «круглых» форм и прочие трюки, которые, по большому счету, к программированию не имеют никакого отношения. А вот книги подобной этой, которые закладывают самые основы программирования, встретить на прилавках книжных магазинов весьма проблематично.

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

Работа над книгой была нелёгкой – всякий, кому хотя бы раз приходилось сканировать, распознавать, форматировать и кое–где исправлять 700 страниц текста с таблицами, примерами и массой математических формул, поймёт меня. Сначала я хотел отделаться минимумом – оставить все в таком формате, в каком был оригинал.

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

Так же я позволил себе по ходу дела исправить кое–какие ошибки и неточности, которые, очевидно, были внесены уже в процессе перевода и вёрстки. К середине второго тома устал не только я, но, судя по всему, и те, кто выпускал книгу в 82-м году.

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

ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА

Разрыв между последними достижениями информатики и повседневной практикой программирования, между трудностью задачи программирования и примитивностью доступного арсенала средств, между головокружительным прогрессом оборудования и инертностью программного обеспечения, по–видимому, нарастает с каждым годом. Именно это положение вещей обсуждалось во время дискуссии, посвященной проблеме подготовки квалифицированных программистов 80-х годов, которая стала одним из наиболее ярких событий недавно прошедшего в Японии и Австралии Всемирного конгресса ИФИП–80. Признавая кризисное состояние практики программирования и демонстрируя широкий спектр мнений по поводу актуальной проблематики, участники дискуссии были, однако, единодушны в своей уверенности в «светлом будущем программирования»; они пришли к заключению, что достичь его можно лишь путем тщательно подготовленного всеобщего и интенсивного курса обучения, не только охватывающего сумму технических приемов, но в определенном смысле формирующего саму личность программиста.

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

Мейера и К. Бодуэна. Она опирается на уже вошедшие в практику преподавания концепции многоязыкового или, правильнее сказать, надъязыкового подхода к обучению программированию. Используя в качестве своего рода языка спецификаций неформально описанные языковые конструкции «высокого уровня», авторы весьма подробно показывают, как эти конструкции реализуются в распространенных алгоритмических языках, выбрав из них типичные представители: ФОРТРАН, ПЛ/1 и АЛГОЛ W. Авторы сумели, не выходя из контекста реального языка, внушить читателю оптимизм в его стремлении научиться хорошо составлять программы, не дожидаясь создания «идеальных» языков программирования.

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

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

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

Интересна активная позиция авторов, направленная на преодоление американской традиции, доминирующей сейчас во многих аспектах программирования – от терминологии до методологических положений.

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

Академгородок,

ПРЕДИСЛОВИЕ

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

В течение последних нескольких лет информатика – исследование автоматической обработки информации, и в частности проблем, связанных с принципами и применениями ЭВМ, – мало–помалу формируется в самостоятельную науку, которая объединяет несколько более или менее независимых дисциплин. Одна из таких дисциплин – программирование (область, в недавнем прошлом еще мало исследованная и подвластная лишь «фанатикам битов и микросекунд») – стала предметом многочисленных систематических исследований и достигла определенной степени формализации.

Наряду с попытками исследователей построить теорию программирования возникло новое явление, несколько умерившее энтузиазм, с которым пользователи ЭВМ встречали бурное развитие возможностей вычислительных машин. Значительное увеличение скорости вычислений и емкости запоминающих устройств многим давало надежду, что они смогут решать задачи постоянно растущих размеров и сложности;

иллюзия подкреплялась еще тем, что программирование поначалу не было очень сложным делом: инженер или служащий мог быстро, не получая специальной подготовки по информатике, выучить необходимые ему в практической деятельности основные элементы такого языка, как ФОРТРАН или КОБОЛ, и «прокрутить»

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

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

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

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

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

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

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

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

рассматриваемые примеры иной раз были оторваны от повседневной практики вычислительных центров; наконец, их нормативный и догматический тон отталкивал профессионалов–практиков.

Главный постулат, принятый в нашей книге, состоит в том, что одни и те же задачи ставятся как в научном, так и в производственном аспекте. Наша цель – убедить читателя той и другой ориентации в том, что программа на ФОРТРАНе может быть «хорошей» или «плохой». Даже будучи убежденными в достоинствах, например, СИМУЛЫ 67, мы полагаем, что абсурдно изгонять из программистского рая подавляющее большинство пользователей, не имеющих доступа к транслятору с этого языка. Наша книга представляет собой компромисс: мы пытались быть точными, не позволяя себе углубляться в чисто теоретические рассуждения.

В нашем изложении мы будем опираться в основном на три языка: АЛГОЛ W, ФОРТРАН и ПЛ/1. Первый из них дает хороший образец ясности в описании алгоритмов, второй является наиболее распространенным языком для научных и инженерных задач, третий стремится объединить возможности числовой обработки и действий с данными, которыми оперируют в задачах управления производством. Мы будем также эпизодически обращаться к некоторому анонимному языку уровня ассемблера; наконец, принципы и алгоритмы будут введены с помощью более абстрактной алгоритмической нотации, приведенной в приложении А.

Нас могут упрекнуть в таком выборе; попытаемся оправдать его, остановившись вкратце на исключенных нами из рассмотрения языках. Наиболее важный из них – КОБОЛ, язык, может быть, еще более, чем ФОРТРАН, распространенный в «реальном мире» информатики. Он обладает оригинальными особенностями с точки зрения структурирования данных. Однако жесткость его управляющих структур и многословие, к которому он вынуждает программиста, делают изнурительным описание всякого сколько-нибудь сложного алгоритма. С другой стороны, самые интересные из его качеств унаследованы языком ПЛ/1. Среди других оставленных нами в стороне языков – ЛИСП, который, несмотря на свой теоретический универсализм, имеет ограниченное применение (основные идеи ЛИСПа, однако, вводятся в гл. V и VI); более глубокое, чем у нас, изучение ассемблеров привело бы к акцентированию внимания на какой–нибудь конкретной машине и усложнило введение алгоритмических понятий. Наконец, в семействе АЛГОЛа, которое дает лучшие образцы «структурированных» языков, мы могли бы выбрать СИМУЛУ 67, АЛГОЛ или ПАСКАЛЬ, у каждого из которых свои особые достоинства. Мы остановились на АЛГОЛе W, используемом во многих университетах. Он сохранил основные черты своего «предка» – АЛГОЛа 60 и вместе с тем вводит важнейшие понятия, представленные в языках последнего времени, в частности структурирование данных.

При этом язык остается простым и легко изучаемым.

Разумеется, эта книга не является учебником по ФОРТРАНу, АЛГОЛу W или ПЛ/1, и библиография адресует читателя к специальным пособиям. Тем не менее в ней рассмотрены основные свойства этих языков, достаточные для обычного программирования: базовые – в гл. II, другие – по мере того, как они становятся необходимыми или позволяют проиллюстрировать важную задачу. Мы хотели таким образом избежать путаницы, которая могла бы возникнуть в результате конкурирующего употребления трех языков; мы стремились также дать возможность читателю, знающему например, ФОРТРАН, но не знакомому ни с АЛГОЛом W, ни с ПЛ/1, на простых примерах приобщиться к тем преимуществам, которые открывают эти два последних языка. Научиться разбирать новый язык программирования относительно просто и всегда полезно для тех, кто уже знает другой язык.

Следует заметить, что описание свойств языков программирования занимает относительно много места, несомненно больше, чем мы этого хотели, потому что некоторые свойства объясняются непросто. Существует некоторая тенденция, пытающаяся полностью освободить курс программирования от изучения языков: это отрицательная реакция на появление многочисленных учебников, посвященных введению в программирование, которые зачастую представляют собой только описание того или иного языка и основное внимание в которых уделяется нетипичным свойствам этого языка; не желая возвращаться к крайностям прежних времен, мы считаем, однако, опасным не дать программисту возможности овладеть основным орудием – его средством выражения. Важно, например, описать критерии, позволяющие выделять «разумные» подмножества языка–то, что мы делаем в этой книге по отношению к ФОРТРАНу, АЛГОЛу W и ПЛ/1, – и вынести сравнительные суждения о различных языках. Можно заметить также, что сами спорные свойства языка часто отражают наличие лежащей в их основе принципиальной проблемы.

После первой главы, знакомящей с начальными понятиями информатики и программирования, во второй главе вводятся основные элементы обычных языков программирования, в частности ФОРТРАНа, АЛГОЛа W и ПЛ/1, а затем даются основы алгоритмической нотации высокого уровня, которая используется во всей оставшейся части книги для разъяснения конструкций и описаний программ. В гл. III рассматриваются управляющие структуры, т.е. основные схемы, которые позволяют описать ход автоматических вычислений. В гл. IV обсуждается одно из центральных понятий в информатике – подпрограммы; акцент здесь сделан на проблемах информационной связи подпрограмм и на методах управления локальными данными, здесь же вводится понятие сопрограммы. Гл. V посвящена изложению понятия структур данных и описанию важнейших из них (стеки, файлы, деревья, графы и т.п.);

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

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

Эта книга в принципе предназначена читателям, уже имеющим некоторый опыт в информатике, в том числе (хотя это и необязательно) и в одном из используемых здесь языков; и все же она была задумана как совершенно независимое целое в том смысле, что все используемые понятия в ней же и определены. Таким образом, и новичок сможет извлечь из книги пользу, если он согласится с временными «пробелами» в изложении некоторых понятий, строгое определение которых дается после их первого использования. Книга может также служить пособием по языкам программирования, алгоритмам, методологии программирования и т.д.

Особое внимание мы уделяем терминологии. По–видимому, информатика больше, чем какая–либо другая наука, перегружена американской терминологией. За исключением нескольких официально принятых терминов, в словаре информатики царит полная анархия; примером, достаточно ясно иллюстрирующим жаргон, употребляемый некоторыми специалистами по информатике, может служить одна брошюра, выпущенная крупной фирмой–производителем ЭВМ, в которой английские «locks» и «interlocks» соседствуют с французскими «espaces–adresses» и с франко– английским «systeme processor».

Мы надеемся, что нам удалось почти везде избежать лингвистической англомании, более или менее признанной в среде специалистов в области информатики (в приложении Б можно найти словарь основных терминов английского происхождения), так что ни «информатика», ни «вычислительная машина» не будут раболепными переводами английских слов 1.

Все содержащиеся в этой книге программы, кроме коротких демонстрационных примеров, были проверены на машине. Мы старались соблюдать правила каждого языка, которым пользовались; одно исключение из этого принципа – в ФОРТРАНе – будет в соответствующем месте отмечено.

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

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

Библиографические ссылки в квадратных скобках, такие, как [Люка 73], относятся к библиографии в конце книги. Они встречаются в тексте и, кроме того, в конце каждой главы.

Библиография не претендует ни на беспристрастность, ни на полноту; приводимые ссылки есть результат выбора, по необходимости субъективного. Кроме того, мы не пытались систематически давать ссылки на хронологически первые публикации результатов, алгоритмов и т.д., когда более поздние работы оказывались легче понимаемыми или более доступными 1.

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

Трудно поблагодарить всех тех, чья помощь и влияние были для нас определяющими, и при этом не связать с ними имеющиеся неудачи и промахи. Мы хотели бы все же, уточнив, что все недостатки этой книги – наши, засвидетельствовать нашу признательность коллегам, которые нам помогли, прочитав рукопись и сделав полезные замечания, и всем тем, чьи идеи мы заимствовали в ходе многочисленных плодотворных дискуссий. Это Ж.–Р. Абриаль, А. Отэн, А. Боссави, Г. Бриссон, П. Казо, М. Демюин, М. Достатни, Г. Гайа, М. Галинье, Ж.П. Грегуар, П. Грессей, Л. Яфиль, И.

Кербар, Д. Лангле, Б. Л. Оже, У. Люка, А. А. Мейер, П. Мулен, Ж. Рандон, Ж. П. Руи, Д. Спон, Ж. М. Триллон и М. К. Вилларем; особенно мы благодарим Л. Болье и Д. Тибо за все полезное, что мы извлекли из совместной подготовки обзорного курса по «общей информатике» в Эколь Насиональ Сюперьор де Телекомюникасьон и К. Кэзера за такую же работу в Институте Информатики Предприятия. Некоторые фрагменты этой книги были использованы для преподавания в этих двух вузах и в фирме Электричество Франции; мы благодарим других преподавателей и слушателей этих курсов за сотрудничество (особенно Д. Жало из ЭНСТ, который обнаружил ошибку в гл. VII). Наконец, мы выражаем свою глубокую признательность Управлению научных исследований фирмы Электричество Франции и Сервис ИМА, которые создали обстановку, позволившую подготовить эту книгу, а также Р. В. Флойду, Д. Е. Кнуту и Д. Маккарти, чьи книги дали решающий импульс всей нашей работе.

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

ОБЩИЕ СВЕДЕНИЯ О ПРОГРАММИРОВАНИИ

I.2 Что такое информатика?

I.3 Что такое информация?

I.4 Что такое вычислительная машина?

I.5 Что может делать вычислительная машина?

I.6 Что такое программирование?

I.7 Несколько ключевых слов12F I.8 Краткая история информатики13F В этой главе изложены основные понятия, необходимые для понимания программирования:

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

Перевод Н. М. Демуровой.

У большинства наших современников всякий намек на «информатику» или «вычислительную машину» вызывает инстинктивную, из глубины души возникающую реакцию, в которой обнаруживается серьезная озабоченность. Перечень наиболее широко распространенных суждений по поводу информатики 1 можно было бы свести к нескольким основным темам: тема неизбежного господства машины над человеком («с этими машинами мы скоро будем не нужны»); тема картотек и ведомостей («мы стали просто номерами»); тема ошибки («с тех пор, как платежи идут через машину, все мои счета неверны»); тема Голема или «ученика чародея», порождающего события, ход которых он не может остановить («робот покорит человека!»); тема всемогущего предвидения («всего х франков за ваш гороскоп, составленный вычислительной машиной!» – «наша ЭВМ предпочитает Красавца на скачках в ближайшее воскресенье»).

Цель этой главы совсем не в том, чтобы дать ответ на приведенные выше суждения или опасения, которые они выражают. Мы хотели бы показать, с одной стороны, возможности, открываемые информатикой, а с другой – ее пределы с той достоверностью, которая убедила бы читателя в том, что вычислительные машины не заслуживают чаще всего «ни этих почестей, ни этого презренья», как сказал Расин; что они представляют собой хотя и мощные, но в то же время очень примитивные орудия;

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

I.2. Что такое информатика?

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

Теория, обработка информации («Информатика») Принимая во внимание кавычки, которые окружают слово «информатика», наш марсианин сказал бы себе наверняка, что тут речь идет о каком–то тонком и немного туманном понятии, пугающем даже составителей словарей. Может быть, он обратился бы тогда к «общественному мнению» и получил бы, вероятно, два типа определений:

«Автоматическая обработка информации» и «наука о вычислительных Даже придя к компромиссу типа «наука об обработке информации с помощью вычислительных машин», он вынужден был бы определять два новых понятия:

«информация» и «вычислительная машина».

Двузначность этого определения есть следствие более глубокого дуализма, который был характерной чертой информатики с самого ее начала. Говорить об информации – это значит акцентировать внимание на человеческих аспектах информатики; сказать «наука о вычислительных машинах» – значит настаивать на важности машины. В течение тридцати лет с тех пор, как программируют на ЭВМ, продолжает оставаться открытым вопрос: человек ли должен приспосабливаться к машине или наоборот? Другими словами, как объяснял Шалтай– Болтай: «вопрос в том, кто из нас здесь хозяин, вот в чем вопрос».

Заинтересованный двусмысленным характером слова «информатика» – слова Естественно, что этот набор примеров отражает французские реалии повседневной жизни.– Прим. ред.

французского происхождения, встречающегося и в немецком, и в русском 1, – наш марсианин мог бы обратиться и к другим языкам. Он констатировал бы, что вообще существуют два соперничающих выражения: одно из них, принятое в основном в университетах, означает науку о вычислительных машинах (Computer Science, Computerwissenschaft, Science des ordinateuers); другое, употребляемое в инженерной среде, – обработка информации; Electronic Data Processing (EDP), Datenverarbeitung. Это балансирование между двумя полюсами – машиной и человеком –вскрывает принципиальную двойственность.

Что можно извлечь из этих семантических колебаний? Прежде всего, что для человека, желающего понять, что такое информатика, эти два слова – «информация» и «ЭВМ» – являются, конечно, ключевыми словами; два следующих раздела соответственно посвящены изучению этих понятий. Далее, что главная проблема информатики состоит в необходимости перейти от человеческих понятий к механическому представлению. Методы программирования, развиваемые в этой книге, в некотором смысле есть не что иное, как средства, предназначенные для облегчения этого разъяснения.

I.3. Что такое информация?

Будем называть информацией всякий критерий выбора среди элементов некоторого множества, т.е. всякий критерий, позволяющий сократить множество, в котором разыскивается ответ на некоторый конкретный вопрос. Если, например, задача ставится так: «Какое слово самое длинное во французском языке?», то полезной информацией будут высказывания: «длина разыскиваемого слова больше 5» и «разыскиваемое слово является наречием». Эти сведения позволяют, действительно, сократить поиск сначала до множества слов длиной больше 5, затем до подмножества предыдущего множества, сформированного исключительно из наречий (т.е. множества наречий длиной больше 5). На этом этапе сведения о том, что разыскиваемое слово не является глаголом, не несут «информацию» в собственном смысле этого слова (или несут нулевое «количество информации»), так как это не позволяет еще раз сократить множество поиска – никакое французское слово не является одновременно глаголом и наречием.

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

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

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

Обработка информации в том виде, в котором она была только что рассмотрена, есть практическая реализация функции f сокращения информации, функции, отображающей (рис. 1.1) множество D, называемое множеством данных, в множество Говоря о многозначности слова «информатика» в русском языке, следует отметить еще одно (при этом более раннее) его употребление в области, связанной с документалистикой и информационно–поисковыми системами.

(См., например, Михайлов А. И., Черный А. И. Основы информатики. –М.: Наука, 1968.) – Прим. ред.

R, называемое множеством возможных результатов, таким образом, что каждому данному d, принадлежащему D, функция f ставит в соответствие результат r = f(d), принадлежащий R.

Рис. I.1 Обработка информации.

Вообще говоря, более соответствует реальности рассмотрение D как множества, называемого в математике «декартовым произведением», т.е. каждое «данное» в действительности составляется объединением нескольких элементарных данных (их «соединением» в том смысле, в котором этот термин будет употребляться в гл. V). Так, множество температур, замеренных каждый час в течение дня в октябре 1977 г., составит одно данное для функции, вычисляющей месячный максимум температур.

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

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

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

I.4. Что такое вычислительная машина?

I.4.1. Общие положения Тот же словарь «Пти Робер» определяет ЭВМ как «электронный вычислитель, снабженный памятью и сверхскоростными средствами вычислений, умеющий адаптировать собственную программу к условиям работы и принимать сложные решения».

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

Чтобы выполнить обработку информации, надо, как мы видим, осуществить применение рассматриваемой функции f к некоторому данному (возможно, сложному), которое принадлежит множеству D.

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

Чтобы «промоделировать» f, необходимо располагать тремя физическими представлениями (Рис. I.2):

- D', физическим представлением множества данных D;

- R', физическим представлением множества результатов R;

- f, физическим представлением функции обработки f, которое должно быть преобразованием или последовательностью преобразований, оперирующих над D' и дающих в результате элемент R'; Г должна быть практически реализуемой, т.е. должна «вычисляться» на некотором физическом Чтобы выполнить обработку информации и интерпретировать ее результат, необходимо располагать, кроме того, двумя кодами представлений и (Рис. I.2):

позволяет представить данное из D (абстрактное) с помощью элемента из D' (физического): это входной код;

позволяет интерпретировать элемент из R', результат автоматической обработки, в качестве представления результата, принадлежащего R: это Рис. I.2 Обработка информации на вычислительной машине.

Программа обработки информации, реализуемой функцией f, является, таким образом, данным, составленным из элементов, физически представимых (конструируемых) множеств D' и R', кодов и и автоматизируемого преобразования f ', таких, что для всякого данного х (принадлежащего D) имеет место ЭВМ позволяет получить такие физические представления. Принципиально машина состоит из двух частей (Рис. I.2):

- центрального процессора – совокупности электронных (иногда электромеханических) устройств, позволяющих «выполнить» f ';

- памяти, физической системы, которая в зависимости от ситуации будет интерпретироваться как D' или R'.

Последнее положение требует некоторых пояснений. Память – это средство представления «информации», т.е., как было показано, элементов из некоторых множеств; Память вычислительной машины есть физическая система с большим числом состояний; каждое состояние может быть связано (в этом состоит роль и ) с элементом какого–либо множества.

Практически используемые системы, т.е. системы, в которых можно эффективно различать их состояния, имеют только конечное число состояний; иными словами, множества D и R всегда представимы конечными множествами. Это одна из фундаментальных черт информатики: рассматриваемые множества конечны; когда говорят о бесконечных множествах, речь идет о некоторой удобной для рассуждений идеальной конструкции; эти множества будут аппроксимироваться иногда «большими»

подмножествами, но всегда конечными.

Рис. I.3 Вычислительная Рис. I.4 Память (так называемая машина.

Удобно представлять память как множество из N физических систем с М состояниями (лучше, чем представление ее единой системой с MN состояниями);

каждая из таких систем называется словом, и память организуется из множества N слов (Рис. I.4).

В современной технике обычными для М являются значения от 28 = 256 до (примерно 1018), а для N – начиная с нескольких тысяч.

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

- целое натуральное число между 0 и М–1 включительно;

- целое положительное, отрицательное или нуль между – m и m включительно - слово 1 из р букв обычного алфавита 2, если 26р М, Как функционирует второе устройство на Рис. I.2 – центральный процессор, которому поручено выполнение операций, составляющих f '? Конкретная вычислительная машина должна иметь конечное число физически реализованных, «встроенных», базовых выполняемых операций: одна из главных идей создателей информатики состояла, таким образом, в том, что с помощью некоторого кода можно было указать соответствие между множеством возможных операций центрального процессора и словом (или частью слова). Это и составляет принцип вычислительной машины с хранимой программой, по которому элементы памяти могут содержать информацию, представляющую в равной степени данные (элементы из D), результаты (элементы из R), а также операторы, выбранные среди операций, которые может выполнять машина 3. В отличие от предшествовавших специализированных вычислительных машин (как, например, суммирующая машина Паскаля) ЭВМ является универсальной машиной, способной выполнять все виды преобразований f, которые представляются как последовательность f' операций, выполняемых обрабатывающим устройством. Одна и та же ЭВМ становится, таким образом, поочередно или даже одновременно переводчиком, математиком, инженером: для этого достаточно (мы еще часто будем употреблять это выражение – «для этого достаточно!») уметь выражать представляемые функции в терминах элементарных выполняемых преобразований.

«Слово» имеет здесь свой обычный смысл, а не «информатический», определенный несколько выше.

Французский алфавит насчитывает 26 букв; для русского читателя обычным можно было бы считать алфавит из букв, и тогда неравенство этой фразы должно было бы иметь вид 32р M – Прим. перев.

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

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

Понятие машины с хранимой в памяти программой приводит к уточнению нашей схемы ЭВМ (Рис. I.5).

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

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

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

Современные машины имеют от одного до нескольких десятков регистров.

Рис. I.5 Вычислительная машина (так называемая модель фон Неймана).

I.4.2. Подробнее о памяти До сих пор очень кратко было сказано о том, что такое «физические системы с конечным числом состояний», которые образуют слова памяти. Теперь пора приоткрыть край занавеса.

В силу очевидного естественного закона, о котором можно было бы долго рассуждать, наиболее легко используемыми физическими системами являются почти всегда двоичные, т.е. элементы с двумя возможными состояниями. Такой элемент называется «бит» (binary digit, двоичная цифра). Безразлично, как называть два этих состояния: 0 и 1, + и –, истина и ложь, Пат и Паташон 1...

Разумеется, для того чтобы слово могло изображать используемую информацию, оно должно иметь более двух возможных состояний. Оно становится, таким образом, комбинацией битов: действительно, система, образованная из n элементов, где у каждого элемента – два состояния, сама имеет 2n возможных состояний.

В оригинале – Лорель и Арди, два очень известных на Западе кинокомика, весьма заметно различающихся своими габаритами. – Прим. перев.

Размер слова, n, является характеристикой каждой ЭВМ и изменяется в достаточно широких пределах при современном состоянии техники. Наиболее обычные значения n = 8,16,24,32,48,60,64,....

В силу многообразия возможных размеров слов для измерения «объемов памяти» часто прибегают к более мелким единицам измерения: байт, множество из битов (система с 28 = 256 состояниями) или литера, единица более расплывчатая (6, или 8 битов). Отметим попутно обозначения «К–байт», «К–слов» и т.д. для обозначения размеров памяти, где «К» означает «кило» (тысячу), но «тысячу»

несколько особую, 210 = 1024: степени двойки удобны для некоторых операций.

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

- механические системы, примером которых может служить перфокарта: на пересечении конкретной строчки и конкретной колонки карты находится элемент в двух возможных состояниях, состояние «проперфорированное» и состояние «непроперфорированное». Классическая перфокарта есть множество из 80 колонок, в каждой из которых 12 элементов такого типа.

Перфоленты подчиняются аналогичному принципу;

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

I.4.3. Ввод–вывод Если вернуться теперь к нашей логической схеме обработки информации (Рис.

I.6), то способ, которым вычислительная машина поможет нам представить D', R' и f', должен показаться более ясным. Чтобы успешно выполнить вычисления f, мы должны еще уточнить, что такое – входной код и – выходной код. Другими словами, остается уточнить, как можно сообщить машине способ преобразования внешней формы данных (D) во внутреннюю (D'), затем внутренней формы результатов (R') во внешнюю форму (R). Под «внутренней» и «внешней» формами здесь подразумеваются «машинная» и «человеческая» соответственно.

Рис. I.6 Обработка информации.

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

Различают - устройства ввода или чтения, которые позволяют передать информацию в память машины. Примеры: устройство чтения с перфокарт или перфолент, лентопротяжный механизм, магнитный диск, клавиатура подключенной к ЭВМ пишущей машинки, оптическое читающее устройство, устройство чтения магнитных карт и т.д.;

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

печатающее устройство, выходной ленточный или карточный перфоратор, магнитная лента или магнитный диск, телетайп, экран терминала, перо графопостроителя, органы управления программно–управляемым станком и т.д.

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

На Рис. I.7 мы дополнили схему вычислительной машины периферийными органами, связанными с ЭВМ устройствами обмена, которые могут обслуживать сразу несколько периферийных устройств.

Рис. I.7 Вычислительная машина I.4.4. Оперативная память, внешняя память В рассматривавшейся до сих пор классической модели вычислительной машины, называемой моделью фон Неймана 1, память образована из N элементов, или слов, пронумерованных от 0 до N–1; «номер» слова называется его адресом. В этой модели все слова эквивалентны в том смысле, что время доступа к слову (время, необходимое для его передачи из памяти в общий регистр или в регистр команд) практически не зависит от адреса (для определенности, это время может иметь порядок миллионной доли секунды на современных ЭВМ).

Этот тип памяти (для которого техника использует обычно ферритовые сердечники или полупроводники) практичен, но дорог. Поэтому ее предназначают для «ядра» вычислительной машины, в котором она составляет главную, или оперативную память.

В современных вычислительных системах объем оперативной памяти варьируется от 8К–байтов на малых машинах до нескольких тысяч К–байтов на больших системах (напомним, что 1 байт это набор из 8 бит и что К = 1024). Если Джон фон Нейман (1903–1957), математик, логик и физик, родившийся в Венгрии. Существуют «модели» более развитые, чем «машина фон Неймана». Они отличаются, в частности, доступом к памяти, которая рассматривается необязательно как однородное множество совершенно одинаковых слов.

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

а) время доступа, как правило, существенно больше;

б) главное, это время не постоянно: время, необходимое для перемещения слова, зависит от места, из которого выполнялось предыдущее перемещение.

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

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

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

I.4.5. Порядок некоторых величин В таблице Рис. I.8 даны порядки величин быстродействия различных устройств.

В качестве единицы обмена информации принята одна литера.

Еще раз подчеркиваем, что речь идет о порядке величин, а не о точных значениях; точные числа в данном случае значат меньше, чем их относительные величины.

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

- выполнение оператора (машинной команды): несколько сотен наносекунд, т.е. несколько десятимиллионных долей секунды;

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

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

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

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

миллисекунд (приблизительно 30 мс для диска) до многих десятков секунд (полная перемотка ленты). Порядок, в котором организуется доступ к элементам, является здесь существенным;

- пересылки электромеханические: читающий перфоратор, алфавитно– цифровое печатающее устройство; скорости порядка тысячной доли секунды на литеру, т.е. значительно ниже, чем на предыдущем уровне;

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

Чаще всего было бы предпочтительно не знать эти физические ограничения и считать, что существует единая память большого размера с переменным временем доступа. И если мы все же отмечаем эти величины, то только потому, что различие их весьма существенно. Например, отношение между временем доступа к некоторому данному в оперативной памяти (примерно 10–6 с) и временем доступа к непосредственно следующему уровню, диску (5010–3с. с учетом среднего времени подвода) равно примерно 50000; можно сравнить программиста с ремесленником, который располагает полкой, вмещающей 20 инструментов, в метре от себя и складом, способным разместить 1000 инструментов, но расположенным в 50 километрах! Ясно, что в таких условиях выбор рядом хранящихся элементов является решающим – даже если системы, называемые в программировании виртуальной памятью (I.7), освобождают частично сегодняшнего программиста от этого бремени.

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

пересылка Карточный перфоратор автоматический 3 миллисекунды Рис. I.8 Порядок некоторых величин.

I.5. Что может делать вычислительная машина?

Чтобы дополнить наше представление об ЭВМ и ее реальных возможностях, остается уточнить (немного) природу пресловутых «базовых операций» центрального процессора, тех, из которых, как говорилось выше, можно составлять программы.

Можно подразделить эти операции, называемые командами или операторами «машинного языка», на четыре большие категории, которые следуют, впрочем, из структуры ЭВМ.

Ниже предполагается, что каждая команда описывается постоянной частью, «кодом», и переменной, «адресной» частью. Различают:

а) Вычислительные команды, или команды обработки, выполняемые арифметическим устройством над величинами, обычно содержащимися в общих регистрах: сложение, логическое И, исключающее ИЛИ и т.д. (Рис.

б) Команды обмена информацией между памятью и арифметическим устройством: загрузка в регистр содержимого некоторого слова (номер регистра и адрес слова указываются в переменной части команды) или Рис. I.9 Сложить содержимое регистра 1 и содержимое слова по адресу Код операции двоичной Рис. I.10 Заслать в регистр 3 содержимое слова по адресу 293.

в) Команды проверки. Обычно команды выполняются одна за другой в порядке адресов программы; команда проверки позволяет указать, что если проверено некоторое условие, то следующая команда вопреки обычному порядку должна быть разыскана по адресу, заданному в адресной части команды. «Условие» может быть, например, равенством содержимого двух Рис. I.11 «Передать управление» команде, являющейся значением слова по адресу 3, если содержимое регистра 2 равно слову по аресу 242; иначе перейти к Команды ввода и вывода, задающие обмен информацией между оперативной памятью и периферийными устройствами.

Самое поразительное в этих командах, существующих в таком виде в современных ЭВМ, это их предельная простота и, если так можно выразиться, их предельная слабость: речь идет в конечном итоге о примитивных манипуляциях над какими–то битами, весьма далекими от задач, решаемых на машине. Самое меньшее, что можно сказать, это констатировать, что существует пропасть между «Вычислить дату ближайшего лунного затмения, наблюдаемого в Мурманске» и «Загрузить содержимое ячейки с адресом 2324 в регистр 5». Эта дистанция – одна из больших проблем программирования, которое можно определить как искусство использовать мощность вычислительных машин, чтобы превратить в «интеллект» предельную ограниченность отдельных команд.

I.6. Что такое программирование?

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

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

г) Увеличенные возможности человеческих ошибок в программах и трудоемкость процессов поиска и исправления ошибок.

д) Тесная зависимость между программой и машиной, на которой она выполняется, зависимость, делающая почти невозможным переход на е) Проблема разделения: для современных ЭВМ характерно, что несколько программ выполняются одновременно на одной и той же машине; жизненно необходимо поэтому уметь контролировать разделение «ресурсов»

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

Некоторые из этих проблем, например а) или в крайнем случае е) или ж), могут быть решены применением системы кодирования, позволяющей программисту записывать команды символически в содержательных обозначениях. Так, вместо команды Рис. I.10 можно писать в формализме, называемом языком ассемблирования (в противоположность «языку» команд машины, или машинному языку):

ПРИСВОИТЬ X = 293 ЗАГРУЗИТЬ X R Специальная программа, называемая ассемблером, которой оснащены почти все вычислительные машины, берет на себя перевод написанных выше строк в команду Рис. I.10.

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

Чтобы выполнить программу Р, написанную на таком языке программирования L, надо сделать его понятным машине. Важно знать два метода, которые позволяют получить этот результат:

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

Рис. I.12 Выполнение методом интерпретации.

б) В методе компиляции выполнение программы включает две фазы; первая есть перевод программы Р в эквивалентную программу F, выраженную в машинном языке; этот перевод выполняется специальной программой, которая называется компилятором. Второй этап – это выполнение результирующей программы Р' с данными D (Рис. I.13).

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

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

Рис. I.13 Выполнение методом компиляции.

Рис. I.14 Языки программирования.

В настоящее время в мире существуют несколько сотен языков программирования. На Рис. I.14 показаны некоторые из наиболее важных языков с указанием их «родства» и влияний. Одним из первых языков программирования был ФОРТРАН (1956), который остается одним из наиболее используемых, несмотря на его достаточно примитивный стиль.

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

I.7. Несколько ключевых слов Для понимания следующих глав будут необходимы определения нескольких основных терминов программирования.

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

ordinateur), программное обеспечение (анг. software и франц. logiciel), техническое обеспечение (англ. hardware и франц. materiel) и т.д. Французские программисты устояли перед соблазном взять ранее родившиеся американские термины и предложили свою, краткую и даже более выразительную терминологию. – Прим. перев.

процессор, периферийные устройства и т.д.), составляющих вычислительный комплекс.

Программисты фамильярно зовут его «железом». Употребляется в качестве противопоставления понятию программного обеспечения.

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

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

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

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

Искусственный интеллект: исследования методов, позволяющих передать автоматическим машинам (и, в частности, ЭВМ) решение задач, традиционно рассматриваемых как достояние человеческого интеллекта: анализ естественных языков; исследование и доказательства математических теорем; «интеллектуальные»

игры; манипуляции объектами в меняющейся обстановке (роботы) и т.д.

I.8.

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

I.8.1. Прединформатика Идея использования материальных носителей для обработки больших объемов данных, несомненно, очень стара. Кнут [Кнут 72], например, видит применение принципов автоматической обработки информации в числовых таблицах на вавилонских глиняных горшках, датируемых 2500 г. до н.э. Обычно в качестве предка современных счетных устройств упоминают также древние китайские счеты (ранее г. до н.э.).

Ближе к нашему времени, в эпоху Возрождения и средние века начали появляться механические и полумеханические вычислительные устройства. Непер изобретает логарифмы в начале XVII в.; в 1620 г. появляется счетная линейка. Два Это резюме навеяно в числе других [Хаски 76].

гения своего времени предлагают оставившие заметный след в истории машины, выполняющие арифметические операции: Паскаль в 1642 г. (сложение и вычитание) и Лейбниц в 1671 г. (четыре операции). Множество различных машин появляется затем, вплоть до начала XIX в.

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

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

Более века спустя англичанин Бэббидж предложил в 1822 г. свою «дифференциальную машину», а позднее, в 1833 г. «аналитическую машину», настоящую модель вычислительной машины с центральным процессором (mill, «мельница») и памятью (store, «склад»). Машина Бэббиджа осталась, однако, нереализованным замыслом, а почти все его идеи независимо «переоткрывались» в сороковые годы нашего века.

Конец XIX в. принес изобретение и усовершенствование арифмометра (Однер, Швеция, 1874; французы Томас де Кольмар с сыном, «арифмометр», 1822–1879 и Боле 1887; Барроуз, США, 1892). Это движение продолжалось до 1930 г.

Американский инженер Герман Холлерит применил для переписи населения 1890 г., а позднее усовершенствовал для следующих переписей «табулятор», использующий перфорированные карты, – машину, идеи которой восприняты алгоритмами сортировки распределением (VII.3.8).

I.8.2. Протоинформатика В статье 1976 г. [Эккерт 76] один из пионеров американской вычислительной техники Дж. Преспер Эккерт заметил, что вычислительные машины могли бы быть изобретены на несколько десятилетий раньше – техника электронных ламп в то время уже существовала. Но только экономические и военные потребности второй мировой войны дали толчок процессу реализации.

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

английский математик Тьюринг в важной статье [Тьюринг 36] заложил основы математической теории вычислений и показал за несколько лет до реализации первых ЭВМ (одна из которых, британский проект АСЕ, был реализован под руководством Тьюринга в 1946 г.), что можно делать теоретически на вычислительной машине и что невозможно. Другие, близкие или дополняющие теории были развиты между 1936 и 1940 гг. американцами Постом и Клини и советским математиком Марковым.

I.8.3. Информатика Дата, отделяющая протоинформатику от информатики, так же неопределенна, как дата, отмечающая переход от протоистории к новейшей истории. Несомненно, однако, что «военные усилия» во многих странах дали решающий импульс рождению первых вычислительных машин, заслуживающих этого имени:

- Ц2 и ЦЗ немецкого инженера К. Цузе, готовые соответственно в 1939 и гг., но уничтоженные в конце войны;

- серия машин МАРК, построенная Г. Айкеном (Гарвардский университет и ИБМ), первый экземпляр которой – МАРК 1 – был закончен в 1944 г.;

- ЭНИАК Джона Маучли и Дж. П. Эккерта (Пенсильванский университет, 1943–1946 гг.); эти два изобретателя основали в 1946 г. компанию «Унивак», первая машина которой вышла в 1951 г.

- ЭДСАК англичанина Уилкса (Кэмбриджский университет), строившийся с 1946 по 1949 г.

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

- первое использование индексного регистра на машине Манчестерского университета (1947–48 гг.) - изобретение транзисторов в 1948 г. исследователями компании «Белл»;

- изготовление серии ИБМ 701 начиная с 1953 г.;

- создание ФОРТРАНа в 1956 г. [Бэкус 57]; в том же году М. Перре изобрел французское слово “ordinateur” 1;

- первое описание АЛГОЛа Бэкусом в 1959 »г., пересмотренное и исправленное в [Наур 60]; здесь можно найти первую формальную спецификацию синтаксиса языка программирования;

- описание КОБОЛа в 1959 г. в результате сотрудничества американского правительства, пользователей и конструкторов;

- первая система с виртуальной памятью (Атлас, Манчестерский университет, 1962 г.).

Начиная с этого времени расширение мирового парка вычислительных машин идет с высокой и все увеличивающейся скоростью; Европа пытается сократить свое отставание в оборудовании (Рис. I.15), однако в силу мало согласованного сопротивления американскому примату, а также из–за определенной медлительности в развитии преподавания информатики в университетах и технических вузах сохраняется все–таки сильная зависимость от языков и машин, импортируемых из США.

Рис. I.15 Эволюция парка ЭВМ.

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

Этим отмечается этап французской истории информатики. – Прим. перев.

Библиография Существует много введений в информатику. Для беглого знакомства с проблемами этой науки можно прочитать, например, [Арсак 70].

Для более полного описания принципов программирования и фундаментальных свойств вычислительных машин можно обратиться к [Вегнер 69] или [Гир 69]. Из работ, посвященных углубленному исследованию структур ЭВМ, надо назвать [Мейнадье 71] на французском языке и [Белл 71] на английском.

Среди введений в программирование, излагающих современные идеи по этому вопросу, можно рекомендовать [Наур 74], а также [Вирт 72], ориентированные на язык программирования Паскаль. Более ранний выпуск [Дейкстра 71] прежде всего немного более труден и менее многословен, но он сыграл важную роль в развитии методов преподавания программирования 1.

ЗАДАЧА

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

Считается известным алфавитный порядок букв (А В С...X Y Z), и словом называется конечная последовательность букв, относительно которых для простоты предполагается, что все они прописные и в последовательность не включены ни пробелы, ни тире и т.д. Примерами слов являются Требуется строго определить свойство: «х предшествует у в алфавитном порядке», где х и у – слова, т.е. дополнить фразу «х предшествует у в алфавитном порядке тогда и только тогда, когда...». Важно заметить, что необходимо дать определение, т.е. характеристическое свойство, а не метод решения вида: «берем первые две буквы слов х и у; если первая буква предшествует первой букве у, то...

иначе, если они одинаковы, берем вторые буквы...» и т.д.

Среди переведенных на русский язык книг, представляющих достаточно полные введения в информатику, следует назвать, кроме уже упомянутой работы [Вирт 72], еще и книгу [Бауэр 76]. О современных зарубежных и отечественных ЭВМ, а также об их математическом обеспечении рассказано в книге [Королев 78]. – Прим. перев.

ВВЕДЕНИЕ В ЯЗЫКИ ПРОГРАММИРОВАНИЯ ФОРТРАН,

АЛГОЛ W, ПЛ/ II.1 Основные характеристики II.2 Алгоритмическая нотация II.3 Введение в ФОРТРАН II.4 Введение в АЛГОЛ W II.5 Введение в ПЛ/ Главное орудие программиста – его средство выражения: язык программирования.

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

Целью этой главы является не исчерпывающее исследование языков, а лишь обзор основных элементов используемых языков, и в частности трех из них – ФОРТРАНа, АЛГОЛa W и ПЛ/1. Эти основные элементы будут необходимы при рассмотрении более глубоких свойств тех же языков – управляющие структуры, структуры данных, рекурсивные выражения, – эти исследования будут продолжены в гл. III–VI.

II.1. Основные характеристики II.1.1. Значения и типы Цель программы состоит в вычислении значений. В свою очередь вычислительная машина оперирует не со значениями, а скорее с представлениями значений, которые являются конфигурациями битов, байтов или слов памяти. Так как физические представления зависят от изображаемых объектов, то для того, чтобы оперировать со значениями, необходимо специфицировать их типы. Это кажущееся ограничение может оказаться на деле выгодным, потому что оно заставляет программиста точно определить все используемые им объекты и лучше контролировать свою программу.

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

Перевод А. В. Тарновского.

II.1.1.1. Литеры Чтобы изобразить литеры, принадлежащие заданному «алфавиту» (обычному алфавиту с прописными и строчными буквами, который расширен десятичными цифрами и какими–нибудь специальными символами, как $ @ < и т.д.), используют коды литер (наиболее распространенными кодами являются коды BCD, EBCDIC, ASCII). В зависимости от кода литера изображается 6 битами, 7 битами или 8 битами (байтом).

II.1.1.2. Строки «Строка», или «цепочка литер» (английское STRING) – это конечная последовательность литер, например

АБРА КАДАБРА

Заметим, что объект типа «литера» это частный случай «строки»

(последовательность длиной в одну литеру). Используются же они, вообще говоря, по– разному.

Внутреннее представление «строк» будет рассмотрено в II.3.3.5 в связи с ФОРТРАНом.

II.1.1.3. Логические значения «Логическое» значение представляет собой одно из двух значений истина или ложь; логические значения появляются всякий раз, когда окружение программы оказывает влияние на ход ее выполнения (условные операторы, ср. ниже III.4.3) или на вычисление выражения (условные выражения, II.1.2.4).

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

II.1.1.4. Целые числа Вычислительные машины разрешают работать с целыми числами, положительными, нулевыми или отрицательными. Множество Z целых чисел в математике бесконечно, но в вычислительной машине целое изображается, вообще говоря, фиксированным числом битов; если число битов равно n (где n чаще всего длина машинного слова), это означает, что в машине представимы только 2n целых чисел. Так, на ИБМ 360 или 370 n = 32 и представимые целые числа содержатся между –231 и +231–1, т.е. приблизительно ±2 миллиарда; для изображения этих чисел используется соответствующий код.

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

II.1.1.5. Дробные числа («вещественные») Термин «вещественное», часто используемый в программировании как противопоставление термину «целое», в сущности, неправилен; он обозначает число, имеющее дробную часть, но в машине можно представить только конечное подмножество множества рациональных чисел.

Авторы предпочитают называть этот тип значений «текстами»; в переводе тем не менее сохранено устоявшееся в русской литературе название. – Прим. перев.

Обычные человеческие обозначения используют для дробных чисел одну из двух форм:

+ a, b 10n («научная нотация») Представление в машине обобщает вторую из этих нотаций. Дробное число относительно некоторой системы счисления рассматривается состоящим из знака (+ или —) и пары изображающей число х = с Вn. Здесь В, основание системы счисления, фиксированное целое положительное число; с, мантисса числа х, положительное целое число, заключенное между 1/В и 1, или 0 (для изображения дробного числа х = 0) и изображаемое фиксированным числом S битов (таким образом могут быть изображены 2s различных значений); наконец, n – порядок х, это целое положительное, отрицательное или 0, заключенное между двумя крайними значениями MIN и МАХ;

(часто имеет место MIN = –МАХ).

Машинная арифметика вещественных чисел полностью характеризуется четырьмя целыми константами: В (основание), S (число значащих битов), MIN и МАХ (предельно возможные значения порядка).

Так, машина ИБМ серии 360 или 370 использует систему счисления с основанием В = («шестнадцатеричная» система), MIN = — 64 и МАХ = 63. Фактически на этих машинах есть два способа представления чисел;

- так называемые вещественные простой точности используют 6 значащих шестнадцатеричных цифр (S = 4 х 6 = 24, поскольку нужно 4 бита для изображения цифры по - вещественные удвоенной точности используют 14 значащих шестнадцатеричных цифр (S = 56). Следовательно, на ИБМ 360/370 можно изобразить 15228 + 1 различных «вещественных»

чисел простой точности и 15260 + 1 «вещественных» удвоенной точности. Для многих задач точность в 6 шестнадцатеричных цифр (т.е. выше чем 7 десятичных цифр) недостаточна, поэтому рекомендуется систематически применять удвоенную точность.

Всякое вещественное число из интервала [–ВМАХ, +ВМАХ] может быть приближено некоторым точно представимым числом, т.е. в форме (MIN n МАХ; с изображается S битами и с = 0 или 1/В 1 каждое измерение имеет пару соответствующих границ [mi, Mi] и элементы массива обозначаются ТАБ [а1 а2,.., аn], где каждое аi означает целое, заключенное между mi и Mi.

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

II.1.2.4. Выражения Выражение позволяет обозначить вычисление каждого значения по другим значениям и операциям. Входные значения выражения могут быть константами, значениями переменных или элементов массивов, или значениями выражений. Так, в наших трех языках примерами выражений типа ЦЕЛОЕ могут быть:

В некоторых языках тип является переменным.

В таких выражениях, как в последнем примере, порядок операций (как и в математике) определяется их приоритетом: говорят, что умножение имеет более высокий приоритет, чем сложение, чтобы указать, что при отсутствии скобок А + В * С обозначает сумму значения А и произведения В * С, а не произведения суммы А + В на С. Мы увидим правила приоритетов в различных языках, которые в целом близки к общепринятым соглашениям. В сомнительных случаях или для того, чтобы нарушить правила приоритета, можно всегда использовать скобки:

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

Точно так же существуют выражения логического типа, т.е. обозначающие истину или ложь. Они, в частности, составлены из операторов отношений, позволяющих проверять равенство или неравенство двух объектов или отношения порядка, определенные на числах или на строках (алфавитный порядок). Так, если I и J – целые переменные, то с помощью отношения 1 < J в АЛГОЛЕ W и ПЛ/1 или I.LT.J в ФОРТРАНе обозначают выражение логического типа (так называемого типа BIT в ПЛ/1), означающего истину, если I меньше J, ложь в противном случае.

Заметим по этому поводу, что в силу приближений, возникающих благодаря представлению дробных чисел в машине (ср. выше II.1.1.5), логическое выражение, сравнивающее два объекта а и b типа ВЕЩЕСТВЕННЫЙ с помощью операторов равенства или неравенства, не имело бы большого смысла; например, такое логическое выражение, как 2.71=(5.42/2) или еще 2.71.EQ.(5.42/2.) в обозначениях ФОРТРАНа, вполне может иметь ложное значение. Важнее сравнивать абсолютное значение |а — b| разности двух чисел с малой положительной константой. Исключением из этого правила является сравнение с числом нуль, которое дает правильный II.1.3. Программы, операторы Цель программы состоит, вообще говоря, в вычислении одного или нескольких значений. Хорошо было бы уметь задавать программу в виде формулы, в которую входили бы данные и операции обработки этих данных, т.е. в виде выражения (термин, который мы только что определили). Тогда программа, вычисляющая сумму квадратов двух чисел а и b, могла бы записываться просто или а вызов программы автоматического перевода можно было бы представить в виде русско–французский–перевод ("ВОЛК И СЕМЕРО КОЗЛЯТ") В наших трех языках программирования нельзя специфицировать программы таким образом, и мы обязаны сами задавать этапы «вычисления» списком предписаний, называемых операторами. Правильные совокупности операторов образуют программы, разрешенные для рассматриваемого языка. Различают два типа операторов:

• операторы обработки информации в собственном смысле слова, • операторы, которые управляют работой программы во времени.

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

а) оператор присваивания имеет дело с переменной или элементом массива, например х, и выражением, например е. Он записывается в зависимости от языка либо хе, либо х:=е, либо х = е (и даже ех).

Записывая этот оператор, программист полагает, что по окончании его выполнения х будет принимать в качестве нового значения величину (значение) выражения е. Обычно х и е имеют одинаковый тип (в ПЛ/1 они могут быть массивами).

Характеристическое свойство присваивания хе, смысл которого определится в разд. III.4, состоит в том, что всякое отношение Р переменных программы будет истинным после выполнения этого присваивания, если и только если Р [ех] было истинно до выполнения; последнее обозначение выражает замену всех вхождений переменной х на выражение е. Можно убедиться в том, что это свойство верно, независимо от того, присутствует ли х в выражении е (кроме частного случая «побочного эффекта»; см. гл. IV).

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

Pages: |

| 2 | 3 | 4 | 5 | ... | 6 |

Главная >> Монографии

[ СКАЧАТЬ ОРИГИНАЛ ДОКУМЕНТА .pdf ]

Похожие работы:

«АКАДЕМИЯ НАУК СССР КОМИССИЯ ПО РАЗРАБОТКЕ НАУЧНОГО НАСЛЕДИЯ АКАДЕМИКА В. И. ВЕРНАДСКОГО ИНСТИТУТ ИСТОРИИ ЕСТЕСТВОЗНАНИЯ И ТЕХНИКИ АРХИВ АН СССР ВЛАДИМИР ИВАНОВИЧ ВЕРНАДСКИЙ В.И. ВЕРНАДСКИЙ Труды по всеобщей истории науки 2-е издание МОСКВА НАУКА 1988 Труды по всеобщ ей истории науки/В. И. В ернадский.- 2-е и з д.- М: Наука, 1988. 336 С. ISBN 5 - 0 2 - 0 0 3 3 2 4 - 3 В книге публикуются исследования В. И. Вернадского по всеобщей истории науки, в частности его труд Очерки по истории...»

«КОМПОНЕНТЫ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ДЛЯ СИТУАЦИОННЫХ ЦЕНТРОВ Омск 2010 УДК 681.3.004.8 ББК И КОМПОНЕНТЫ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ДЛЯ СИТУАЦИОННЫХ ЦЕНТРОВ: / Анисимов О.С., Берс А.А., Жирков О.А. и др. /Под науч. ред. В.А.Филимонова/ Омск: ООО Информационно-технологический центр, 2010.- 152 с.: ил. ISBN В монографии исследуются потенциальные возможности современных информационных технологий исследования. Ситуационные центры могут являться инфраструктурой для реализации упомянутых возможностей....»

«Министерство культуры Российской Федерации Северо-Кавказский государственный институт искусств А. И. Рахаев Г. А. Гринченко И. С. БАХ ШЕСТЬ СОНАТ ДЛЯ ЧЕМБАЛО И СКРИПКИ Нальчик Издательство М. и В. Котляровых 2010 2 ББК 85.315.2 УДК 785.72.082.2(430)+929 Бах Р27 Рецензенты: Б. Г. Ашхотов, доктор искусствоведения, профессор Ф. С. Эфендиев, доктор философских наук, профессор Рахаев А. И., Гринченко Г. А. Р27 И. С. Бах. Шесть сонат для чембало и скрипки. – Нальчик: Издательство М. и В. Котляровых,...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ АДЫГЕЙСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЦЕНТР БИЛИНГВИЗМА АГУ X. 3. БАГИРОКОВ Рекомендовано Советом по филологии Учебно-методического объединения по классическому университетскому образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности 021700 - Филология, специализациям Русский язык и литература и Языки и литературы народов России МАЙКОП 2004 Рецензенты: доктор филологических наук, профессор Адыгейского...»

«РОССИЙСКАЯ ФЕДЕРАЦИЯ АКАДЕМИЯ НАЦИОНАЛЬНОЙ БЕЗОПАСНОСТИ, ОБОРОНЫ И ПРАВОПОРЯДКА Ш.Ш. Исраилов, Н.Н. Пушкарев, А.А. Кобяков ОРГАНИЗАЦИЯ УПРАВЛЕНИЯ ПЕРСОНАЛОМ БИЗНЕС СТРУКТУР Монография Агентство печати Наука Москва 2006 1 ББК 65.290 2я7 И 88 УТВЕРЖДЕНО решением Учёного Совета Академии национальной безопасности, обороны и правопорядка от 5 мая 2004 года Под научной редакцией доктора экономических наук, профессора РЭА им. Плеханова Шубенковой Е.В. Рецензенты: Гретченко А.И. – доктор экономических...»

«В.В. Тахтеев ОЧЕРКИ О БОКОПЛАВАХ ОЗЕРА БАЙКАЛ (Систематика, сравнительная экология, эволюция) Тахтеев В.В. Монография Очерки о бокоплавах озера Байкал (систематика, сравнительная экология, эволюция) Редактор Л.Н. Яковенко Компьютерный набор и верстка Г.Ф.Перязева ИБ №1258. Гос. лизенция ЛР 040250 от 13.08.97г. Сдано в набор 12.05.2000г. Подписано в печать 11.05.2000г. Формат 60 х 84 1/16. Печать трафаретная. Бумага белая писчая. Уч.-изд. л. 12.5. Усл. печ. 12.6. Усл.кр.отт.12.7. Тираж 500 экз....»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования Оренбургский государственный университет С.В. МИРОНОВ, А.М. ПИЩУХИН МЕТАСИСИСТЕМНЫЙ ПОДХОД В УПРАВЛЕНИИ МОНОГРАФИЯ Рекомендовано к изданию Ученым Советом государственного образовательного учреждения высшего профессионального образования Оренбургский государственный университет в качестве научного издания Оренбург 2004 УДК...»

«1 ИНСТИТУТ ФИЛОСОФИИ, ПОЛИТОЛОГИИ И РЕЛИГИОВЕДЕНИЯ КОМИТЕТА НАУКИ МИНИСТЕРСТВА ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН РАУШАН САРТАЕВА ЭКОЛОГИЯ ЧЕЛОВЕКА, НОВАЯ ОНТОЛОГИЯ И УСТОЙЧИВОЕ РАЗВИТИЕ КАЗАХСТАНА Алматы 2012 2 УДК 502/504 (574) ББК 20.1 (5 Каз) С 20 Рекомендовано Ученым Советом Института философии, политологии и религиоведения Комитета науки МОН РК Под общей редакцией: З. К. Шаукеновой, члена-корреспондента НАН РК, доктора социологических наук, профессора Рецензенты: Д.У. Кусаинов,...»

«МЕЖДУНАРОДНЫЙ ЮРИДИЧЕСКИЙ ИНСТИТУТ В.Б. Евдокимов, Т.А. Тухватуллин СОВРЕМЕННЫЙ РОССИЙСКИЙ ФЕДЕРАЛИЗМ: ОТНОШЕНИЯ ЦЕНТРА С ЕГО СУБЪЕКТАМИ (конституционно-правовые аспекты) Москва 2011 ББК 67.99(2) Е15 Евдокимов В.Б., Тухватуллин Т.А. Е15 Современный российский федерализм: отношения Центра с его субъектами: (конституционно-правовые аспекты). Монография. М.: Международный юридический институт, 2011. – 248 с. Рекомендовано к изданию Учебно-методическим советом МЮИ. Протокол № 43 от 14 декабря 2011...»

«i i i i БИБЛИОТЕКА БИОТЕХНОЛОГА Р. П. Тренкеншу, Р. Г. Геворгиз, А. Б. Боровков ОСНОВЫ ПРОМЫШЛЕННОГО КУЛЬТИВИРОВАНИЯ ДУНАЛИЕЛЛЫ СОЛОНОВОДНОЙ (DUNALIELLA SALINA TEOD.) Севастополь, 2005 i i i i i i i i УДК 639. Тренкеншу Р. П., Геворгиз Р. Г., Боровков А. Б. Основы промышленного культивирования Дуналиеллы солоноводной (Dunaliella salina Teod.) — Севастополь: ЭКОСИ–Гидрофизика, 2005. — 103 с. В монографии представлены результаты исследований продукционных характеристик Dunaliella salina Teod.,...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ федеральное государственное бюджетное образовательное учреждение высшего профессионального образования САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ТОРГОВО-ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ (ФГБОУ ВПО СПбГТЭУ) ИННОВАЦИИ В ОБЛАСТИ ТЕХНОЛОГИИ ПРОДУКЦИИ ФУНКЦИОНАЛЬНОГО И СПЕЦИАЛИЗИРОВАННОГО НАЗНАЧЕНИЯ Коллективная монография САНТК-ПЕТЕРБУРГ 2012 УДК 641.1:613:29 ББК Инновации в области технологии продукции общественного питания функционального и...»

«Министерство образования и науки Российской Федерации Дальневосточный федеральный университет А.М. Кузнецов, И.Н. Золотухин Этнополитическая история Азиатско-Тихоокеанского региона в ХХ – начале ХХI вв. Владивосток Издательство Дальневосточного федерального университета 2011 1 http://www.ojkum.ru/ УДК 323.1 ББК 66.5(0) К 89 Работа выполнена в рамках Аналитической ведомственной целевой программы Развитие научного потенциала Высшей школы Рецензенты: М.А. Фадеичева, доктор политических наук,...»

«РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕ ЛЕНИЕ ИНСТИТУТ ГУМАНИТАРНЫХ ИССЛЕДОВАНИЙ И ПРОБЛЕМ МАЛОЧИСЛЕННЫХ НАРОДОВ СЕВЕРА Н.И. ИВАНОВА СОВРЕМЕННОЕ КОММУНИКАТИВНОЕ ПРОСТРАНСТВО РУССКОГО ЯЗЫКА В РЕСПУБЛИКЕ САХА (ЯКУТИЯ) СОцИОПСИХОЛИНГВИСТИЧЕСКИЙ АСПЕКТ Ответственный редактор доктор филологических наук П.А. Слепцов НОВОСИБИРСК НАУКА 20 УДК 81.27 +. ББК 81.2Рус + 2Рос.Яку И Рецензенты доктор филологических наук А.А. Бурыкин кандидат...»

«Министерство образования и науки Российской Федерации Московский государственный университет экономики, статистики и информатики (МЭСИ) Шубина И.В., Завражин А.В., Федоров П.Ю. Образовательная политика в России: история и современность Монография Москва, 2011 1 УДК 378 ББК 74 Ш 951 Работа выполнена на кафедрах Педагогики, Философии и гуманитарных наук МЭСИ Авторы: кандидат педагогических наук Шубина И.В. доктор исторических наук, доцент Завражин А.В. кандидат юридических наук Федоров П.Ю....»

«ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ г. МОСКВЫ МОСКОВСКИЙ ИНСТИТУТ ОТКРЫТОГО ОБРАЗОВАНИЯ Кафедра филологического образования КУЛЬТУРА РЕЧИ СЕГОДНЯ: ТЕОРИЯ И ПРАКТИКА Коллективная монография Москва, 2009 ББК 81.2-5 УДК 80 К 90 Культура речи сегодня: теория и практика: коллективная монография / сост. Дмитриевская Л.Н. — М.: МИОО, 2009. — 200 с. Редакционная коллегия: Дмитриевская Л.Н., кандидат филол. наук ; Дудова Л.В., кандидат филол. наук; Новикова Л.И., доктор пед. наук. Составление: Дмитриевская Л.Н....»

«Министерство образования и науки Красноярского края КРАСНОЯРСКИЙ КРАЕВОЙ ИНСТИТУТ ПОВЫШЕНИЯ КВАЛИФИКАЦИИ И ПРОФЕССИОНАЛЬНОЙ ПЕРЕПОДГОТОВКИ РАБОТНИКОВ ОБРАЗОВАНИЯ А.Л. РУДАКОВ Стресс, стрессоустойчивость и саногенная рефлексия в спорте МОНОГРАФИЯ Красноярск, 2011 4 А.Л. РУДАКОВ Стресс, стрессоустойчивость и саногенная рефлексия в спорте 5 УДК 159/94+614 ББК 88.3+52.5 Г 37 РЕЦЕНЗЕНТЫ: Нургалеев В.С., к.пед.н., д.психологических наук, профессор. Горячева Т.В., к.мед.н., доцент. Рудаков А.Л....»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ КАЛИНИНГРАДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ А.А. Девяткин ЯВЛЕНИЕ СОЦИАЛЬНОЙ УСТАНОВКИ В ПСИХОЛОГИИ ХХ ВЕКА Калининград 1999 УДК 301.151 ББК 885 Д259 Рецензенты: Я.Л. Коломинский - д-р психол. наук, проф., акад., зав. кафедрой общей и детской психологии Белорусского государственного педагогического университета им. М. Танка, заслуженный деятель науки; И.А. Фурманов - д-р психол. наук, зам. директора Национального института образования Республики...»

«3 ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКАЯ АКАДЕМИЯ ПРАВОСУДИЯ ЦЕНТРАЛЬНЫЙ ФИЛИАЛ Клепиков Сергей Николаевич АДМИНИСТРАТИВНАЯ ОТВЕТСТВЕННОСТЬ В СУБЪЕКТАХ РОССИЙСКОЙ ФЕДЕРАЦИИ Воронеж 2006 4 Государственное образовательное учреждение высшего профессионального образования РОССИЙСКАЯ АКАДЕМИЯ ПРАВОСУДИЯ ЦЕНТРАЛЬНЫЙ ФИЛИАЛ КАФЕДРА ОБЩЕТЕОРЕТИЧЕСКИХ ПРАВОВЫХ ДИСЦИПЛИН Клепиков Сергей Николаевич АДМИНИСТРАТИВНАЯ ОТВЕТСТВЕННОСТЬ В СУБЪЕКТАХ...»

«Министерство образования Республики Беларусь УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ ГРОДНЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ ЯНКИ КУПАЛЫ И.Ю.Самойлова ДИНАМИЧЕСКАЯ КАРТИНА МИРА И.БРОДСКОГО: ЛИНГВИСТИЧЕСКИЙ АСПЕКТ Монография Гродно 2007 УДК 882 (092 Бродский И.): 808.2 ББК 81.411.2 С17 Р е ц е н з е н т ы: заведующий кафедрой культуры речи и межкультурных коммуникаций Белорусского государственного педагогического университета им. М.Танка доктор филологических наук, профессор И.П. Кудреватых; доктор...»

«Особо охраняемые природные территории УДК 634.23:581.16(470) ОСОБО ОХРАНЯЕМЫЕ РАСТЕНИЯ САМАРСКОЙ ОБЛАСТИ КАК РЕЗЕРВАТНЫЙ РЕСУРС ХОЗЯЙСТВЕННО-ЦЕННЫХ ВИДОВ © 2013 С.В. Саксонов, С.А. Сенатор Институт экологии Волжского бассейна РАН, Тольятти Поступила в редакцию 17.05.2013 Проведен анализ группы раритетных видов Самарской области по хозяйственно-ценным группам. Ключевые слова: редкие растения, Самарская область, флористические ресурсы Ботаническое ресурсоведение – важное на- важная группа...»

наверх

<< ГЛАВНАЯ | КОНТАКТЫ

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

МЕТОДЫ

ПРОГРАММИРОВАНИЯ

ОГЛАВЛЕНИЕ

ГЛАВА II. ВВЕДЕНИЕ В ЯЗЫКИ ПРОГРАММИРОВАНИЯ

ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕИЗДАНИЯ

ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА

ПРЕДИСЛОВИЕ

ОБЩИЕ СВЕДЕНИЯ О ПРОГРАММИРОВАНИИ

ОБЩИЕ СВЕДЕНИЯ О ПРОГРАММИРОВАНИИ

ЗАДАЧА

ВВЕДЕНИЕ В ЯЗЫКИ ПРОГРАММИРОВАНИЯ ФОРТРАН,

ВВЕДЕНИЕ В ЯЗЫКИ ПРОГРАММИРОВАНИЯ ФОРТРАН,

АБРА КАДАБРА

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА (Авторефераты, диссертации, методички, учебные программы, монографии)

МЕТОДЫ

ПРОГРАММИРОВАНИЯ

ОГЛАВЛЕНИЕ

ГЛАВА II. ВВЕДЕНИЕ В ЯЗЫКИ ПРОГРАММИРОВАНИЯ

ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕИЗДАНИЯ

ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА

ПРЕДИСЛОВИЕ

ОБЩИЕ СВЕДЕНИЯ О ПРОГРАММИРОВАНИИ

ОБЩИЕ СВЕДЕНИЯ О ПРОГРАММИРОВАНИИ

ЗАДАЧА

ВВЕДЕНИЕ В ЯЗЫКИ ПРОГРАММИРОВАНИЯ ФОРТРАН,

ВВЕДЕНИЕ В ЯЗЫКИ ПРОГРАММИРОВАНИЯ ФОРТРАН,

АБРА КАДАБРА

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)