Д. Кнут - Искусство программирования том 1 (1119450), страница 62
Текст из файла (страница 62)
Так как обработка выполняется последовательно, имеем также ил > ил 1 при 1 < Ь < и. Всего у нас гГ буферов; следовательно, Гл > ел л при Х < !г < п. Насколько большим должно быть !Э', чтобы время сл завершения операции было минимальным из возможных, Т + С + (и — 1) шах(5, С)1 Сформулируйте общее правило определения наименьшего такого Х. Проиллюстрируйте свое правило лля 5 = 1, Р = 100, Т=.5, я=100 и(а) С=.5; (Ь) С=1.0; (с) С=1,01; (г1) С=1.5; (е) С=2.0; (1) С=2.5; (8) С = 10.0; (Ь) С = 50.0; (!) С = 200.0.
Поэтоъгу в нашем примере имеем (а) Тг = 1; (Ь) Ж = 2; (с) Ж = 3, ск = 2.5; (4) Ю = 35, сл = 51.5, :(е) Д' = 51, сл = 101 5; (!) Х = 41, сл = 102; (8) лг = 11, сл = 109.5; (Ь) Х = 3, сл = 149.5; (!) Д' = 2, сл = 298.5. 1.4.5. История и библиография Большинство фундаментальных методов, описанных в разделе 1.4, было независимо разработана разными программистами, и подробная история возникновения их идей, видимо, никогда не будет достоверно известна. Поэтому сейчас мы просто попытаемся перечислить и оценить наиболее важные работы, которые внесли вклад в развитие этих идей.
Подпрограммы были первым средством экономии сил программистов. Еще в 19 веке Чарльз Бэббидж (СЬаг!еэ ВаЬЬаяе) предвидел возможность создания библиотеки программ для своей аналитической машины [см. СЬвг!ел ВаЬЬаде апд Н!э Са!си/агшя Епя)пел, под редакцией Филиппа (РЬ!!!р) и Эмили (Епн1у) Моррисон (МогПвоп) (Почет, 1961), 56). И теперь можно сказать, что его мечта сбылась в 1944 году, когда Грэйс М. Хоппер (Стасе М. Норрег) написала подпрограмму вычисления функции э1п х для счетно-решающего устройства МатЕ 1, установленного в Гарвардском университете «см. МесИап!ва!!оп оЕ ТИоияИ! Ргосевяев (Епископ: На!.
РЬув. ЬаЪ., 1959), 164]. Но это еще были, в сущности, "открытые подпрограммы", т. е. такие подпрограммы,'которые нужно вставлять в программу, а не связывать динамически. Управление машиной Бэббиджа, как и ткацким станком Жаккарда, осуществлялось с помощью набора перфокарт, а счетно-решающим устройством МагЕ 1 — с помощью бумажных перфолент.
Таким образом, эти устройства существенно отличались от современных компьютеров с их хранящимися в памяти программами. Связь с подпрограммами, реализуемая на машинах с хранящимися в памяти программами, где адрес, по которому нужно вернуть управление, передается в качестве параметра, была рассмотрена Германом Г. Голдстайном (Негтап Н.
Со!бвь!пе) и Джоном фон Нейманом (ЗоЬп топ 1з1еигпапп) в их широкоизвестной монографии по программированию, написанной между 1946 и 1947 годами «см. работу фон Неймана Со!!ее!ее! И'ог!тв 5 (Незя Уог1е: Маспп11ап, 1963), 215-235]. В их программах главная программа отвечала за передачу параметров в тело подпрограммы, а не за передачу необходимой информации в регистры.
В Англии А. М. Тьюринг (А. М. ТиНпй) уже в 1945 году разработал аппаратное и программное обеспечение связи с подпрограммами [см. работу Ргосееойпйв ог" а Бесове! Еутров!ит оп 1,агйе-Яса!е !1!8!га! Са!си!абп8 МасИшегу (СатЬг!е!8е, Мазан Нагтаге! Еп!уегя!су, 1949), 87 — 90; В. Е. Сагреп!ег, Н. %. Рогап, ес!!!огя, А. М. ТиНп8'я АСЕ Яерогг оу 1946 апе! ОгИег Рарегя (СатпЬН48е, Маяяс М1Т Ргеяв, 1986), 35, 36, 76, 78, 79]. Способы применения и строение универсальной библиотеки подпрограмм — это главная тема первого учебника по компьютерному программированию М. У. %!1!евя, О. 3.
!УЬее1ег, Я. С!11, ТИе Ргерагабоп оГРгойгвтя йзг ап Е!есггоп!с .И8!Са! Сотригег, 1вг ее!. (Неае!!п8, Мазал Ае!о!воп-%ев1еу, 1951) (Уилкс М., Уилер Д. и Гилл С. Составление программ для электронных счетных машин. — Мл Изд-во иностр. лиг., 1953). Слово "сопрограмма" придумал М. Э. Конвей (М. Е. Сопзгау) в 1958 году, после того как он разработал это понятие и впервые применил его при построении программы на языке ассемблера. Почти в то же время сопрограммы независимо изучали Дж. Эрдвинн (д. Егт!ту!пп) и Дж.
Мернер (1. Мегпег). Они написали статью иВ1!асега! Е!п1еайеп*, которую посчитали недостаточно интересной, чтобы быть достойной опубликования. К сожалению, до сегодняшнего дня ни один экземпляр этой статьи, похоже, не сохранился. Первое опубликованное объяснение понятия сопрограммы появилось значительно позже в статье Конвея иПев!8п о! а БерагаЫе Тгапв!г!оп-П!айгат Сотр11ег", САСМ 6 (1963), 396-408. На самом деле о примитивной форме связи сопрограмм уже кратко упоминалось в "советах по программированиюп в первых публикациях, посвященных машине !!Ы1УАС «ТИе Ргойгаттег 1,2 (РеЪгиагу, 1954), 4]. Удобное обозначение для сопрограмм в алголоподобных языках было введено в работе ОаЫ, Нуйаагс1 81М1Л,А 1 «САСМ 9 (1966), 671-678].
Несколько прекрасных примеров сопрограмм (включая сопрограммы репликвции) появилось в книге 0.-3. ПаЫ, Е. 19. П!!вся!га, С. А. Н. Ноаге Яггисгигее! Ргойгатт!п8, СЬар!ег 3 (Дап У., Дейкстра Э., Хоор К. Структурное программирование / Пер. с англ.— Мс Мир, 1975 (сер. "Математическое обеспечение ЭВМп)). Первой программой-интерпретатором можно считать "универсальную машину Тьюринга", способную имитировать любые другие машины Тьюринга.
Машины Тьюринга— * "ДвусторОнняя связь". — Прим. перее. это не реальные компьютеры, а теоретические конструкции, использующиеся для доказательства того, что некоторые задачи нельзя решить с помощью алгоритмов. Программы-интерпретачоры в традиционном смысле упоминал в 1946 году Джон Мочли (ЛоЬп МапсЫу) в своих лекциях, которые он читал в Школе Мура (Мооге ЯсЬоо1). Самыми известными из первых интерпретаторов, главным назначением которых было обеспечение удобных средств выполнения операций с плавающей точкой, были программы для машины ЖЫг!ванд 1 (разработанные Ч.
В. Адамсом (С. %. Адашэ) и др.) и для машины 111!ас 1 (разработанные Д. Дж. Уилером (В. 3. УуЬее!ег) и др.). Тьюринг также принимал участие в их разработке; интерпретирующие системы для компьютера Р!1ос АСЕ были написаны под его руководством. Более подробно о положении дел с интерпретаторами в начале 50-х годов говорится в статье 3. М. Веппегг, В. С.
Рг!пв, М. Ь. Жоог!в, "1пгегргегабке ЯпЬ-гонг!пеэ", Ргос. АСМ Ха!. Сопй (1952), 81-87 [см. также различные статьи в журнале Ргосееш1п8з ог" !Ье Яутрояит оп АиготаВс Рго8гаттт8 Гог Ге81га! Сотригегз (1954), издаваемом Департаментом морских исследований (Вашингтон, федеральный округ Колумбия). Наиболее широкоиспользуемой программой-интерпретатором, вероятно, была "1ВМ 701 Ярее1сойп8 зуэгеш" Джона Бэкуса (ЛоЬп Васйпэ) [см. 3АСМ 1 (1954), 4 — 6[. Этот интерпретатор был несколько модифицирован и искусно переписан для 1ВМ 650 В. М. Волонтисом (У. М.
%о!оп!!е) и другими из компании Ве1! Те1ерЬопе 1аЬогасобеэ; их программа "Ве!! 1пгегргег!че Яуз!еш" приобрела широкую популярность. Интерпретируюшие системы 1РЬ, которые были разработаны в начале 1956 года А. Ньювеллом (А. алеке!!), Дж. К. Шоу (3. С. ЯЬав) и Г. А. Саймоном (Н. А. Я!шоп) для совершенно других целей (см. раздел 2.6), широко использовались для обработки списков. Как уже упоминалось во введении к разделу 1.4.3, о современных способах применения интерпретаторов в компьютерной литературе, как правило, говорится "на ходу" [см. ссылки на статьи, перечисленные в этом разделе, в которых интерпретаторы обсуждаются более подробно[. Первая программа трассировки была разработана Стэнли Гиллом (Ягап!еу С!!!) в 1950 году [см. его интересную статью в журнале Ргосеешпйз оГ !Ье Воуа! Яоиегу оу1 опйоп, зег!ев А, 206 (1951), 538 — 554[.
В упомянутой выше книге Уилкса, Уилера и Гилла содержится несколько программ трассировки. Наверное, самая интересная из них — это подпрограмма С-10, написанная Д. Дж. Уилером, в которой предусмотрена возможность, позволяющая приостановить трассировку при входе в библиотечную подпрограмму, выполнить эту подпрограмму иа полной скорости, а затем продолжить трассировку. Информация о программах трассировки довольно редко публикуется в общей компьютерной литературе. Это обусловлено, главным образом, тем, что данные методы по своей природе ориентированы на конкретную машину.
Автору известна только одна ранняя работа на эту тему — статья Н. У. Меей, "Ап Ехребтеп!а1 Моп!ьог!п8 НопВпе (ог гЬе 1ВМ 705", Ргос Ггеэгегп 3о!пг Сотри!ег Сопб (1956), 68-70. В ней обсуждается программа трассировки для машины, на которой было чрезвычайно трудно решить одну задачу, В настоящее время внимание к программам трассировки сместилось в сторону программ, обеспечивающих выборочный вывод результатов и оценок производительности программы; одна из лучших подобных систем была разработана Э. Сзттерсвейтом (Е, ЯаыеггЬча!!е) и описана в журнале Яойжаге РгасВсе зг Ехрепепсе 2 (1972), 197 — 217.
Буферизация первоначально выполнялась аппаратным способом, аналогично тому, как это делалось в программе 1.4.4 — (3). Внутренняя буферная область, недо- ступная для программиста, играла роль ячеек 2000 — 2099, и команды 1.4.4 — (3) выполнялись неявно и незаметно, когда выдавалась команда ввода. В конце 40-х годов первые программисты ПЯЪ'АС разработали программные методы буферизации, которые особенно полезны для сортировки (см. раздел 5.5). Хороший обзор основных принципов В/В, преобладавших в 1952 году, можно найти в Трудах конференции Восточного компьютерного объединения, которая проводилась в 1952 году.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
