Разностная машина Бэббиджа

Проекты машины Чарльза Бэббиджа были поистине предвестниками современных компьютеров. Если бы технологии позволяли построить его машину при небольших материальных затратах и если бы необходимость обработки данных торговли и правительства была такой же большой, как сегодня, то идеи Бэббиджа привели бы к компьютерной революции в начале XX века. Однако при его жизни была построена только демонстрационная модель его Разностной машины. Эта машина определяла числовые значения, вычисляя «последовательные разности». Рассмотрим этот метод на примере вычисления квадратов целых чисел. Мы начинаем, зная, что квадрат 0 равен 0, квадрат 1 равен 1, квадрат 2 равен 4 и квадрат 3 равен 9. Зная это, мы можем определить квадрат 4 следующим образом. Сначала мы вычисляем разности квадратов, значения которых мы уже знаем: 12 - О2 = 1, 22 - 12 = 3 и З2 - 22 = 5. Затем вычисляем разности этих разностей: 3- 1 =2и5-3 = 2. Заметьте, что результат в том и в другом случае равен 2. Предполагая, что эта закономерность сохраняется и дальше (можно доказать математически, что это так), мы делаем вывод, что и разность между выражениями (42 - З2) и (З2 - 22) должна быть также равна 2. Следовательно, (42 - З2) должно быть на 2 больше, чем (З2 - 22), значит, 42 - З2 = 7 и 42 = З2 + 7 = 16. Теперь, когда мы знаем квадрат4, мы можем вычислить квадрат 5, опираясь на значения 12, 22, З2 и 42. (Хотя более подробное обсуждение последовательных разностей выходит за рамки нашего курса, возможно, студентам, изучающим дифференциальное исчисление, будет интересно узнать, что приведенный выше пример является следствием того факта, что вторая производная функции у = х2 постоянна и равна 2.)

Происхождение этих небольших машин восходит к тем любителям, которые начали экспериментировать с самодельными компьютерами сразу после разработки больших исследовательских машин в 40-х годах. Именно в этом «подполье» Стив Джобе и Стефан Возняк создали в 1976 году коммерчески жизнеспособный домашний компьютер и основали компанию Apple Computer для его производства и продажи. Хотя продукция Apple была популярна, она не пользовалась большим спросом в деловых кругах, которые продолжали рассчитывать на уже привычную компанию IBM в большинстве своих компьютерных потребностей.

В 1981 году IBM представила свой первый настольный компьютер, названный персональным компьютером (сокращенно ПК), программное обеспечение для которого было разработано молодой развивающейся компанией Microsoft. Этот компьютер имел немедленный успех и закрепил ПК в сознании деловых людей как предмет торговли. Сегодня термин ПК используется по отношению ко всем машинам различных производителей, конструкция которых произошла от первого персонального компьютера IBM и многие из которых продолжают поставляться вместе с программным обеспечением компании Microsoft.

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

Наука об алгоритмах

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

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

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

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

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

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

♦ Какие задачи имеют алгоритмическое решение?

♦ Как можно облегчить поиск алгоритма?

♦ Как можно усовершенствовать технику представления и передачи алгоритма?

♦ Как можно применить наши знания об алгоритмах и технологиях для создания лучших машин?

♦ Как можно проанализировать и сравнить характеристики различных алгоритмов?

Всеми этими вопросами занимается наука об алгоритмах (рис. 0.3).

Роль абстракции

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

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

Рис. 0.4. Иерархия абстракций в аппаратном обеспечении стандартного персонального компьютера

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

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

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

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

Влияние на общество

Научный и технологический прогресс подрывает основания, на которых базировались общественные решения в прошлом, и даже бросает вызов многим общественным принципам. В чем различие между наличием интеллектуального поведения и наличием самого интеллекта? Когда начинается жизнь? Когда она заканчивается? Чем различаются растение и животное? Есть ли жизнь в других солнечных системах? Такие вопросы заставляют человека пересмотреть свои убеждения и часто — изменить их.

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

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

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

АРХИТЕКТУРА ЭВМ

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

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

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

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

Биты и их хранение

В современной компьютерной науке информация представляется как последовательность битов. Бит (bit) — двоичный разряд — является одним из двух чисел — 0 или 1, которые с настоящего момента мы будем рассматривать просто как символы, не имеющие никакого числового значения. В дальнейшем мы убедимся, что значение бита варьирует в зависимости от его применения. Иногда последовательность битов используется для представления числовых значений, иногда они обозначают буквы или другие символы, иногда — изображения, иногда могут обозначать звуки. Хранение бита в машине требует устройства, которое может находиться в двух состояниях, такого как выключатель (включен или выключен), реле (открыто или закрыто) или флаг на флагштоке (поднят или опущен). Одно из состояний используется для обозначения 0, второе для обозначения 1. Рассмотрим способы хранения битов в современных машинах.

Вентили и триггеры

Начнем с описания логических операций AND (И), OR (ИЛИ) и XOR (исключающее ИЛИ)1 (рис. 1.1). Эти операции схожи с арифметическими операциями умножения и сложения тем, что они так же объединяют пару значений на входе, чтобы породить третье значение на выходе. Однако в отличие от арифметических операций они манипулируют только числами 0 и 1. В данном контексте число 0 имеет значение «ложь» (false), а 1 — значение «истина» (true). Операции, которые манипулируют значениями «истина» и «ложь», называют булевыми операциями (Boolean operations) в честь математика Джорджа Буля (1815-1864).

