Главная » Статьи для тега "алгоритма"

Быстрая сортировка Free Pascal

Добавлено Дата: 3 May, 2014 категория: Free Pascal

В 1962 г. известный математик Хоар (C. A. R. Hoare) опубликовал алгоритм сортировки, за которым закрепилось название quicksort. Идея этого алгоритма удивительно проста. Сначала выбирается "средний" элемент в сортируемом масси- ве. Все, что больше этого элемента, переносится в правую часть массива, а все, что меньше, — в левую. После первого шага "средний" элемент оказывается на своем месте. Затем аналогичная процедура повторяется для каждой половины массива. На каждом последующем шаге размер обрабатываемого фрагмента массива уменьшается вдвое. Количество операций, которое требуется, в среднем, для реа-

Читать »

Выполнение алгоритма поиска в глубину в Visual C# (Sharp)

Добавлено Дата: 12 March, 2014 категория: C#

Все необходимые компоненты алгоритма поиска в глубину, включая тесты, были реализованы, и теперь мы готовы приступить к его тестированию. Для первого теа попробуем найти маршрут между Монреалем и Сиэтлом. На рис. 4.7 можно веть, что существуют два варианта этого маршрута: через Лос-Анджелес и через Торонто. Но наш алгоритм выдает следующий, довольно странный, результат (мы не рассматривали, как выводить результаты на экран, но это довольно легко сдать, применив оператор цикла for для обработки массива foundRoute, который содержит города найденного маршрута):

Читать »

Как я разбирался с форматами ADPCM

Добавлено Дата: 7 May, 2012 категория: Программирование звука

Хотя  IMA  действительно  предоставляет  полный  пакет  спецификаций  на  IMA ADPCM,  в  том  числе  примеры  программ,  реализующих  данный  стандарт,  мне  не удалось  отыскать  детальной  информации  по  реализациям  последнего,  подготовленным Microsoft и Apple. Кроме того, чтобы не допустить возможного нарушения авторских  прав  IMA,  я  намеренно  не  использовал  разработанные  этой  организацией  примеры.  Кое-какой  полезный  материал  мне  удалось  отыскать  в  Internet, в  том  числе  реализацию  базового  алгоритма,  написанного  Джеком  Дженсеном QackJansen),  и  раздел  «Техническая  поддержка  разработчиков  Apple  1081»  (Apple Developer  Support  TechNote  1081),  где  был  выделен  ряд  фундаментальных  отличий между версиями этого алгоритма от Microsoft и Apple.

Читать »

Процесс раскрытия данных – ЧАСТЬ 3

Добавлено Дата: 7 March, 2012 категория: Microsoft SQL Server, Базы данных

Развертывание

Существует несколько методов внедрения функций раскрытия данных в приложения.

?               Непосредственное создание XMLA, взаимодействующего со службой анализа с помощью протокола SOAP. Это позволяет использовать полную функциональность раскрытия данных ценой углубленного программирования.

Читать »

Псевдокод

Добавлено Дата: 19 January, 2012 категория: Java, Структуры данных и алгоритмы

Зачастую программистам требуется создать описание алгоритма, предназначаемое только для человека. Подобные описания не являются программами, но вместе с тем они более структурированы, чем обычный текст. В частности, «высокоуровневые» описания сочетают естественный язык и распространенные структуры языка программирования, что делает их доступными и вместе с тем информативными. Такие описания способствуют проведению высокоуровневого анализа структуры данных или алгоритма. Подобные описания принято называть псевдокодом.

Читать »

Анализ средних и худших показателей

Добавлено Дата: 19 January, 2012 категория: Java, Структуры данных и алгоритмы

На примере метода аггауМах можно убедиться, что при определенном типе исходных данных алгоритм выполняется быстрее, чем при других. В данном случае можно попытаться выразить время выполнения алгоритма как среднее, взятое на основе результатов, полученных при всех возможных исходных данных. К сожалению, проведение анализа с точки зрения средних показателей является весьма проблематичным, так как в этом случае требуется определить вероятностное распределение входящего потока. На рис. 3.3 схематично представлена зависимость времени выполнения алгоритма от распределения входного потока данных. Например, если исходные данные только типа «А» или «D».

Читать »

Квадратичная функция времени выполнения алгоритма

Добавлено Дата: 16 January, 2012 категория: Java, Структуры данных и алгоритмы

Решение указанной задачи представлено во фрагменте кода 4.16.

Алгоритм computeSpansl (Р):

