Библиотека программиста

«Если отладка - процесс удаления ошибок, то программирование должно быть процессом их внесения»

Э.Дейкстра

Главная страница > Разработка алгоритмов

Разработка алгоритмов

1. Алгоритмы и вычисления

Понятие алгоритма интуитивно понятно и часто используется в математике и компьютерных науках. Говоря неформально, алгоритм - это произвольная корректно определена вычислительная процедура, на вход которого подается некоторая величина или набор величин, а результатом выполнения которой является выходная величина или набор значений. Таким образом, алгоритм представляет собой последовательность вычислительных шагов, которые превращают входные величины в выходные.

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


1.2. Зачем изучать алгоритмы? Эффективность алгоритмов

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


1.3. Золотое правило разработчиков алгоритмов

Теперь рассмотрим для примера простую задачу, которая известна всем еще с начальной школы, а также метод решения этой задачи - умножение двух чисел. Эту задачу можно описать следующим образом:
Вход: 2 целых n-разрядных числа x и y
Выход: произведение чисел x · y
Рассмотрим пример для чисел x = 5678 и y = 1234. Результат известного с детства метода умножения в столбик будет выглядеть следующим образом...


2. Анализ алгоритмов 2.1. Сортировка вставками

Приступая к изучению анализа алгоритмов, мы рассмотрим достаточно простой алгоритм для задачи сортировки - сортировка методом включения. Напомним формулировка проблемы: Вход: последовательность n чисел (a1, a2,...,an) Выход: перестановка (aa1, aa2,...,aan) входной последовательности таким образом, что для всех ее членов выполняется соотношение aa1<=aa2<=...<=aan


2.2. Машина с произвольным доступом к памяти

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


2.3. Анализ алгоритма сортировки методом включения

 
При использовании любых материалов с сайта http://www.introligator.org
обратная ссылка обязательна.
Rambler's Top100 Рейтинг@Mail.ru