Операция AND отражает истинность или ложность высказывания, которое построено из двух меньших или более простых высказываний при помощи союза «и». Такое высказывание имеет вид Р AND Q, где Р — это одно высказывание, a Q— другое. Например, Кермит - лягушонок AND Мисс Пигги - актриса.

Входные данные оператора AND отражают истинность или ложность компонентов сложного высказывания; результат, который мы имеем на выходе, отражает истинность или ложность самого сложного высказывания. Поскольку утверждение вида Р AND Q истинно только тогда, когда обе его части истинны, можно заключить, что на выходе операции 1 AND 1 должна быть 1, а во всех других случаях результатом будет 0 (см. рис. 1.1).

Подобным же образом в основании операции OR лежит сложное утверждение вида Р OR Q, где Р опять является одним утверждением, a Q — другим. Такое выражение является истинным тогда, когда, по крайней мере, один из его компонентов является истинным (см. рис. 1.1).

В английском языке1 нет отдельного союза, который передавал бы значение операции исключающее ИЛИ. Результатом этой операции является 1 (истина), когда одно значение на входе равно 1 (истина), а другое равно 0 (ложь). Например, высказывание вида Р XOR Q означает «или Р, или Q, но не оба»2.

Следующей булевой операцией является операция NOT (HE, отрицание) (см. сноску 1). Она отличается от AND, OR и XOR тем, что имеет только одно значение на входе. На выходе получается противоположное значение; если входящее значение операции НЕ «истина», то результатом ее применения является «ложь» и наоборот. Следовательно, если на входе мы имеем истинность или ложность высказывания Фоззи - медведь, то на выходе — истинность или ложность высказывания Фоззи не медведь.

Устройство, которое порождает результат какой-либо булевой операции при данных входных значениях, называется вентилем (gate). Вентили могут быть построены с применением различных технологий, таких как механические устройства, реле различных типов, оптические механизмы и т. д. В современных компьютерах вентили являются небольшими электронными схемами, в которых числа 0 и 1 представлены как уровни напряжения. Однако не будем вдаваться в детали. Для задач, стоящих перед нами, достаточно символического представления вентилей (рис. 1.2). Обратите внимание, что вентили, соответствующие операциям AND, OR, XOR, NOT представлены схемами, имеющими различную форму, при этом исходные значения входят с одной стороны, а результирующее значение выходит с другой.

Такие вентили, как эти, являются стандартными блоками, из которых конструируется компьютер. Важным шагом в этом направлении является схема, изображенная на рис. 1.3, которая представляет собой отдельный пример из множества существующих схем, называемых триггерами. Триггер (flip-flop) — это схема, которая на выходе имеет значение 0 или 1. Это значение остается неизменным до тех пор, пока кратковременный импульс, исходящий из другой цепи, не заставит его переключиться на другое значение. Другими словами, триггер будет переходить из одного состояния в другое только под влиянием внешнего стимула. До тех пор, пока оба значения на входе цепи равны 0 (см. рис. 1.3), результат на выходе (0 или 1) будет оставаться неизменным. Однако подача импульса 1 на верхний вход схемы приведет к тому, что значение на выходе будет равно 1, в то время как подача импульса 1 на нижний вход триггера в результате даст 0.

Рассмотрим последнее утверждение более подробно. Не зная текущего значения на выходе схемы (см. рис. 1.3), предположим, что значение на верхнем входе стало 1, а значение на нижнем входе осталось равным 0 (рис. 1.4, а). В результате этого преобразования значение на выходе вентиля ИЛИ станет равным 1, независимо от того, какое значение имеется на другом входе вентиля. В свою очередь, оба входящих значения вентиля И теперь станут равны 1, так как одно из них и так равно 1 в результате действия вентиля НЕ. Тогда на выходе вентиля И будем иметь 1, что означает, что второй вход вентиля ИЛИ теперь равен 1 (рис. 1.4, б). Этот факт является гарантией того, что значение на выходе вентиля ИЛИ будет оставаться равным 1, даже если значение на верхнем входе триггера опять станет равным 0 (рис. 1.4, б). В итоге значение на выходе триггера стало равным 1 и будет оставаться таким и после того, как значение на верхнем входе будет опять равно 0.

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

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

Конечно, существуют и другие способы построения триггера (рис. 1.5). Если вы поэкспериментируете с этой схемой, вы придете к выводу, что хотя она обладает другой внешней структурой, ее внутренние свойства остаются такими же, как и у ранее рассмотренной схемы (см. рис. 1.3). Это заключение является иллюстрацией роли абстрактных инструментов. Проектируя триггер, инженер рассматривает и альтернативные способы построения триггера с использованием стандартных блоков. Затем, когда триггер и другие основные схемы спроектированы, инженер может использовать их в качестве стандартных блоков для конструирования более сложной схемы. В свою очередь, схема элементов вычислительной машины приобретает иерархическую структуру, каждый уровень которой в качестве абстрактных инструментов использует компоненты более низкого уровня.