Мы начинаем с наиболее фундаментального понятия вычислительной техники, а именно с понятия алгоритма (algorithm). Неформально, алгоритм — это набор шагов, которые определяют выполнение какой-либо задачи1. Например, существует алгоритм для построения модели самолета (выраженный в форме инструкции), для управления стиральной машиной (обычно изображен на лицевой стороне машины), для исполнения музыки (последовательность нот в нотной записи) и для выполнения фокусов.
Перед тем как машина сможет выполнить какую-либо задачу, необходимо разработать алгоритм и представить его в форме, совместимой с машиной. Представление алгоритма, совместимое с машиной, называется программой (program). Программы и алгоритмы, которые они представляют, называются программным обеспечением (software), в отличие от самой ЭВМ, которая называется аппаратным обеспечением (hardware).
Более точно, алгоритм — это упорядоченный набор однозначных, выполнимых шагов, которые определяют конечный процесс.
Алгоритм фокуса.Эффект: Фокусник достает несколько карт из обычной колоды игральных карт и кладет их на стол изображением вниз, тщательно перемешивает их, распределяя по столу. Затем, когда зрители просят показать или черную, или красную карту, фокусник переворачивает карту нужного цвета.
Секрет и последовательность действий:
Шаг 1. Из обычной колоды карт возьмите десять красных и десять черных карт. Распределите их на столе по цвету в две колонки изображениями вверх.
Шаг 2. Объявите, что вы вытащили несколько красных и несколько черных карт.
Шаг 3. Соберите красные карты. Под видом того, что собираете их в маленькую колоду, возьмите их в левую руку и при помощи большого и указательного пальца правой руки придайте картам слегка вогнутую форму. Затем положите колоду красных карт на стол изображением вниз со словами: «В этой стопке красные карты».
Шаг 4. Соберите черные карты. Способом, описанным в шаге 3, придайте картам слегка выпуклую форму. Затем верните эти карты на стол изображением вниз со словами: «А в этой стопке черные карты».
Шаг 5. Сразу после того, как вы положите черные карты на стол, двумя руками перемешайте карты, распределяя их по поверхности стола. Объясните зрителям, что вы тщательно перемешиваете карты.
Шаг 6. Пока на столе остаются карты, расположенные изображением вниз, выполняйте следующие шаги:
6.1. Попросите зрителей назвать красную или черную карту.
6.2. Если назван красный цвет и на столе есть карта, лежащая изображением вниз, с вогнутой формой, переверните такую карту со словами «Вот красная карта».
6.3. Если назван черный цвет, и на столе есть карта, лежащая изображением вниз, с выпуклой формой, переверните такую карту со словами: «Вот черная карта».
6.4. В противном случае скажите зрителям, что больше нет карт нужного цвета, и в доказательство переверните оставшиеся карты.
Изучение алгоритмов началось как раздел математики. Действительно, математики занимались поиском алгоритмов задолго до создания современного компьютера. Главной Цель лекциию было нахождение набора указаний, который бы описывал решение всех задач определенного типа. Одним из наиболее известных примеров этих исследований является алгоритм для нахождения отношения двух сложных чисел. Другой пример — алгоритм Евклида для нахождения наибольшего общего делителя двух положительных целых чисел, открытый античным греческим математиком Евклидом.
Алгоритм Евклида.Описание: Этот алгоритм предполагает наличие на входе двух положительных целых чисел и вычисляет их наибольший общий делитель.
Последовательность действий:
Шаг 1. Присвоить переменным М и N значения большего и меньшего числа соответственно. Шаг 2. Разделить М на N и значение остатка присвоить переменной R.
Шаг 3. Если R не равно 0, тогда присвоить М значение N, присвоить N значение R и возвратиться к шагу 2; в противном случае наибольшим общим делителем является значение, присвоенное N.
Как только алгоритм решения задачи найден, выполнение этой задачи больше не требует понимания принципов, лежащих в основе алгоритма. Вместо этого процесс выполнения задачи сводится к процессу простого следования указаниям. (Мы можем следовать алгоритму деления для нахождения отношения двух чисел или алгоритму Евклида для нахождения наибольшего общего делителя, не понимая, почему этот алгоритм работает.) В известном смысле, интеллект, необходимый для решения поставленной задачи закодирован в алгоритме.
Именно благодаря этой способности собрать и передать интеллект посредством алгоритмов, мы можем конструировать машины, которые показывают разумное поведение. Следовательно, уровень интеллекта, обнаруживаемый машинами, ограничен интеллектом, который может быть передан через алгоритмы. Только если мы найдем алгоритм, который управляет выполнением задачи, мы можем построить машину, которая ее выполнит. Также если не существует алгоритма решения задачи, то решение этой задачи выходит за пределы способностей машины.
Таким образом, разработка алгоритмов является главной задачей в области вычислительной техники и, следовательно, значительная часть данной науки занимается проблемами, связанными с этой задачей. В свою очередь, мы можем обрести понимание вычислительной техники, рассмотрев некоторые из этих проблем. На первом месте находится вопрос, как разрабатывается алгоритм — вопрос, который тесно связан с проблемой решения задач вообще. Найти алгоритм решения задачи — это, в сущности, обнаружить ее решение. Значит, исследования в этой области вычислительной техники происходят из таких областей психологии, как решение задач человеком и теория обучения.
Когда найден алгоритм для решения задачи, следующий шаг — представить алгоритм так, чтобы он мог быть передан машине или другим людям. Это означает, что мы должны трансформировать понятийный алгоритм в набор однозначных инструкций. Исследования, возникшие из этой необходимости, исходили из наших знаний языка и грамматики и привели к большому количеству систем представления алгоритмов, называемых языками программирования (programminglanguage), в основе которых лежит многообразие подходов к процессу программирования, называемых парадигмами программирования. Поскольку компьютерные технологии применялись к все более и более сложным задачам, ученые обнаружили, что проектирование больших систем программного обеспечения включает в себя больше, чем просто разработку отдельных алгоритмов для выполнения требуемых действий. Оно влечет за собой также проектирование взаимодействия между этими компонентами. В результате возник новый раздел вычислительной техники, который называется разработкой программного обеспечения и происходит из таких различных областей научного знания, как аппаратура, управление проектом, руководство кадрами и проектирование языков программирования.
Другая важная область вычислительной техники занимается проектированием и конструированием аппаратов для выполнения алгоритмов. Хотя изучение архитектуры ЭВМ включает в себя обсуждение современных технологий, нашей целью не является овладение всеми деталями того, как современная архитектура ЭВМ реализуется в электрической схеме. Это завело бы нас слишком далеко в область электротехники. Кроме того, как вчерашние механические вычисляющие устройства уступили дорогу электрическим устройствам, так и современная электроника скоро может быть заменена другими технологиями, среди которых первым кандидатом является оптика. Наша Цель лекции — получить достаточное представление о современных технологиях, для того чтобы понять их применение в современных машинах и их влияние на развитие вычислительной техники.
Мы бы хотели, чтобы архитектура ЭВМ была следствием только наших знаний об алгоритмических процессах и не была ограничена возможностями технологий. То есть вместо того, чтобы позволять технологиям определять проектирование ЭВМ и, следовательно, способ представления алгоритма, мы бы хотели, чтобы наши знания были движущей силой, определяющей строение машины. С развитием технологий эта мечта приближается к реальности. Сегодня возможно построить машину, которая позволяет представить алгоритм в виде сложных последовательностей инструкций, выполняемых одновременно, или в виде системы соединений между многочисленными элементами, подобно тому, как наш мозг представляет информацию в форме связей между нейронами.
С конструированием вычислительных машин тесно связана разработка связи машины с внешним миром. Например, как поместить алгоритм в машину или сообщить ей, какой алгоритм выполнять? Решение таких проблем при условии, что от машины ожидается выполнение большого количества задач, требует решения многих проблем, связанных с согласованием действий и распределением ресурсов. Так как от машин требовалось выполнение все более и более сложных задач, компьютерная наука обратилась к изучению интеллекта человека в надежде на то, что, понимая, как рассуждает и воспринимает наш собственный мозг, мы будем в состоянии создать алгоритм, который бы имитировал эти процессы, и, следовательно, сможем передать эти способности машине. В результате возникла область вычислительной техники, которая называется искусственным интеллектом и опирается на исследования в психологии, биологии и лингвистике.
Поиск алгоритмов для решения все более и более сложных проблем ведет к вопросам, касающимся предельных ограничений алгоритмических процессов. Если не существует алгоритма для решения задачи, тогда эта задача не может быть решена машиной, то есть машины способны решать только алгоритмически разрешимые задачи.
Осознание того, что существуют задачи, не имеющие алгоритмического решения, появилось как отдельный предмет исследования в математике с публикацией теоремы о неполноте Курта Геделя в 30-х годах XX века. Эта теорема утверждает, что в любой математической теории, заключающей в себе традиционную систему арифметики, существуют утверждения, которые не могут быть ни доказаны, ни опровергнуты. Короче говоря, любое полное знание нашей системы арифметики выходит за пределы возможностей алгоритмических процессов.
Стремление к изучению ограничений применения алгоритмических методов, которое последовало за теоремой Геделя, привело математиков к проектированию абстрактных машин для выполнения алгоритмов (это было до того, как технологии позволили создать действующие машины) и исследованию теоретических возможностей таких гипотетических машин. Сейчас изучение алгоритмов и машин составляет основу вычислительной техники.
Такие условия, как ограниченные возможности хранения данных и трудоемкие процедуры программирования, ограничивали сложность алгоритмов, к которым применялись первые вычислительные машины. Однако все эти ограничения начали исчезать, машины стали использоваться для выполнения все более сложных задач. Так как попытки выразить комбинации этих задач в форме алгоритма стали подвергать испытанию способности человеческого ума, все больше исследовательских усилий было направлено на изучение алгоритмов и процесса программирования.
Именно в это время теоретические работы математиков начали приносить плоды. В результате появления теоремы о неполноте Геделя математики обратились к исследованию вопросов, касающихся алгоритмических процессов, что способствовало развитию технологий. Этот процесс подготовил возникновение новой дисциплины науки, называемой вычислительной техникой.
Сегодня эта новая дисциплина укрепилась как наука об алгоритмах. Как мы видим, эта наука занимается широким спектром вопросов, которые связаны с такими разными предметами, как математика, аппаратура, психология, биология, управление торгово-промышленной деятельностью и лингвистика. В последующих лекциях мы обсудим многие разделы этой науки. В каждом случае нашей лекции будет представлены главные идеи раздела и темы текущих исследований.
Важно различать вычислительную технику как науку и ее применение (различие, аналогичное отличию физики от машиностроения). Физика является наукой, которая пытается объяснить отношения между силой, массой и ускорением. Машиностроение представляет собой применение этой науки. Инженеру-механику следует понимать физику, но инженер, в зависимости от своей специализации, должен также обладать знаниями о различных видах стали, составе бетона или доступности шарикоподшипников на рынке. Физик интересуется, как изменяется закон Ньютона при подходе Эйнштейна. Следовательно, не следует ожидать, что работы физика будут содержать обсуждение грузовых ограничений различных шкивов, присутствующих на рынке, или указаний правительства относительно ремней безопасности автомобиля.
Определим круг вопросов, которыми занимается вычислительная техника.
♦ Какие задачи имеют алгоритмическое решение?
♦ Как можно облегчить поиск алгоритма?
♦ Как можно усовершенствовать технику представления и передачи алгоритма?
♦ Как можно применить наши знания об алгоритмах и технологиях для создания лучших машин?
♦ Как можно проанализировать и сравнить характеристики различных алгоритмов?
Всеми этими вопросами занимается наука об алгоритмах.
Рисунок 2 – Алгоритм в вычислительной технике
Влияние на общество.Научный и технологический прогресс подрывает основания, на которых базировались общественные решения в прошлом, и даже бросает вызов многим общественным принципам. В чем различие между наличием интеллектуального поведения и наличием самого интеллекта? Когда начинается жизнь? Когда она заканчивается? Чем различаются растение и животное? Есть ли жизнь в других солнечных системах? Такие вопросы заставляют человека пересмотреть свои убеждения и часто — изменить их.
Вычислительная техника является источником таких вопросов в различных областях жизни. В юриспруденции возникают проблемы, касающиеся того, в какой степени возможно владеть (быть хозяином) программным обеспечением, касающиеся права и ответственности, которые влечет за собой эта собственность. В этике человек сталкивается с вызовом традиционным принципам, на которых основывается поведение. В правительстве возникает вопрос о том, в какой мере компьютерные технологии и их применение должны контролироваться государством. И во всем обществе обсуждается вопрос о том, дают ли новые применения компьютерных технологий большую свободу или, наоборот, ограничивают ее.
Решение этих проблем требует базовых знаний в соответствующей науке или технологиях. Например, если общество должно принять решение относительно хранения и размещения ядерных отходов, члены этого общества должны осознавать последствия воздействия радиации, понимать, что требуется для защиты от опасности радиационного заражения и трезво оценивать промежуток времени, в течение которого сохраняется риск радиационного заражения. Также, чтобы рассудить, следует ли позволять правительству или компаниям создавать большие интегрированные базы данных, содержащие информацию о гражданах или потребителях, члены общества должны обладать элементарными представлениями о возможностях, ограничениях и развитии технологий создания баз данных. Эта книга дает основные знания для того, чтобы вы могли подойти к решению таких вопросов осознанно. Действительно, многие разделы посвящены социальным, этическим и правовым вопросам. Например, мы обсуждаем проблему секретности в разделе, посвященном Сети и технологиям создания баз данных, а проблему собственности на программное обеспечение в разделе, касающемся разработки программного обеспечения. Хотя эти вопросы не являются частью вычислительной техники, они важны как для читателей, начинающих изучение этой дисциплины, так и для людей, специализирующихся на предметах, связанных с применением вычислительных машин.
Контрольные вопросы
1. Охарактеризуйте основные этапы развития вычислительных машин.
2. Какова роль абстракции в вычислительной технике?
3. Что включает понятие «алгоритм» в контексте понятия «вычислительная техника»?
4. Какое влияние оказывает развитие вычислительной техники на общество?
