1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 2
Текст из файла (страница 2)
Не ощущая вначале никакого порога и следуя 'линии изложения, читатель тем не менее к концу книги окая«ется на высоте проблематики, которая является содерн«вянем современной профессиональной математической работы, не делающей никаких скидок на возраст н опыт читателя. Как уже было сказано, книга в основном предназначена для самостоятельного чтения университетскими студентами. Она может быть также использована для кружковой или просеминарской работы в техникумах, физико-математических классах и на младших курсах пединститутов. Материал книги складывался в течение нескольких лет и был частично апробирован в летней школе вузовских преподавателей Дальнего Востока (Владивосток, 1970 г.), в курсе лекций, прочитанных в Стэнфордском университете (1970 г.), и спецкурса для студентов-математиков младших курсов в Новосибирском университете 1197 П72 уч.
год). Подчеркивая экспериментальный характер втой книги, автор все же не может не назвать некоторые выдающиеся математические сочинения, воодушевлявшие его во время работы над книгой. Надо полагать, многие современные математики испытали' на себе воздействие таких замечательных книг, как «Что такое математика7» Куранта и Робинса и «Матеметйка и правдоподобные рассуждения» Пойя. Что касается более избирательного влияния, то в свое время на автора произвели сильное впечатление небольшая книга Хинчнна «Три жемчужины теории чисел» как непревзойденный пример раскрытия содержания науки через обсул'дение конкретных задач, н известный мемуар Бэра «О раарывных функциях», убедительно демонстрирующий силу поступательного развития решения задачи, начиная с алементарной постановки н кончая полным решением проблемы во всей ее сложности. Будучи далеким от мысли поставить себя в'ряд со столь знаменитыми предшественниками, автор тем не менее видит в своем труде скромную попытку частичного осуществления долга, оставленного нам учителями,— не жалеть усилий на раскрытие польаы, глубины и красоты математической науки перед лицом каждого, нежелающего приобщиться к этому фундаменту современного анания.
Новосибирск, Академгородок А. П. Ершов ЧАСТЬ 1 ЭКОНОМИЯ ПАМЯТИ В ОПЕРАТОРНЫХ СХЕМАХ ГЛАВА ~ СОДЕРЖАТЕЛЬНЫЙ АНАЛИЗ ЗАДАЧИ 5 1 1. Краткое повторение программирования Электронная вычислительная машина. ЭВМ вЂ” это автомат, состоящий из памяти и исполнительного устройсспва. Память состоит иа занумерованных подряд ячеек. Номер ячейки называется ее адресом. В ячейках памяти хранится информация, представленная в машине в виде двоичного числа, т.
е. последовательности нулей и единиц. Как и в обычной арифметике, позиции двоичных цифр содержимого ячейки называют разрядами. Подобно тому как в' азбуке Морае последовательности точек и тире могут обозначать самую разную информацию, так и нули н единицы в ячейках памяти могут иметь смысл не только двоичных разрядов числа, но и многого другого. Для того чтобы подчеркнуть возмох'ность самой раакой интерпретации содержимого ячеек памяти, это содержимое нааызают (машинным) словом.
Число двоичных разрядов в слове называется его длиной. Исполнительное устройство может выполнять отдельные ко.1санды. Набор разных команд (система команд ЭВМ), которые может выполнять устройство, обычно сравнительно невелик, а сами команды очень просты. Типичной командой является следующая: взять из указанных ячеек памяти одно или два слова з качестве аргументов, передать их в исполнительное устройство, выполнить над ними укааанное действие (сложить, умножить, сравнить по величине и т. н.), а результат направить в указанную ячейку памяти. Программа.
Из сказанного понятно, что для решения сколько- нибудь слоясной задачи ЭВМ должна выполнить очень длинную последовательность команд. Так как ЭВМ работает автоматически, 'то эта последовательность команд должна быть придумана заранее и введена в память машины до начала решения задачи. Обычно в одной ячейке памяти хранится точно одна команда машины, а непрерывность работы исполнительного устройства обеспечивается тем, что кая<дая команда (если только это не была команда остановки машины) обязательно оставляет в исполнительном устройстве адрес ячейки со следующей подлежащей выполнению командой. Таким образом, составить программу решения- задачи на ЭВМ вЂ” это значит написать такую последовательность команд машины, чтобы они, оказавшись з нужной части памяти машины 1л.
1. содегя(Ательный АКАлиз зАЛАчи и выполняясь одна за другой, создали бы последовательность действий исполнительного устройства, которая приведет к решению аадачи. Каждая команда программы заставляет выполнить указанное в ней действие с содержимым указанных ячеек памяти. Это значит, что при составлении программы нужно определить, какие ячейки памяти будут использованы в работе машины и что в них будет храниться. Обычно поступают таким образом. Размышляя над способом решения задачи, программист определяет, какие переменные величины появляются и используются прн ее решении. Одни величины даются уясе в условии задачи — обычно это ее исходные данные и искомые результаты.
Другие возникают в ходе решения задачи н нааываются промежуточными переменными величинами. Их значения вычисляются как результаты выполнения одних команд программы и используются позднее в других командах как их аргументы. Таким образом, при составлении программы у программиста появляется два списка — список команд и список величин программы.
Эти списки непосредственно связаны с памятью машины (кап<дай позиции каждого из списков сопоставляется некоторая ячейка) и друг с другом. Сзяаи величин с командами выглядят следующим образом. Каждая команда состоит из двух частей: кода онераиии, который указывает, какое действие вызывает команда, и адресной части. В адресной части указаны адреса ячеек, используемых в качестве аргументов и результатов команды. В некоторых командах в адресной части указываются не ячейки с величинами программы, а адреса команд,— в частности, когда следующая по порядку выполнения команда находится в программе не вслед за данной, а где-то в другом месте, которое и указывается своим адресом.
Это случается, например, при необходимости повторить группу команд программы несколько раз или выбрать один из нескольких вариантов вычислений в зависимости от значения переменных величин программы. Программирование. Осмысливая только что прочитанное, мы можем усмотреть некоторое сходство программирования для ЭВМ со школьным способом решения арифметических аадач по вопросам. Решая задачу таким способом, ученик должен был составить план решения в виде серии вопросов.
В вопросе спрашивалось, какая величина задачи должна быть вычислена. Вопрос ставился так, чтобы это вычисление выполнялось за одно действие над уже иавестными величинами. Пределом трудности считалась задача, которая решалась в 5 — 6 действий.
Программирование же для ЭВМ реальных задач требует предусматривать в плане решения десятки тысяч и ббльшее количество действий, для 1са>кдого из которых должна быть безошибочно записана вызывающая его команда. Поэтому с самого начала появлесия ЭВМ все усилия «!.!.
КРАТКОГ ПОВТОРЕНИЕ ПРОГРАММИРОВАНИЯ 1$ программистов были направлены на создание методов облегчения задачи программировании. Один из таких методов состоит в том, что составление программы для ЭВМ разбивается на этапы. На одном этапе программист составляет программу в такой форме, в которой ему легче эту программу придумать. На другом этапе промежуточная форма программы по некоторым формальным правилам превращаетсн в программу, непосредственно воспринимаемую машиной (»«ашинную програмл!у).
Фор»«альпы»«и эти правила являются в том смысле, что их применение к промежуточной форме требует педантичной точности, но не требует понимания того, что делает программа. Другимн словами, эти правила единым образом применимы к любой промежуточной форме программы. Последнее обстоятельство позволяет правила перевода промежуточной формы программы в машинную описать в виде общего алгоритма.
Этот алгоритм можно в свою очередь запрограммировать. У получившейся таким образом «сверхпрограммы» входными данными будет любая промежуточная форма программы, а результатом— машинная программа, в точности соответствующая промежуточной форме. В специальной литературе такие «сверхпрограммы»- переводчики называются трансляторами, компиляторами или программирующими программами. При наличии транслятора промежуточная форма программы, бОлее удобная для ее составления человеком, становится для него окончательной формой,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
