Понятие алгоритма
Понятие алгоритма является одним из основных понятий современной информатики. Термин «алгоритм» (алгорифм) происходит от имени среднеазиатского ученого IX века аль-Хорезми, который разработал правила выполнения четырех арифметических действий в десятичной системе счисления.
Вплоть до 30-х годов прошлого столетия понятие алгоритма носило сугубо интуитивный характер и имело скорее методологическое, чем математическое значение. Общей теории алгоритмов фактически не существовало, а под алгоритмом понимали конечную совокупность точно сформулированных правил, которые позволяли решать те или иные классы задач Основными свойствами такого «интуитивного» понятия алгоритма являются [1, с. 177]:
1. Массовость алгоритма. Подразумевается, что алгоритм позволяет решать не одну конкретную задачу, а некоторый класс задач данного типа. В простейшем случае массовость обеспечивает возможность изменения исходных данных в определенных пределах.
2. Детерминированность алгоритма. Процесс применения правил к исходным данным (путь решения задачи) однозначно определен.
3. Результативность алгоритма. На каждом шаге процесса применения правил известно, что считать результатом этого процесса, а сам процесс должен прекратиться за конечное число шагов.
В течение длительного времени пока дело касалось задач, имеющих решение, математиков устраивало такое определение алгоритма. Совсем другое дело, когда задача или класс задач могут и не иметь решения. В этом случае требуется строго формализованное понятие алгоритма, чтобы иметь возможность доказать его отсутствие.
В 20-х годах XX века задача такого определения понятия алгоритма стала одной из центральных математических проблем. Решение ее было получено в середине 30-х годов в работах известных математиков Д. Гильберта, К. Геделя, А. Черча, С. Клини, Э. Поста и А. Тьюринга в двух эквивалентных формулировках: на основе особого класса функций, получивших название рекурсивных функций, и на основе абстрактных автоматов.
|
|
Таким образом, первоначально теория алгоритмов возникла в связи с внутренними потребностями теоретической математики. Математическая логика, основания математики, алгебра, геометрия и анализ остаются и сегодня одной из основных областей приложения теории алгоритмов. Кроме того, теория алгоритмов оказалась тесно связанной и с рядом областей лингвистики, экономики, физиологии мозга и психологии, философии и естествознания. Примером одной из задач этой области может служить описание алгоритмов, реализуемых человеком в процессе умственной деятельности.
Вместе с тем в 40-х годах прошлого века в связи с созданием электронных вычислительных и управляющих машин возникла область теории алгоритмов, тесно взаимодействующая с информатикой. Появление ЭВМ способствовало развитию разделов этой теории, имеющих ярко выраженную прикладную направленность.
В общем случае при составлении алгоритма конкретной задачи актуальное значение имеет такое представление алгоритма, которое позволяет наиболее быстро реализовать его механизированным путем, и в частности с помощью ЭВМ. При этом для решения задачи с помощью ЭВМ ее необходимо запрограммировать, т.е. представить алгоритм решения задачи в виде последовательности команд, которые может выполнять машина. Однако процесс записи алгоритма в виде последовательности машинных команд очень длительный и трудоемкий. Его также можно автоматизировать, если использовать для записи алгоритмов алгоритмические языки, представляющие собой набор символов и терминов, связанных синтаксической структурой. С их помощью можно по определенным правилам описывать алгоритмы решения задач. Алгоритмы, записанные в алгоритмическом языке, автоматически самой ЭВМ с помощью специальной программы-транслятора могут быть переведены в машинные программы для конкретной ЭВМ.
|
|
Итак, алгоритм – конечный набор правил или команд (указаний), позволяющий исполнителю решать любую конкретную задачу из некоторого класса однотипных задач.
Исполнителем может человек, группа людей, станок, компьютер и др. С учетом особенностей исполнителя составленный алгоритм может быть представлен различными способами: с помощью графического или словесного описания, в виде таблицы, последовательностью формул, записанных на алгоритмическом языке (языке программирования) и т.д.
Алгоритм, записанный на «понятном» компьютеру языке программирования, называется программой.
К основным типам алгоритмических структур относят [2, с. 150-156]:
· линейный алгоритм;
· алгоритмическая структура «ветвление»;
· алгоритмическая структура «выбор»;
· алгоритмическая структура «цикл».
Алгоритм, в котором команды выполняются последовательно одна за другой, называется линейным алгоритмом.
В алгоритмической структуре «ветвление» та или иная серия команд выполняется в зависимости от истинности условия.
|
|
В алгоритмической структуре «выбор» выполняется одна из нескольких последовательностей команд при истинности соответствующего условия.
В алгоритмической структуре «цикл» серия команд (тело цикла) выполняется многократно.
Литература
1. Акулов, О.А. Информатика: базовый курс: учеб. пособие для студентов / О.А. Акулов, Н.В. Медведев. – М.: Омега-Л, 2005. – 552 с.
2. Угринович, Н.Д. Информатика и информационные технологии. Учебник для 10-11 классов / Н.Д. Угринович. – М.: Бином. Лаборатория знаний, 2002. – 512 с.
Языки программирования
Под языком программирования будем понимать совокупность средств и правил представления алгоритма в виде, приемлемом для компьютера. Существует разделение всех языков на две большие группы – языки высокого и низкого уровней.
Языком самого высокого уровня считается человеческий язык, и когда компьютер станет его легко понимать, то он вплотную приблизится к человеку. Языком самого низкого уровня считается язык так называемых машинных кодов. Все остальные алгоритмические языки лежат где-то посредине.
С помощью языков низкого уровня создаются очень эффективные и компактные программы, так как разработчик получает доступ ко всем возможностям процессора. С другой стороны, при этом требуется очень хорошо понимать устройство компьютера, затрудняется отладка больших приложений, а результирующая программа не может быть перенесена на компьютер с другим типом процессора. Подобные языки обычно применяют для написания небольших системных приложений, драйверов устройств, модулей стыковки с нестандартным оборудованием, когда важнейшими требованиями становятся компактность, быстродействие и возможность прямого доступа к аппаратным ресурсам.
Особенности конкретных компьютерных архитектур в языках высокого уровня не учитываются, поэтому создаваемые программы на уровне исходных текстов легко переносимы на другие платформы, для которых создан транслятор этого языка. Разрабатывать программы на языках высокого уровня с помощью понятных и мощных команд значительно проще, а ошибок при создании программ допускается гораздо меньше.
Языки программирования принято делить на пять поколений [1, с. 572]. В первое поколение входят языки, созданные в начале 50-х годов, когда первые компьютеры только появились на свет. Это был первый язык ассемблера, созданный по принципу «одна инструкция – одна строка». Программы представляли собой длинные логические последовательности нулей и единиц.
Расцвет второго поколения языков программирования пришелся на конец 50-х – начало 60-х годов. Тогда был разработан символический ассемблер, в котором появилось понятие переменной. Он стал первым полноценным языком программирования. Благодаря его возникновению заметно выросли скорость разработки и надежность программ.
Появление третьего поколения языков программирования принято относить к 60-м годам. В это время родились универсальные языки высокого уровня, с их помощью удается решать задачи из любых областей. Такие качества новых языков, как относительная простота, независимость от конкретного компьютера и возможность использования мощных синтаксических конструкций, позволили резко повысить производительность труда программистов. Понятная большинству пользователей структура этих языков привела к написанию небольших программ (как правило, инженерного или экономического характера) значительное число специалистов из некомпьютерных областей. Подавляющее большинство языков этого поколения успешно применяется и сегодня.
С начала 70-х годов по настоящее время продолжается период языков четвертого поколения. Эти языки предназначены для реализации крупных проектов, повышения их надежности и скорости создания. Они обычно ориентированы на специализированные области применения, где хороших результатов можно добиться, используя не универсальные, а проблемно-ориентированные языки, оперирующие понятиями узкой предметной области. Как правило, в эти языки встраиваются мощные операторы, позволяющие одной строкой описать такую функциональность, для реализации которой на языках младших поколений потребовались бы тысячи строк исходного кода.
Рождение языков пятого поколения произошло в середине 90-х годов. К ним относятся также системы автоматического создания прикладных программ с помощью визуальных средств разработки, без знания программирования. Главная идея, которая закладывается в эти языки, – возможность автоматического формирования результирующего текста на универсальных языках программирования. Инструкции же вводятся в компьютер в максимально наглядном виде с помощью методов, наиболее удобных для человека, не знакомого с программированием.
Примерами языков высокого уровня, широко используемых во всем мире являются FORTRAN (Фортран), COBOL (Кобол), Algol (Алгол), Pascal (Паскаль), Basic (Бейсик), С (Си), C++ (Си++), Java (Джава, Ява).
Первое место по популярности в мире занимает язык Basic. Разработан первый Basic в 1964 г. сотрудниками Дартмутского колледжа Дж. Кемени и Т. Курцем. Интересно происхождение названия языка. В 19 веке один английский миссионер выделил из английского языка триста наиболее употребительных слов, назвал их Basic English и стал обучать туземцев. Опыт оказался весьма успешным, и контакты с аборигенами значительно упростились. Создатели языка Basic стремились достигнуть того же эффекта – облегчить понимание между «туземцами» – начинающими программистами, и компьютерами.
Идея оказалась удачной, и на десятилетия язык Basic стал основным в деле вовлечения в программирование новых и новых адептов. Большое достоинство Бейсика, из-за которого его изучение продолжается и поныне – это возможность создавать диалоговые программы. За прошедшие годы было создано несколько версий языка – GW-Basic, MSX-Basic, Turbo Basic, Quick Basic, и, наконец, мощный Visual Basic.
Программа, подготовленная на языке программирования, проходит этап трансляции, когда происходит преобразование исходного кода программы в объектный код, который далее пригоден к обработке редактором связей. Редактор связей – специальная программа, обеспечивающая построение загрузочного модуля, пригодного к выполнению.
Трансляция может выполняться с использованием средств компиляторов или интерпретаторов. Компиляторы транслируют всю программу, но без ее выполнения. Интерпретаторы, в отличие от компиляторов, выполняют пооператорную обработку и выполнение программы.
Существуют специальные программы, предназначенные для трассировки и анализа выполнения других программ, так называемые отладчики. Лучшие отладчики позволяют осуществить трассировку (отслеживание выполнения программы в пооператорном варианте), идентификацию места и вида ошибок в программе, «наблюдение» за изменением значений переменных, выражений и т. п. Для отладки и тестирования правильности работы программ создается база данных контрольного примера.
Системы программирования включают:
· компилятор;
· интегрированную среду разработчика программ;
· отладчик;
· средства оптимизации кода программ;
· набор библиотек (возможно с исходными текстами программ);
· редактор связей;
· сервисные средства (утилиты) для работы с библиотеками, текстовыми и двоичными файлами;
· справочные системы;
· документатор исходного кода программы;
· систему поддержки и управления проектом программного комплекса.
Инструментальная среда пользователя представлена специальными средствами, встроенными в пакеты прикладных программ, такими, как:
· библиотека функций, процедур, объектов и методов обработки;
· макрокоманды;
· клавишные макросы;
· языковые макросы;
· программные модули-вставки;
· конструкторы экранных форм и отчетов;
· генераторы приложений;
· языки запросов высокого уровня;
· языки манипулирования данными;
· конструкторы меню и многое другое.
Дальнейшим развитием локальных средств разработки программ, которые объединяют набор средств для комплексного их применения на всех технологических этапах создания программ, являются интегрированные программные среды разработчиков. Основное назначение инструментария данного вида – повышение производительности труда программистов, автоматизация создания кодов программ, обеспечивающих интерфейс пользователя графического типа, разработка приложений для архитектуры клиент-сервер, запросов и отчетов.
Литература
1. Информатика. Базовый курс / Симонович С.В. [и др.] – СПб: Питер, 2005. – 640 с.
2. Сафронов И.К. Бейсик в задачах и примерах / И.К. Сафронов. – СПб.: БХВ-Петербург, 2003. – 224 с.
3. Информатика: Учебник / Под ред. Н.В. Макаровой. – М.: Финансы и статистика, 2005. – 768 с.