АРХИВ СТАТЕЙ ЖУРНАЛА «МОЙ КОМПЬЮТЕР» ЗА 2003 ГОД

Биография алгоритмов

• Все журналы \ Номер 17/240 `2003 от 28.04.2003 \ Биография алгоритмов

Анастасия КОВАЛЕВА nastusha82@ua.fm

Алгоритм. Помню, как первый раз столкнулась с этим словом. Было это в школе, в классе пятом, когда мне было задано подготовить доклад о том, что такое алгоритм и откуда произошел этот термин. Благодаря походу в библиотеку я узнала, что этим страшным словом называется предписание, определяющее процесс перехода от исходных данных к искомому результату. От чего легче мне, правда, не стало, все равно я сразу ничего не поняла, хоть и добыла информацию о том, откуда произошло это слово. А история такова: в 820 г. арабский математик аль-Хорезми в своем учебнике «Наука исключения и сокращения» (Рис. 1) проиллюстрировал выделение полного квадрата на примере уравнения x2+10x=39. Эта книга сыграла большую роль в развитии математики. От названия книги, которое на арабском звучало «Аль-Джабр Ва-Аль-Мукабала», возникло слово «алгебра», а термин «алгоритм» появился от имени автора книги аль-Хорезми, которое в латинских переводах книги превратилось в algorismi. В итоге я все-таки разобралась с алгоритмом, и доклад был сдан. Однако я и не предполагала, что мне еще столько раз придется с ним столкнуться.

Происхождение

Каждый, кто пробует себя в программировании, в явной или неявной форме сталкивается с алгоритмами. Давайте разберемся, а как же так получилось, что алгоритмы из математики перекочевали в программирование. Обратимся еще раз к истории. Зачатки алгоритмов можно найти еще в глубокой древности до появления книги аль-Хорезми. Приблизительно в 1800 году до н.э. некий вавилонянин изложил на глиняной таблице алгоритм расчета времени, которое потребуется на увеличение вдвое определенного объема зерна при годовом приросте в 20% (Рис. 2). В III веке до нашей эры греческим математиком Евклидом был написан трактат «Начала», где можно найти самый древний алгоритм, используемый и по сей день, — нахождение наибольшего общего делителя двух чисел (Рис. 3). С дальнейшим развитием науки математики увеличивалось количество и разнообразие алгоритмов, пока XX век не устроил им основательную встряску. Появились задачи, не имеющие решения. Для доказательства того, что такую задачу нельзя решить, необходимо доказать, что алгоритма решения не существует. А для этого нужно было четко определить понятие «алгоритм». Чем и занялась новая наука —теория алгоритмов. С появлением ЭВМ теория алгоритмов и компьютерная наука шли рука об руку. Английский математик Алан Тьюринг, задавшись целью описать задачи, не имеющие решения, создал в 1936 году «универсальную машину», которую можно назвать прообразом компьютера. В 1948 году Тьюринг занялся программированием реального компьютера. В кибернетике алгоритм помог эффективно задавать последовательность сигналов. В свою очередь, ЭВМ подвигли теорию алгоритмов на изучение сложности алгоритма и его оптимизацию.

Интересно, что и блок-схему, которую вы представляете, когда слышите слово «алгоритм», придумал математик. Это был Джон фон Нейман, который иллюстрировал блок-схемой модель столкновения ядерных частиц (Рис. 4). Преимущества графического способа представления алгоритмов были очевидны. Благодаря своей компактности и наглядности, представление в виде связанных между собой блоков, соответствующих определенным действиям, получило большое распространение. Сначала каждый из крупных производителей компьютеров разрабатывал свою систему блоков, которые отражали его подход к обработке информации. Пытаясь превзойти конкурентов, компании даже выпускали собственные трафареты для рисования блок-схем алгоритмов, которые тогда были более популярны, чем специальное программное обеспечение, включая специально разработанный для рисования блок-схем язык SFL (Systems Flowchart Language — язык системы блок-схем). Свои блок-схемы имели и отдельные организации, например, военно-воздушные силы США.

Стандартизация

Однако единый стандарт был не за горами. В 1961 году Международная организация стандартов (ISO) основала комитет по Компьютерам и обработке информации. На подкомитет X3.6, в который входили представители все тех же компьютерных компаний и компаний-пользователей, была возложена обязанность разработки стандартов для блок-схем. Со своей задачей он справился. В 1963 году был выпущен стандарт, в котором определены все основные термины, касающиеся компьютерных алгоритмов, а также правила рисования блоков (Рис. 5). Но блок-схемы не стояли на месте. Развитие языков программирования привело к необходимости введения новых блоков. Стандарт 1963 года был пересмотрен несколько раз. Он претерпел ряд значительных изменений в 1965 году и небольших корректировок в 1966 и 1968. В 1970 американский стандарт был приведен в соответствие с ISO. Нельзя не упомянуть про советские заслуги в области стандартизации блок-схем. С 1980 года действовал ГОСТ 19.003-80 Схемы алгоритмов и программ. Обозначения условные графические. В 1990 году он был сменен другим ГОСТом, который соответствует стандарту ISO 5807-85 —ГОСТ 19.701-90 Схемы алгоритмов, программ данных и систем, который действителен и сейчас. Что представляют собою эти стандарты и что же они нам предписывают? Прежде всего, вы можете ознакомиться с основными определениями, касающимися блок-схем. Но главное предназначение стандарта — определить внешний вид блоков и их предназначение. Можно увидеть следующие группы: символы данных, символы процесса, символы линий и специальные символы. Для каждого из них указывается форма, но не размер (Рис. 6). На вашей совести соблюдение пропорций, которые определяются по двум размерам а и b (b=1,5a), в масштабе вас никто не ограничивает.

Коэффициент полезного действия

Факт огромного значения алгоритмов для развития компьютерной науки неоспорим. Но вопрос эффективности использования алгоритмов в программировании у некоторых вызывает сомнения. Начинающий программист сталкивается с блок-схемами алгоритмов в большинстве случаев не добровольно. Это происходит либо в школе, либо уже в вузе, когда к простенькой программе приходится еще и рисовать блок-схему. У большинства это вызывает недоумение. «Я написал программу за 5 минут, а теперь мне придется полчаса рисовать к ней алгоритм», — возмущается будущий хакер. Однако по мере постижения искусства программирования, а значит, и с усложнением программ, становится ясно, что без алгоритма во многих случаях не обойтись. Нет, теперь вы уже не будете разрисовывать нахождение максимума в массиве. Но вот глобальную последовательность действий приходится нарисовать, чтобы потом не запутаться.

В кругах психологов, преподавателей и IT-специалистов разразился спор о пользе алгоритмов. Проводились исследования эффективности использования графических инструкций и алгоритмов. Например, Камманн в 1975 получил положительные результаты выполнения задачи набора сложного телефонного номера. Эксперименты были проведены с профессионалами Bell Telephone Laboratories и домохозяйками. Применение графической инструкции, указывающей варианты использования различных телефонных кодов, привело к меньшим ошибкам, чем в случаях с текстовыми инструкциями. Ученые Райт и Рейд, напротив, в 1973 году получили лучшие результаты для письменных инструкций. Перед испытуемыми была поставлена задача выбора механизма космического полета. Результатом должен быть правильный выбор времени, расстояния и стоимости. Когда доходило до решение задачи по памяти без каких-либо инструкций, добровольцы из группы, где применялась письменная инструкция, справлялись лучше.

Толчком к бурной полемике стала работа ученых Университета Индианы (Шнайдерман, Майер, МкКей, Хеллер), выпущенная в 1977 году. Первоначально они намеревались доказать повышение качества работы программиста при использовании блок-схем. Исследования были основаны на сравнении результатов выполнения различных заданий по программированию на языке FORTRAN студентов 2 курса при применении блок-схем и без них. Было проведено 5 экспериментов. В первом студентов разделили на две группы, одна из которых должна была составить блок-схему на заданную задачу и написать к ней программу. Вторая группа посвящала все время программированию. Во втором эксперименте проверялось понимание программы с использованием блок-схемы алгоритма и без нее. Студентам были заданы две более сложные задачи. Первая группа получила блок-схему алгоритма для программы 1, в то время как программа 2 должна была быть понята без алгоритма. Вторая группа студентов имела прямо противоположное задание. Третий эксперимент касался понимания и дебага. В ходе него было выделено 2 группы: студенты, которые ранее имели дело с блок-схемами, и те, кто встретились с ними лишь на самом тестировании. Вторая группа получила дополнительные 10 минут на выполнение задания. В каждой группе были выделены подгруппы, одна из которых работала без алгоритма, другая — с детализированной блок-схемой (micro-flowchart), третья — с обобщенной блок-схемой (macro-flowchart). Требовалось найти три ошибки в программе и исправить их. Студенты также должны были оценить, насколько они поняли программу, и, в случае использования блок-схемы, насколько последняя была полезна. В четвертом эксперименте изучалась помощь блок-схем при модификации программы. Было выделено 3 группы, каждая из которых работала без алгоритмов, с микро блок-схемой и макро блок-схемой соответственно. Согласно выданной инструкции, студенты должны были найти место, где необходимо модифицировать программу, и выполнить правильно модификацию. Учитывались правильность выполнения и затраченное время. Последний опыт касался выполнения задания вручную по полученной программе, программе и алгоритму, либо только алгоритму.

Результаты, полученные во всех опытах, очень удивили Шнайдермана и его коллег. Ученые предполагали, что результаты студентов, использовавших в задании блок-схему, будут намного выше тех, кто программирует без нее. Однако значительной разницы не наблюдалась. Напротив, с некоторыми заданиями справились лучше как раз те, кто работали без блок-схемы алгоритма. В тех экспериментах, где сравнивались микро и макро блок-схемы, результаты получались выше для макро блок-схем. Авторы объясняли это тем, что детализированная блок-схема, занимающая несколько листов, сложнее воспринималась, а также не несла никакой новой информации кроме той, которую можно было получить из программного кода. Из трех вариантов — блок-схема с программой, только программа и только блок-схема, выигрывал второй вариант. Выводы, которые были сделаны учеными, гласили, что блок-схема уступает программному коду, т.к. не может отразить всех подробностей языка программирования. Исходя из результатов экспериментов, понимание и эффективность работы благодаря ей не улучшается. Поэтому использование блок-схемы не несет большой пользы при программировании, скорее наоборот, отнимает время у разработчика. Однако Шнайдерман не отрицал, что полученные результаты вплотную зависят от тех задач, которые были поставлены перед программистами, а также от уровня их знаний. В эксперименте участвовали начинающие программисты, перед которыми стояли довольно простые задачи. Поэтому нужно было провести схожие эксперименты с опытными программистами и решением задач разного уровня сложности. Кроме того, в экспериментах ученых университета Индианы не был правильно учтен временной критерий, т.к. студенты всех групп (за исключением эксперимента №3) получали одинаковое время на выполнение задания, либо вообще не были ограничены по времени. Хотя именно время, которое тратится при использовании алгоритма и без него, важно учитывать.

Положительные результаты получили ученые Брук и Дункан (1980), Канниф и Тейлор (1987), Сканлан (1989), а также Шнайдерман в своем новом исследовании (1982). На этот раз он сравнивал понимание, отладку и редактирование программ с помощью листинга программы, псевдокода и графического представления важных структур данных. Наименьшие результаты были получены в группе студентов, использующих листинг, а наибольшие — в группе, которая использовала графические иллюстрации. Эксперименты, давшие положительные результаты, были проведены Крювсом и Зиглером, сотрудниками факультета Компьютерной науки университета Западного Кентукки. Они выделили 2 группы: первая работала с блок-схемами, вторая — с программами (Рис. 7). Студенты должны были ответить на вопросы, касающиеся трех блок-схем/программ разной сложности. Критерием оценки результатов были правильность ответов, уверенность в своих ответах, а также затраченное время. Результаты для программы легкого уровня были близки с теми, которые были получены в Университете Индианы, т.е. отличия между двумя группами по всем трем критериям не превышали 10%. Однако с увеличением сложности программ результаты второй группы ухудшались. Наибольшее различие ощущалось во временных результатах для третей задачи. Со сложной задачей первая группа справилась почти в два раза быстрее. Таким образом, в ходе экспериментов были доказаны четыре гипотезы. Начинающие программисты достигнут более точных результатов (1), будут работать быстрее (2) и будут более уверены в своей работе (3), используя блок-схемы алгоритмов, чем при использовании структурированного кода. Превосходство блок-схемы над структурированным кодом будет увеличиваться с усложнением задач (4). Интересно было бы провести подобные эксперименты на профессиональных программистах.

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

Идёт загрузка...

Данную страницу никто не комментировал. Вы можете стать первым.

Ваше имя:
Ваша почта:
Комментарий:
Введите символы или вычислите пример: * Обновить