|
Во все времена своего существования человек нуждался в инструментах для счета, В первобытные времена таким инструментом у человека была его собственная рука. (Пальцевый счет использовался человеком и на более высоких ступенях развития цивилизации — в Древней Греции и в Древнем Риме.)
Затем человек стал использовать для счета самые примитивные устройства — сначала это были деревянные палочки с зарубками — бирки (первое упоминание о них на барельефе фараона Сети I относится примерно к 1350 г до н. э.); китайцы, персы, индийцы пользовались для представления чисел и счета ремнями и веревками с узлами. Записывать числа и вести счёт на бумаге было невозможно по той простой причине, что ее еще не существовало, пергамент же был слишком дорог.
Острая необходимость в более совершенном инструменте для записи чисел и счета привела к появлению абака«(в переводе на русский язык — дощечка, покрытая пылью). По свидетельству Геродота египтяне им пользовались уже в V в. до н. э. По существу, этот инструмент похож на обычные русские счеуы.
В XVII в. были изобретены логарифмы и сразу вслед за этим был создан новый счетный инструмент — логарифмическая линейка. Примерно в то же время на свет появились арифметические машины Шиккарда, Паскаля, Лейбница. Это уже были механические устройства, использующие многочисленные шестерни, колеса, зубчатые рейки и т. п. Они умели «запоминать» числа и выполнять элементарные арифметические операции. В действие они приводились человеческой рукой, причем зачастую для этоГо требовались недюжинные усилия.
Особую роль в развитии вычислительной техники сыграли работы выдающегося английского ученого Чарльза Беббиджа. В начале XIX в. он предложил идею создания «разностной» машины, которая предназначалась для вычисления значений многочленов без вмешательства человека в процесс счета, т. е. машина должна была считать автоматически. И такая машина была им создана. Но Беббидж мечтал об универсальной машине, на которой можно было бы
рёшать произвольные вычислительные задачи. Всю жизнь посвятил Беббидж разработке такой машины, которую сам он назвал «аналитической». Беббидж составил подробную схему машины, выполнил огромное количество чертежей отдельных узлов, воплотил в металле некоторые ее части. Но полностью создать машину он, конечно же, не мог. Идеи Беббиджа намного опередили свое время, уровень развития науки и техники того времени не позволил ему до конца решить поставленную задачу. И хотя с тех пор прошло полтора столетия, все современные вычислительные машины по своей структуре в значительной степени похожи на аналитическую машину Беббиджа.
Так, по проекту Беббиджа машина должна была обладать запоминающим устройством для хранения чисел (он называл его «складом»), устройством, способным выполнять арифметлческие операции (по Беббиджу — «мельница»), устройством, управляющим последовательностью действий машины, устройством ввода и вывода информации, т. е. практически всеми основными элементами современных вычислительных машин.
Разумеется, машина Беббиджа, как и предшествующие арифметические машины, задумывалась как чисто механическое устройство. По проекту автора, она должна была выполнять сложение за одну секунду, умножение и деление примерно за одну минуту. Вводить информацию и управлять вычислительным процессом Беббидж предлагал с помощью перфокарт, т. е. картонных карточек с пробитыми на них отверстиями. Эту идею он заимствовал у француза Жаккара,, который в начале XIX в. изобрел способ управления ткацкими станками с помощью перфокарт.
Беббидж высказал исключительно важную мысль о возможности изменения хода вычислений в зависимости от промежуточных результатов. Такое свойство машины уже позволяло решать на ней весьма слржные задачи. Однако для того чтобы заставить машину выполнять необходимые вычисления, нужно было составить для нее программу, т. е. последовательность инструкций (команд) для всех ее устройств. И первые такие программы для аналитической машины Беббиджа были составлены талантливым математиком Адой Лавлайс (дочерью поэта Байрона), которую по праву можно назвать первым программистом в истории человечества.
Конечно же, эти программы существовали только на бумаге, так как сама машина так и не была построена и не было возможности выпрлнить эти программы. Лишь примерно через сто лет идеи Беббиджа начали реально воплощаться в жизнь.
В 1937 г. болгарин А. Атанасов приступил к созданию электронной вычислительной машины, предназначенной для решения задач математической физики. Одновременно проект большой релейной машины предложил сотрудник Гарвардского университета в США Г. Айткен. Машина была построена в 1944 г. и называлась «Марк-1».
Но это была электромеханическая машина, а в 1945 г. в США появилась первая электронная вычислительная машина (ЭВМ) — ЭНИА1С Это была уже ламповая машина на электронных реле. Однако она имела существенный недостаток — для того чтобы изменить режим работы, нужно было каждый раз вручную перекоммутировать схему
Следующий важный шаг в развитии вычислительных машин сделал знаменитый американский математик Джон фон Нейман. Он предложил вводить в память машины наряду с исходными числовыми данными также и саму программу. Такой принцип был назван принципом хранимой программы. Теперь уже можно было рассматривать программу тоже как объект для воздействия, т. е. ее уже можно было изменять прямо в процессе вычислений. Программа могла теперь сама себя перерабатывать и изменяться по мере необходимости в зависимости от результатов вычислений.
В Советском Союзе первая электронная вычислительная машина была создана под руководством академика С. А. Лебедева в 1951 г. Называлась она МЭСМ — малая электронная счетная машина. В 1952 г. была построена самая мощная в то время в Европе машина — БЭСМ-1. А в 1953 г. появились первые серийные советские ЭВМ — «Стрела» и М-2, причем эти машины по меркам того времени обладали широкими вычислительными возможностями и высоким быстродействием.
Далее развитие вычислительной техники пошло семимильными шагами. Если в 1952 — 1953 гг. электронных машин в мире было несколько десятков, то в 1965 г. — около 40 тыс., в 1970 г. — более 100 тыс., в 1977 г. — -около 400 тыс. и т. д. В настоящее время самостоятельно используемых ЭВМ в мире насчитывается уже несколько миллионов,- не считая микроЭВМ, встроенных в различные приборы и автоматы.
Но не только росло количество ЭВМ, еще быстрее они совершенствовались.
Электронные вычислительные машины (или, как теперь их часто называют, компьютеры) принято делить на поколения. В основу градации обычно кладут элементную базу, на которой строятся машины, а также их возможности, область применения и т. д. Деление это весьма условно, ибо случается, что машина, построенная на элементной базе одного поколения, по структурным особенностям и возможностям относится к машинам другого поколения. (Так, например, серийная советская машина БЭСМ-6 по элементной базе относится к ЭВМ второго поколения, а по своей архитектуре близка к машинам третьего поколения.)
К настоящему времени обычно насчитывают четыре или даже пять поколений ЭВМ.
Машины первого поколения строились на электронных лампах. Их быстродействие достигало 20 тыс. операций в секунду. Программы писались на языке машины. Причем каждая машина имела свой, присущий только ей язык, и если программа была написана на этом языке, то на другой ЭВМ ее уже использовать было нельзя. Объем памяти машин был весьма небольшим. Программист сам распределял оперативную память под программу, исходные данные, полученные результаты.
В ЭВМ второго поколения на смену электронным лампам пришли полупроводниковые приборы -транзисторы, которые позволили довести быстродействие до нескольких сотен тысяч операций в секунду, одновременно значительно увеличив надежность машин. Произошел переход от написания программ на языке машины к написанию их на алгоритмических языках высокого уровня. Запись программы на алгоритмическом языке использует некоторые слова и стандартную математическую символику. Такая запиеь значительно проще и нагляднее программы, написанной на языке машины. Программист, составляющий такую программу, може? и вовсе не знать языка машины. Перевод программы с алгоритмического языка на язык машины осуществляется самой машиной с помощью специальной программы-транслятора.
В конце 60-х гг. наступил следующий этап в развитии ЭВМ — появились машины третьего поколения. Их рождение связано с ростом возможностей технологии полупроводников. На одном кремниевом, кристалле, а точнее кристаллической пластинке, удалось создать электронную схему, содержащую сотни и даже тысячи простейших элементов. Такую схему назвали интегральной. Она стала эквивалентной целому блоку ЭВМ. Машины, построенные на интегральных схемах, имеют быстродействие порядка миллиона операций в секунду. Использование интегральных схем повысило надежность, уменьшило размеры ЭВМ.
В машинах третьего поколения стал применяться принцип распараллеливания работ. ЭВМ стала одновременно обрабатывать несколько программ. Общение с ЭВМ осуществляется сразу с нескольких терминалов, т. е. удаленных от ЭВМ пультов, снабженных клавиатурой и экраном. Каждый работающий за таким пультом решает свою задачу и не ощущает, что на этой же ЭВМ одновременно с ним другие пользователи решают свои задачи.
Последнее достижение на пути миниатюризации — микроминиатюрные интегральные схемы, когда на крошечной кремниевой пластине содержатся уже десятки тысяч электронных компонент. Это так называемые большие интегральные схемы (БИС). Более того, розданы сверхбольшие интегральные схемы (СБИС), насчитывающие на поверхности кристалла сотни тысяч электронных компонент. БИС и СБИС стали элементной базой ЭВМ четвертого поколения. Новое поколение значительно превосходит старые ЭВМ по. быстродействию, достигая десятков и даже сотен миллионов операций в секунду. Если для машин первых поколений требовались большие помещения, слож-
ные системы охлаждения и вентиляции, то современные машины значительно меньше по размерам и менее прихотливы к условиям .эксплуатации. Кстати, отметим, что их миниатюризация позволяет не только экономить помещение — она сказывается и на быстродействии. В. самом деле, сейчас скорости работы различных устройств ЭВМ настолько высоки, что начинает играть роль время прохождения сигнала от одного устройства к другому, хотя эти скорости и сопоставимы со скоростью света. Уменьшая длину пути прохождения сигнала, удается повысить скорость работы ЭВМ. f Современные ЭВМ обладают значительно большими возможностями, чем старые машины, — на них, как уже говорилось, можно одновременно решать несколько задач, к ним можно обращаться с удаленных выносных пультов (терминалов). Кроме того, они значительно надежнее и, что немаловажно, стоимость решения задач на них значительно ниже, чем на старых ЭВМ. Очень часто машины используют не поодиночке, их объединяют в мощные вычислительные комплексы и сети. Тогда их возможности резко возрастают.
Широко обсуждается вопрос о создании ЭВМ пятого поколения, которые обеспечат новый уровень взаимодействия человека с ЭВМ. Отличительной их особенностью должен стать -повышенный уровень интеллекта.
Разработчики стремятся к тому, чтобы с машинами можно было общаться на естественном языке, чтобы с их помощью накапливались знания, чтюбы ЭВМ могли обучать и обучаться.
В настоящее время очень широкое распространение получили персональные ЭВМ. Эти малогабаритные машины, сравнительно дешевы, неприхотливы, просты в эксплуатаций, но обладают довольно большими возможностями при решении широкого круга задач. Размещать такие ЭВМ-можно на обычном письменном столе.
Миниатюризация элементной базы привела к созданию микропроцессоров. Микропроцессоры могут быть вмонтированы в наручные часы и теперь на руке у нас не только собственно часы, но и. календарь, и калькулятор. Микропроцессоры управляют работой стиральной машиныавтомата, запоминают номера телефонов в телефонном аппарате,, без микропроцессоров трудно себе представить современную радиоаппаратуру.
Менялись Машины, менялись поколения ЭВМ, а вместе с ними менялся и характер их применения. Если поначалу они создавались и использовались восновном для решения разного рода вычислительных задач; то в дальнейшем сфера их применения необычайно расширилась. Теперь это уже и задачи обработки результатов физических экспериментов, и моделирование различных, объектов естествознания, и задачи управления как народным хозяйством в целом," так и отдельными предприятиями и отраслями производства.
- Трудно переоценитыроль, которую играют ЭВМ к геологии и
медицине, в биологии и лингвистике, в химии и экономике, в исследовании космоса и ядерной физике. Машины помогают конструкторам в создании самолетов и космических кораблей, архитекторам в проектировании зданий. Машины управляют станками, составляют расписание движения поездов и самолетов, переводят тексты с одного языка на другой, управляют полетом космических аппаратов, ставит диагнозы болезней.
С помощью ЭВМ удается решать задачи, решение которых раньше считалось невозможным из-за огромного объема вычислений, или даже если п было возможным, то терялся смысл из-за слишком большой продолжительности решения задачи. Эксперименты и подсчеты, требовавшие раньше тысяч часов рутинной работы сотен людей, теперь выполняют за несколько минут и с высокой точностью.
Скажем, решение задачи краткосрочного прогноза погоды требует большого количества сложных математических расчетов.* Ясно, что не слишком велика была бы польза, если бы мы выполнили все необходимые расчеты для прогноза погоды на завтра лишь послезавтра. Машина все подсчитает точно и в срок. Если же прогноз иногда и не оправдывается, то не по вине машины, а из-за того, что неудачно составлены те уравнения, которые ей пришлось решать, или, как говорят, неудачно построена математическая модель изучаемого явления — в данном случае модель погоды. Или же неточны исходные величины, заданные в этой модели.
Все более широкое применение находят ЭВМ и как средства обучения. Машина может быть самым внимательным и терпеливым преподавателем. Причем занятия она ведет с каждым [обучаемым индивидуально; фиксирует любой пробел в знаниях и способствует глубокому и прочному усвоению изучаемой дисциплины.
Очень часто говорят, что ЭВМ осуществляет обработку данных, говорят об алгоримах обработки данных, об исходных данных, о кодировании данных и т, д. В том же смысле употребляют термин «обработка информации», поэтому важно [уяснить себе, что под этим понимается.
Слово «информация» переводится на русский язык как сведения. Информацию любой природы, зафиксированную [каким-либо образом, мы и будем называть данными. Информация может быть зафиксирована в книгах с помощью букв, знаков, картинок и цифр или каким-либо другим способом/ например в виде записей на магнитных лентах, на фотокадрах и, пока еще не очень хорошо известным нам способом, в мозге человека. [Физическую среду, на которой (или внутри которой), зафиксирована информация, называют носителем информации. Носителем информации может быть бумага, перфолента, перфокарта, магнитный диск и многое другое. Современная техника предлагает все новые и новые носители информации, основанные на использовании электрических, магнитных и оптических свойств раз-
личных материалов и даже свойств отдельных молекул. Существенно, чтобы носитель информации позволял читать зафиксированную информацию. То, что написано в книгах, может читать человек, то, что зафиксировано с помощью электрических сигналов, магнитных записей может «читать» соответствующее техническое устройство.
Данные, физически зафиксированные на любом носителе информации, с той или иной степенью точности можно представлять себе в виде последовательности символов.
В самом деле, всякая книга, может быть рассмотрена как последовательность символов, обозначающих буквы, цифры и другие знаки. Газетная фотография представляет собой последовательность чередующихся черных и светлых точек. Чтобы убедиться в этом, рас-ч-смотрите газетную фотографию через увеличительное стекло. Вообще, любую фотографию с некоторой степенью приближения можно рассматривать как последовательность точек разного цвета или степени затемнения. Любой график также можно рассматривать как последовательность координат, выраженных числами, т. е. как некоторую последовательность цифр.
Очень важно понять, что все сведения об объектах реального мира, о явлениях природы,, о результатах размышлений, о научных законах и выводах человечество научилось фиксировать в виде последовательностей символов, в виде данных. Вычислительные машины прямо приспособлены именно для обработки символьных последовательностей, для их преобразования из одной формы в другую, для выполнения арифметических и логических операций над такими последовательностями, Неудивительно поэтому, что в лексикон, связанный с функционированием ЭВМ, вошли такие выражения, как «обработка слов», «анализ предложений», «обработка строк». И еще важно отметить, что человечеству понадобилось не так уж много различных символов, чтобы написать миллионы томов книг. Наприер, в текстах книг на русском языке использовано 33 буквы, 10* цифр и около десятка других различных знаков, т. е. с помощью всего нескольких десятков различных символов, удается зафиксировать колоссальные объемы информации. Как это делается, мы с вами хорошо знаем — из букв формируются слова, из слов, — предложения, из предложений — осмысленный текст статьи, книги и т. д. Те же данные можно представить, используя меньшее число букв. Например, в латинском алфавите букв меньше, чем в русском (их 26). Но нам известно, что все написанное с использованием русского алфавита можно перевести на любой другой язык без потери сведений, содержавшихся в исходном тексте.
Более того, оказывается, достаточно всего двух различных символов, т. е. алфавита, состоящего всего из двух букв, чтобы с их помощью зафиксировать все имеющиеся в распоряжении человечества сведения, всю_ информацию. Мы знаем, например, что телеграфист с помощью азбуки Морзе, используя всего два символа — точку и и тире, может передать любой текст. Этот факт и лежит в основе использования в ЭВМ алфавита, состоящего всего из двух символов.
Приведенные рассуждения имели своей целью объяснить читателю, почему ЭВМ, первоначально предназначенные для быстрого автоматического выполнения вычислений, оказались универсальным инструментом обработки данных самого различного происхождения и характера. Они способны автоматически выполнять алгоритмы преобразования символьных последовательностей, и этого оказалось достаточно, чтобы использовать их для выполнения любых алгоритмов и решать задачи, не имеющие отношения к расчетам: задачи типа анализа текстов, формирования чертежей, сложные логические задачи.
Укоренившееся название «электронная вычислительная машина» отражает лишь очень небольшую часть возможностей ЭВМ по обработке данных.
* В основе дальнейшего развития научно-технического прогресса лежит широкое, повсеместное внедрение в промышленное производ-" ство и другие сферы деятельности человеческого общества последних достижений науки, техники, технологии. Интенсификация производства, научной деятельности, образования немыслима без автоматизации, без внедрения автоматизированных линий, гибко перестраиваемых производств, без автоматизации управленческой деятельности. В настоящее время основным звеном, по существу, всех [систем автоматизации является цифровая автоматика и вычислительная техника. Партии и правительство уделяют развитию этой отрасли знаний и производства самое серьезное/внимание. Принят перспективный план развития вычислительной техники и ее повсеместного внедрения в народное хозяйство. В ближайшие годы с вычислительной техникой и ее применением будут связаны тем или иным образом все члены общества, вовлеченные в общественное производство.
Процесс широкого внедрения вычислительной техники иногда называют, процессом информатизации, общества, а все, что связано с применением ЭВМ, их разработкой, созданием программ для них, называют информатикой. В каком-то смысле понятие «информатика» подменяет собой то, что называется кибернетикой. Как мы знаем, кибернетика определяется как наука об общих законах управления в зкивой ц неживой природе. На современном этапе управление в многообразных сферах «неживой» природы (в производстве, науке, технике) осуществляется с помощью ЭВМ. В этом смысле информатику можно назвать частью кибернетики.
В то же время широкое применение вычислительной техники для научных расчетов, научного прогнозирования, анализа результатов
экспериментов, учета и контроля, т. е. в сферах, прямо не связанных с управлением, позволяет считать, что информатика охватывает другой, более широкий класс проблем и решает более разнообразные задачи по сравнению с кибернетикой в классическом ее понимании.
Если же отвлечься от самых общих определений, то под информатикой понимают науку, связанную:
1) с разработкой вычислительных машин и систем, с технологией их создания;
2) с разработкой математических моделей естествознания и общественных явлений о целью их строгой формализации;
3) с обработкой данных, созданием численных и логических методов решения задач, сформулированных на этапе построения математической модели;
4) с разработкой алгоритмов решения задач управления, расчета . и анализа математических моделей;
5) с программированием алгоритмов, созданием программного обеспечения ЭВМ.
Огромный вклад в развитие информатики в ее современном понимании внесли выдающиеся ученые и организаторы науки академики С. А. Лебедев, М. А. Лаврентьев, М. В. Келдыш, В. М. Глунк ков и др.
Интенсификация производственной деятельности, ускорение научно-технического прогресса невозможны без широкого массового внедрения средств вычислительной техники во все сферы деятельности нашего общества. Этим определена необходимость изучения основ информатики и вычислительной техники на всех уровнях образования, начиная со средней школы, техникума, ПТУ и т. д. Возникает естественный вопрос — посильная ли это задача достижение в нашей стране всеобщей компьютерной грамотности. Тут напрашивается “аналогия, которую подметил академик Б. Сендов (НРБ). Он сказал,! что нынешняя ситуация напоминает эпоху начала телефонизации: когда только появилась телефонная связь, в городах былб всего несколько десятков или сотен телефонных аппаратов. Чтобы позвонить по телефону, надо было снять трубку, соединиться с «телефонной барышней», назвать ей номер или даже просто имя абонента (не так уж много их было и нетрудно было запомнить их [все). «Барышня» с помощью проводков со штеккерами на концах соединяла о абонентом, и происходил разговор. Люди с ужасом думали о том, что будет, если количество телефонов в городах резко возрастет. Сколько же тогда понадобится «барышень», чтобы обеспечить бесперебойную связь?! Прошло время, в больших городах теперь сотнй тысяч и даже миллионы телефонных аппаратов. И каждый из нас сам выполняет роль телефонной барышни. Достаточно снять трубку и набрать нужный номер, как тут же произойдет соединение. Правда при этом нам помогает АТС (автоматическая телефонная станция) — устройство исключительно сложное. И именно это самое устройство дает нам возможность о такой легкостью соединяться с любым або-
центом города, а также без вмешательства телефонистки, набрав код другого города в нашей стране или даже за рубежом, мы можем разговаривать с самыми удаленными точками планеты.
Аналогичная ситуация происходит и с использованием вычислительной техники. На заре создания ЭВМ, в эпоху машин первого поколения, писать программы умели лишь профессионалы-программисты. Математики, физики, биологи — все, кому надо было решать задачи на машине, обращались за помощью к этим профессионалам, и те составляли соответствующие программы.
Шло время, появились алгоритмические языки высокого уровня, близкие к естественным языкам общения. Уже значительно более широкий круг специалистов мог самостоятельно работать на ЭВМ. И чем более совершенствовалась вычислительная техника, чем более она усложнялась, тем проще становилось общение о ней, т. е. все происходит по той же схеме, что и с телефонизацией. И для того чтобы использовать вычислительную технику, решать на ней различные задачи, вовсе не обязательно глубоко и подробно знать ее устройство. Ведь мы умеем пользоваться телевизором, технически весьма сложным прибором, хотя далеко не все знают тонкости его конструкции. Современная ЭВМ* — очень сложное устройство, аппаратные средства которой в сочетании с программным обеспечением помогают просто и эффективно решать с ее помощью разнообразные задачи. Общение с ЭВМ становится настолько простым, что ему уже можно обучать каждого, кто этого пожелает, т. е. такому общению можно научить уже в школе. Но обучая основам информатики, нужно ставить себе целью не только и даже не столько научить обучаемого написанию программ для ЭВМ, сколько развить в нем способность к алгоритмическому мышлению, привить умение строить и анализировать алгоритмы решения различных задач.
. Умение выделить в процессах, явлениях природы, производственной деятельности людей «алгоритмическую» сторону эквивалентно пониманию механизмов этих явлений и процессов, отчетливому восприятию их причинно-следственной связи.
В предлагаемой книге, рассчитанной на широкий круг читателей, разумеется, нельзя охватить все направления, входящие в состав информатики. Главное внимание в ней авторы сосредоточили на изложении понятий алгоритмизации и программирования. При этом авторы стремились к элементарному изложению, понимая под этим не столько упрощение, а главным образом доходчивость изложения подчас не очень простых вещей, связанных о данным предметом.
ГЛАВА 1
АЛГОРИТМЫ И АЛГОРИТМИЗАЦИЯ
§ 1.1. Понятие алгоритма
В своей повседневной деятельности нам постоянно приходится сталкиваться с разнообразными правилами, предписывающими последовательность действий, цель которых состоит в достижении некоторого необходимого результата. Подобные правила очень многочисленны. Например, мы обязаны следовать вполне определенной системе правил, чтобы позвонить по телефону-автомату (опустить монету, снять трубку, набрать номер и т. д.) или пройти через турникет в метро, вычислить произведение двух многозначных чисел или найти корни квадратного уравнения. Нужно выполнить определенную последовательность действий, чтобы сварить суп или подняться в лифте на нужный этаж, с помощью циркуля и линейки разделить отрезок пополам или вычислить сумму бесконечно убывающей геометрической прогрессии, приготовить лекарство или связать на спицах свитер. Примеры такого рода можно продолжать неограниченно. Их часто называют алгоритмами.
В особо четких формулировках предстают перед яами алгоритмы, связанные с правилами выполнения арифметических, действий и геометрических построений. Не будет большой ошибкой сказать, что элементарная (и не элементарная) математика в значительной степени сводится к нахождению правил решения задач.
Название «алгоритм» связано с именем выдающегося математика» древности Мухаммеда бен-муса альгХорезми (IX в. н. э.). Он изложил общие правила выполнения действий над числами, представленными в десятичной форме, которыми мы пользуемся до сих пор. Существенным было то, что эти правила могли быть применены к любым числам.
До этой поры существовало очень много приемов выполнения арифметических операций, в которых учитывались те или иные особенности конкретных чисел, над которыми проводились эти операции. Например, если один из сомножителей представляет число, состоящее из одних девяток, то к другому сомножителю нужно дописать число нулей, равное числу девяток в первом сомножителе, и затем из получившегося числа вычесть второй сомножитель. Тем самым мы получим нужный результат. Например, если число 999 нужно умножить на 5, мы к цифре 5 добавим три нуля (так как в первом сомножителе три девятки), получим 5000 и затем вычтем второй сомножитель, т. е. число 5. Результатом будет число 4995, которое и является произведением чисел 999 и 5.
Мы и сейчас пользуемся многими приемами быстрого устного счета. Например, чтобы умножить любое число на 5, надо приписать к нему 0 и разделить полученное число пополам. Или, чтобы умножить число на 25, достаточно умножить это число на 100, т. е. при писать к нему два нуля, и разделить результат на 4. Однако такого рода приемы можно применять только в тех случаях, когда хотя бы один из сомножителей имеет специальный вид (все девятки, 5, 25 и т. д.).
Аль-Хорезми предложил правила, пригодные во всех случаях и одинаковые для любых пар чисел. Сторонников методики аль-Хо-резми начали называть алгоритмиками, а под словом «алгоритм» стали понимать систему правил, обладающих некоторыми определенными свойствами.
Действия согласно той или иной инструкции, являющейся алгоритмом, для получения определенного результата предполагают наличие некоторых исходных данных.
Например, исходными данными при выполнении арифметической операции над двумя числами является эта пара чисел, а результатом — одно число.
Первым свойством алгоритма является дискретный, т. е, пошаговый характер определяемого им процесса.
Другим важнейшим свойством алгоритмов является массовость. Смысл данного понятия заключается в том, что существует некоторое множество объектов, которые могут служить исходными данными для рассматриваемого алгоритма. Например, для алгоритмов выполнения арифметических операций — сложения, вычитания, умножения и деления — такими данными являются все действительные числа. Когда складываем, например, два числа 27 и 35, то пользуемся алгоритмом сложения столбиком ...
Здесь мы не просто складываем цифры в соответствующих разрядах, но и в зависимости от результата сложения осуществляем перенос единиц в более старшие разряды. Заметим, кстати, что когда мы складываем однозначные числа, е. попросту говоря, цифры, то
пользуемся таблицей сложения: ...
Разумеется, этой таблицей мы пользуемся и применяя алгоритм сложения многозначных чисел.
То же самое можно сказать и об умножении двух чисел. Перемножая цифры, мы пользуемся лишь хорошо известной нам таблицей умножения. Если же мы перемножаем многозначные числа, то тут приходится применять алгоритм умножения столбиком: ...
Здесь мы пользуемся таблицей умножения, есть и запоминание результата умножения цифр, и перенос в старшие разряды, и алгоритм сложения столбиком. Заметим, что алгоритм умножения столбиком включает в себя как составную часть алгоритм сложения.
Подчеркнем еще раз, что алгоритм умножения остается одним и тем же для любых пар чисел.» Иными словами, исходными данными для этого алгоритма могут быть любые пары чисел. Конечно, такой способ умножения чисел не всегда самый рациональный. Так, при применении этого алгоритма в том случае, когда один из сомножителей состоит только из девяток, мы затратим больше усилий по сравнению с приемом быстрого счета. Но смысл массовости алгоритма состоит как раз в том, что .он одинаково пригоден для всех случаев, требует лишь механического выполнения цепочки некоторых простых действий и при этом нет нужды в затратах творческой энергии.
В свое время противники методов аль-Хорезми именно за это пренебрежительно относились к «алгоритмикам», снявшим, покров таинственности с искусства .выполнять арифметические операции.
Приведем пример еще одного алгоритма, а именно алгоритма деления отрезка пополам с помощью циркуля и линейки. Исходными данными здесь уже являются не числа, а заданный отрезок. Действий — построение с помощью циркуля и линейки.
Для того чтобы разделитьотрезок пополам, возьмем раствор циркуля, равный длине отрезка, и из концов отрезка опишем этим радиусом окружности (рис. 1.1). Через точки пересечения окружностей проведем прямую. Эта прямая пересечет заданный отрезок в точке, которая, как известно, и является серединой данного отрезка.
Подчеркнем, что приведенная последовательность действий обладает свойсгвом массовости, поскольку ее можно применять к любому _ отрезку для отыскания его середийы.
Читатель, конечно же, заметил, что для решения поставленной задачи вовсе не обязательно, чтобы радиус описываемых окружностей был равен длине заданного отрезка — достаточно, чтобы эти радиусы были одинаковыми и большими, чем половина длины отрезка. Наше ограничение преследовало цель сделать «алгоритм четким и однозначным»
Остановимся еще на одной важной особенности, присущей каждому алгоритму. Предполагается, что алгоритм понятен для исполнителя, т. е. исполнитель алгоритма знает, как его выполнять. При этом исполнитель алгоритма, выполняя его, действует «механически». Очевидно, что формулировка алгоритма должна быть настолько точна и однозначна, чтобы могла полностью определять все действия исполнителя.
Анализ приведенных, выше алгоритмов показывает, что если применять алгоритмы повторно к одним цтем же исходным данным, то мы всегда будем получать один и тот же результат. Например, если применять рассмотренный ранее алгоритм деления отрезка пополам к одному и тому же отрезку, то каждый раз будем получать одну и ту же точку.
И если при этом каждый раз сравнивать результаты, полученные после соответствующих шагов алгоритмического процесса, то окажется, что при одних и тех же исходных данных эти результаты всегда будут одинаковыми. Таким образом, можно говорить об определенности и однозначности алгоритмов.
Теперь можно более точно определить алгоритм как систему правил, сформулированную на языке, понятном исполнителю, и определяющую цепочку действий, в результате выполнения которых мы приходим от исходных данных к искомому результату. Такая цепочка действий называется алгоритмическим процессом, а каждое действие — его шагом. Число шагов для достижения результата обязательно должно быть конечным. Кроме того, алгоритм должен обладать свойствами массовости, определенности и однозначности.
Механический характер алгоритма, его определенность и однозначность позволяют в качестве исполнителя рассматривать и специальные машины-автоматы.
Неправильно было бы думать, что для любой задачи существует лишь один алгоритм ее решения. Пусть, например, надо сосчитать количество зрителей на трибунах стадиона. Можно сосчитать количество зрителей в каждом секторе и потом их сложить. А можно посчитать количество зрителей, сидящих в первом ряду по всему периметру стадиона, сложить с количеством зрителей, сидящих во
втором ряду, затем в третьем и т. д. Результат в обоих случаях, естественно, должен получиться одинаковым.
Однако далеко не всегда даже для внешне кажущейся легкой задачи удается найти хоть какой-нибудь алгоритм ее решения.
Так, на протяжении тысячелетий математики пытались решить задачу о квадратуре круга: с помощью циркуля и линейки построить квадрат, равновеликий кругу с заданным радиусом г, т. е. так, чтобы пгг=я2, где х — сторона искомого квадрата. Лишь в XIX в. усилиями выдающихся математиков Лежандра и Линдемана была строго доказана неразрешимость этой задачи. В самом деле, из условия задачи следует, , что x=rV~~n. Поэтому надо осуществить построение так, чтобы получить отрезок, длина которого в раз больше длины данного отрезка. Оказывается «умножить» графически с помощью циркуля и линейки отрезок на число можно лишь тогда, когда это число является корнем алгебраического уравнения с целыми коэффициентами. Лежандр установил, что я — число иррациональное (т. е. непредставимо в виде p/q, где р и q — взаимно простые числа), а Лин-деман — что оно (а значит, и Уя), к тому же, и трансцендентное, т. е. не удовлетворяет никакому алгебраическому уравнению с целыми коэффициентами.
Столь же известна другая задача древнегреческой математики — задача о трисекции угла, т. е. о делении угла на три равные части с помощью циркуля и линейки. Как и в случае задачи о квадратуре круга, неразрешимость этой задачи была доказана лишь в XIX в. и. гоже алгебраическими методами.
ХУиомянем, наконец, еще об одной, замечательной, задаче древности — удвоение куба: требуется построить куб, объем которого был бы вдвое больше объема заданного куба. Лишь в 1337 г. было доказано, что не существует алгоритма, который бы позволил с помощью циркуля и линейки решить поставленную задачу.
Заметим, что во всех трех знаменитых задачах древности для их решения разрешалось пользоваться только циркулем и линейкой. И оказалось, что этих средств недостаточно, чтобы решить каждую из поставленных задач. Однако отсюда вовсе не следует, что эти задачи нельзя решить, применяя какие-либо другие средства. Те неё древние греки находили для этого хитроумные способы.
В указанных примерах речь шла о задачах, для которых (и это строго доказано) не существует алгоритмов решения (т. е. задачи неразрешимы) в рамках фиксированного набора допустимых действий, в данном случае — построения только с помощью циркуля и неразмеченной линейки.
Есть также множество проблем, о которых мы и сейчас не можем сказать, разрешимы они ила нет, и если разрешимы, то каким образом;
Так известна .гипотеза о том, «что любое четное число представимо в виде суммы двух простых чисел. Но утверждение это пока не доказано, и не ясно, удастся ли его когда-либо доказать или опровергнуть.
Итак, из сказанного выше вытекает, что для некоторых задач -существует несколько алгоритмов их решения, для некоторых таких алгоритмов вообще не существует, и, наконец, есть задачи, для которых мы не знаем, существуют или нет алгоритмы их решения.
§ 1.2. Алгоритмические системы
Когда речь идет о построении алгоритма решения какой-либо конкретной задачи, то мы явно или неявно предполагаем известными те объекты, когорые будут исходными данными для нашего алгоритма. Например, в задаче деления отрезка пополам в качестве таких объектов выступают отрезки произвольной длины. При построении алгоритма нахождения корней квадрагного уравнения такими объектами являются тройки любых чисел, определяющие коэффициенты уравнения ах2+6х+с=0.
Второе, что мы предполагаем известным, — это те действия, с помощью которых строятся шаги алгоритма. Например, в той же задаче о делении отрезка мы разрешаем использовать только действия с циркулем и линейкой, а в задачах решения уравнения разрешается выполнять действия сложения, вычитания, умножения, деления и извлечения квадратного корня. Иными словами, мы предполагаем известными все возможности исполнителя алгоритма, т. е. знаем, что умеет делать исполнитель (ведь алгоритм обязательно адресован какому-то конкретному исполнителю).
Мы также должны знать, как формулировать шаги заданий, чтобы их понял исполнитель, т. е.. знать, какой язык понятен исполнителю алгоритма. Наконец, при построении алгоритма решения какой-либо конкретной задачи мы должны знать, что собой будет представлять результат: число, точку иа прямой и т. д., т. е. мы должны знать множество объектов, к которым принадлежит результат. Но с помощью циркуля и линейки решаегся не только задача деления отрезка пополам, ио и целый ряд геометрических построений.
С помощью арифметических операций также строятся алгоритмы решения самых различных задач.
Набор средств и понятий, позволяющих строить не один алгоритм, а множество алгоритмов, решающих различные задачи, будем называть алгоритмической системойГ Алгоритмических систем мржет быть много и каждая из них определяется:
1) множеством входных объектов, подлежащих обработке алгоритмами данной системы;
2) свойствами исполнителя алгоритмов, т. е. набором тех действий, которые может выполнять исполнитель;
3) множеством, к которому могут принадлежать результаты выполнения алгоритмов данной системы;
4) языком, на котором формулируются алгоритмы, адресованные испблнителю.
Заметим, что множество входных объектов (исходных данных), и множество результатов часто совпадают. Например, в алгоритмах вычислений арифметических выражений и исходные данные, и результаты — числа. Но в ряде случаев исходные данные и результаты могут оказаться совершенно разной природы. Например, во многих задачах управления в качестве исходных данных алгоритмов, решающих задачи планирования, выступают числа, выражающие производительность, мощность предприятий, запасы ресурсов. Результатом же работы алгоритма может оказаться информация, приводящая к решению построить новый завод.
Другой пример. Исходными данными для алгоритма поиска нужной книги в книгохранилище служат фамилия автора, название книги, год и место ее издания.
Ответом служат числа, указывающие номер стеллажа и номер полки где следует искать книгу.
Что касается действий, которые может выполнять ислрлнитель, то они также могут, резко отличаться, в различных алгоритмических системах. Например, в задачах геометрических построений предполагается, что исполнитель владеет циркулем и линейкой — может npoводить прямые линии, выбирать произвольную точку, соединять точки, чертить окружности, отыскивать точки пересечения В алгоритмах управления роботом-манипулятором в зависимости от конструкции робота предполагаются известными те элементарные движения, которые он может выполнять, например шоворот механической руки, движение вперед-назад, захват детали и т. д.
Язык алгоритмической системы тесно связан с исполнителем и не должен включать в свой состав указаний на недопустимые н или невозможные для «исполнителя действия,, а также обращения к входным объектам, если они не принадлежат. алгоритмической системе. (это же касается и результатов). Он должен быть точно понимаем исполнителем.
Если исполнитель алгоритма — человек, владеющий русским.языком, то в качестве языка для формулировки алгоритмов вполне можно использовать русский язык.
В алгоритмических системах, предназначенных для построения алгоритмов обработки данных, т. е. обработки символьных последовательностей любого происхождения, - в качестве множества исходных, объектов рассматриваются наборы символов конечной длины. А как мы уже знаем, наборами символов можно обозначать числа слова текста, предложения, т. е. представлять информацию любого содержания.
Результат обработки данных также представляет собой наборы символов. Тем самым в этих алгоритмических системах множество-исходных данных и множество результатов совпадают. А вот наборы действий, которые может выполнять исполнитель в различны алгоритмических системах для обработки данных, весьма сильно различаются.
Если исполнитель — человек, то в качестве одного действия ему можно, например, предложить выбрать максимальное число из трех за данных чисел.
В то же время вычислительная машина в одно действие не может решать такую простую задачу, и такое действие для нее превращается в несколько шагов алгоритма. Набор ее операций весьма ограничен, однако, комбинируя их в нужной последовательности, можно построить . весьма сложные алгоритмы решения множества различных задач.
Соответственно язык, на котором задаются шаги заданий, адресованных компьютеру, значительно беднее, чем язык, адресованный человеку, так как набор действий, которые может выполнять компьютер, сравнительно невелик. В то же время такой язык более точен, v его предложения не допускают различных толкований и алгоритм, написанный на таком языке, представляет собой последовательность команд, адресованных различным устройствам ЭВМ, совсем не похожую на привычные нам фразы естественного языка. По своей сути язык ЭВМ формален, а то что он все-таки назван языком, имеет под собой довольно глубокое основание. Несмотря на несхожесть его с обычным языком, бн имеет свой алфавит, свою грамматику.
Алгоритм, адресованный ЭВМ как исполнителю, представляет собой некий текст, т. е. некоторую последовательность символов.
В связи с этим отменим одно очень важное обстоятельство. Если мы имеем дело с алгоритмической системой, предназначенной для составления алгоритмов обработки данных, т. е. любых последовательностей символов, то открывается следующая принципиально важная возможность.
Как мы уже отметили, четвертой составной частью, алгоритмической системы является язык формулировки алгоритмов. А текст, в том числе текст алгоритма, на любом языке есть также символьная последовательность, которую можно преобразовывать в той же алгоритмической системе. Следовательно, открывается возможность составлять алгоритмы, которые в свою очередь будут преобразовывать алгоритмы, обрабатывая тексты, реализующие эти алгоритмы.
При решении задач с помощью ЭВМ этим широко пользуются, автоматически преобразуя алгоритмы из одной формы в другую или автоматически меняя алгоритм в ходе вычислений. Это создает ту удивительную логическую гибкость, которая и превратила ЭВМ в принципиально новый инструмент обработки данных. Недаром говорят об искусственном интеллекте, об интеллектуальных системах, построенных на основе ЭВМ, и недаром пытаются с помощью ЭВМ моделировать работу мозга человека.
Итак, в алгоритмической системе можно строить самые различные алгоритмы. Но не всегда~конкретный алгоритм, построенный в выбранной алгоритмической системе, будет пригоден для работы со всеми ее входными объектами. Например, в алгоритмической системе, предназначенной для обработки числовой информации, в качестве исходных данных определены все числа. В тех алгоритмах, которые включают в себя операцию деления, в качестве исходных данных нельзя использовать нуль, хотя он и принадлежит множеству исходных данных алгоритмической системы. Тем самым для конкретного алгоритма не все исходные данные оказываются допустимыми. В этих случая* говорят, что данный конкэдртный алгоритм неприменим к таким исходным данным.
Например, в алгоритмической системе геометрических построений с прмощью циркуля и линейки можно рассмотреть задачу построения треугольника по трем заданным отрезкам. Исходными данными в этой системе является множество троек всевозможны отрезков. Однако не любая такая тройка отрезков будет допустимой для алгоритма построения треугольника. Хорошо известно, что треугольник построить нельзя, если длина какого-либо отрезка окажется больше суммы длин двух других отрезков. Поэтому можно сказать, что алгоритм построения к этим исходным данным неприменим, а сами исходные данные являются для него недопустимыми.
Мы уже говорили, что при выполнении алгоритма результат должен быть получен за конечное число шагов. Если же окажется, что при применении алгоритма к каким-либо исходным данным алгоритмический процесс продолжается бесконечно, то и в этом случае говорят, что алгоритм к этим исходным данным неприменим, а сами исходные данные являются для него недопустимыми.
Рассмотрим, например, алгоритм деления двух чисел. И пусть наша цель состоит в том, чтобы при делении двух чисел получить при этом абсолютно точный результат. Возникает вопрос: для всех ли чисел алгоритм деленияуголком дает точный результат за конечное число шагов? KOHEЦ ФPAГMEHTA КНИГИ
|
