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

Организация алгоритма поиска в Visual C# (Sharp)

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

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

Читать »

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

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

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

Читать »

ШИФРОВАНИЕ ДАННЫХ СУБД

Добавлено Дата: 24 July, 2012 категория: SQL, Базы данных

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

Читать »

Объединяем все вместе

Добавлено Дата: 8 May, 2012 категория: Ядро Linux

Вернемся снова  к  подсчету   количества людей  в  комнате.  Допустим,  что  можно считать  по  одному  человеку за  секунду.   Следовательно, если  в  комнате  находится  7 человек, то подсчет  займет  7 секунд.   Очевидно, что  если  будет n человек, то подсчет всех  займет   n  секунд.   Поэтому можно сказать, что  этот  алгоритм масштабируется, как  О(n) . Что  если  задача  будет  состоять в  том, чтобы  станцевать перед  всеми, кто находится в комнате? Поскольку, независимо от того, сколько человек будет в комнате, это  займет  одно  и то же время, значит, этот  алгоритм масштабируется,  как  O(1) . В табл.  В.1  показаны другие  часто  встречающиеся характеристики сложности.

Читать »

Исследование и тестирование системы

Добавлено Дата: 13 April, 2012 категория: Ядро Linux

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

Читать »

Множество О

Добавлено Дата: 10 April, 2012 категория: Ядро Linux

Полезным обозначением асимптотического поведения функции является верхняя граница — функция, значения которой всегда больше значений изучаемой функции. Говорят, что  верхняя граница некоторой функции растет быстрее, чем рассматриваемая функция. Специальное обозначение "большого-О" используется для описания этого  роста.  Это  записывается как  f (х)  

Читать »

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

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

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

Читать »

Алгоритм кодирования Хаффмана

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

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

Читать »

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

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

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

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

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

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

Читать »

Использование нотации большого О

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

Считается дурным тоном говорить, что «/(я) < 0(g (я))», так как определение нотации большого О уже содержит «меньше или равно». В то же время, несмотря на распространенное употребление, не вполне корректно записать «/(я) = 0(g(n))» (в обычном понимании отношений, обозначенных символом «=»), и совершенно не верно, что «/(я) > 0(g(n))», или «/(Л) > 0(g(n))». Оптимальным выходом будет определение «/(я) есть 0(g(n))». Либо, используя математические символы, данное отношение можно выразить следующим образом:

Читать »

Бинарные деревья

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

Одним из видов деревьев, представляющих особый интерес, является бинарное дерево. Как установлено в п. 6.1.1, правильным бинарным деревом является упорядоченное дерево, в котором каждый составной узел имеет два дочерних элемента. Более того, там же специально оговорено, что бинарные деревья считаются правильными, если только’обратное не будет отмечено специально. Заметим, что это условие никоим образом не нарушает целостности понятия, следовательно, любое неправильное бинарное дерево может быть легко преобразовано в правильное, в чем можно убедиться, выполнив упражнение М-6.3. И даже, отказавшись от этого условия, можно считать неправильное бинарное дерево правильным, рассматривая недостающие простые узлы как «нулевые узлы» или установив заглушки, выступающие в роли узлов.

Читать »

Перехват исключений Java

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

После того как метод генерирует исключение, оно перехватывается, иначе выполнение программы прекращается. Метод, в котором возникла исключительная ситуация, может передать ее другому методу или перехватить ее сам. После перехвата такой ситуации проводится ее анализ и обработка. Общая методология обработки исключений состоит в том, что программа «пытается» выполнить некий фрагмент кода, который может порождать исключения. Если исключение действительно появляется, выполняется его перехват, то есть алгоритм выполнения переходит к заранее описанному блоку catch. После этого в блоке перехвата происходит обработка обстоятельств возникновения исключительной ситуации.

Читать »

Операторы if и switch

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

Алгоритмы управления в Java аналогичны соответствующим алгоритмам другкх развитых языков. В данном разделе подробнее рассмотрим основную структуру и синтаксис алгоритма управления, в том числе возвращаемые методом значения, операторы условия, операторы варианта, циклы и частные формы «переходов»* (операторы break и continue).

Читать »

Сортировка с помощью очереди с приоритетами

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

Другим не менее важным применением очереди с приоритетами является сортировка, когда п элементов из множества S могут сравниваться в соответствии с отношениями упорядочения, и требуется реорганизовать их в порядке возрастания (или, по крайней мере, в порядке неубывания). Алгоритм сортировки So помощью приоритетной очереди Q доста- 1 точно прост и состоит из двух шагов:

Читать »

Применение динамического программирования для поиска наиболее длинной общей подпоследовательности

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

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

Напомним, что для решения поставленной задачи имеются две строки X и У длиной пит каждая, и требуется определить самую длинную строку S, которая будет подпоследовательностью обеих строк одновременно. Так как Хи У состоят из символов, имеется естественное множество индексов, с помощью которых можно определить подзадачи — индексы в строке Хи в строке К

Читать »