CFA LogoCFA Logo Computer
Загрузка поиска
Новости Компьютеры Прайс-лист [Новое] Прайс-лист [Б/У] Для ноутбуков Конфигуратор ПК Заказ, Оплата, Доставка Сервис объявления Драйвера Статьи Как нас найти Контакты
Новости
RSS канал новостей
Тайваньская компания MSI осуществила сегодня анонс фирменной модели графического ускорителя GeForce ...
Компания Manli опубликовала официальный пресс-релиз, посвященный своей новой видеокарте. Энтузиастам ...
Компания Sony накануне раскрыла некоторые подробности доступности своего нового флагманского смартфона ...
В списке новинок формата фаблет японская компания Sony готовит нового флагмана, который в настоящее ...
Компания Acer сделала наконец официально доступным свой новый ноутбук, рассчитанный на профессиональных ...
Самое интересное
Программаторы 25 SPI FLASH Адаптеры Optibay HDD Caddy Драйвера nVidia GeForce Драйвера AMD Radeon HD Игры на DVD Сравнение видеокарт Сравнение процессоров

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

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

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

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

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

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

Рис. 1. Учебник «Наука исключения и сокращения»   Рис. 2. Глиняная табличка

Рис. 3. Трактат «Начала»

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

Рис. 4. Джон фон Нейман

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

Однако единый стандарт был не за горами. В 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. Правила рисования блоков   Рис. 6. Блок-схема

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

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

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

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

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

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

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

Рекомендуем ещё прочитать:






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

Ваше имя:
Ваша почта:

RSS
Комментарий:
Введите символы: *
captcha
Обновить






Рейтинг@Mail.ru
Хостинг на серверах в Украине, США и Германии. © www.sector.biz.ua 2006-2015 design by Vadim Popov