Input: массив чисел Л содержащий п элементов.

Output: массив чисел S, содержащий п элементов, причем S[i] является максимальным целым значением к, где к< /+1, а Р [j ] < Р [/ ], при j = / — к + 1,…, /.

Читать »

Алгоритмы шаблонного сопоставления – Силовое решение

Добавлено Дата: 10 January, 2012 категория: Java, Структуры данных и алгоритмы

Проектная модель алгоритма силового решения (brute force) представляет собой технологическое средство создания алгоритмов, когда имеется нечто, что требуется найти, или при необходимости оптимизировать нег которую функцию. Применение такой методики в обычных ситуациях сводится к перебору возможных конфигураций исходных данных и выбора наилучшего варианта.

Читать »

Что такое время выполнения алгоритма?

Добавлено Дата: 8 January, 2012 категория: Java, Структуры данных и алгоритмы

Время выполнения алгоритма или операции над структурой данных зависит, как правило, от целого ряда факторов, вследствие чего* возникает вопрос — как следует проводить его измерение. При реализации алгоритма можно определить затраты времени, регистрируя действительное время, затраченное на выполнение алгоритма в каждом отдельном случае запуска с различными исходными данными. Подобные измерения должны проводиться с достаточной точностью с помощью системных вызовов, встроенных в язык или операционную систему, для которой написан данный алгоритм (например, метод System.currentTimeMillis() или вызовом исполняющей среды с возможностью профилирования). В общем, требуется определить, каким образом время выполнения программы зависит от количества исходных данных. Для решения этой задачи можно провести ряд экспериментов, в которых будет использовано различное количество исходных данных. Далее полученные результаты наглядно представляются с помощью графика, где каждый случай выполнения алгоритма обозначается с помощью точки, координата х которой равна размеру исходных данных п, а координата у — времени выполнения алгоритма t (см. рис. 3.1). Чтобы сделать определенные выводы на основе полученных экспериментов, необходимо использовать качественные образцы исходных данных и провести достаточно большое число экспериментов — что позволит определить некоторые статистические характеристики в отношении времени выполнения алгоритма.

Читать »

Сортировка методом слияния и рекуррентные соотношения

Добавлено Дата: 3 January, 2012 категория: Java, Структуры данных и алгоритмы

Существует еще один способ обоснования утверждения 10.3, гласящего, что время выполнения алгоритма сортировки равно О(п log п), в основу которого положена рекурсивная природа алгоритма сортировки методом слияния. В этом разделе содержится именно такой анализ алгоритма сортировки, и по этой причине представляется математическая концепция рекуррентных отношений (recurrence relation).

Читать »

Алгоритмы шаблонного сопоставления Алгоритм Бойера-Мура

Добавлено Дата: 3 January, 2012 категория: Java, Структуры данных и алгоритмы

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

Читать »

Простейшие операции

Добавлено Дата: 31 December, 2011 категория: Java, Структуры данных и алгоритмы

После изложения разработанного высокоуровневого способа описания алгоритмов приступим к рассмотрению различных способов анализа алгоритмов.

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

Читать »

Асимптотическая нотация

Добавлено Дата: 31 December, 2011 категория: Java, Структуры данных и алгоритмы

Очевидно, что анализ времени выполнения такого простого алгоритма, как аггауМах, проведен слишком глубоко. В ходе анализа возникает несколько вопросов:

•    Действительно ли необходим такой уровень детализации?

•          Действительно ли так важно установить точное число простейших операций, выполняемых алгоритмом?

Читать »

Требования к методологии общего анализа

Добавлено Дата: 30 December, 2011 категория: Java, Структуры данных и алгоритмы

Экспериментальные исследования, безусловно, очень полезны, однако при их проведении существуют три основных ограничения:

•          эксперименты могут проводиться лишь с использованием ограниченного набора исходных данных; результаты, полученные с использованием другого набора, не учитываются;

Читать »

Сортировка слиянием

Добавлено Дата: 16 December, 2011 категория: Java, Структуры данных и алгоритмы

Читатель уже убедился, насколько удобно при описании алгоритмов пользоваться возможностями рекурсии (например, методики проходов дерева, представленные в главе 6). В этом разделе представляется методика сортировки под названием сортировка методом слияния, которая легко описывается с помощью рекурсии. Этот алгоритм тоже создан на основе проектной алгоритмической модели, названной «разделяй и властвуй», одновременно удобной и универсальной.

Читать »