Алгоритмизация, алгоритмы, языки и программы. Алгоритмизация и программирование Примеры алгоритмов программирование

Часто появляются статьи вида «нужны ли программисту алгоритмы», и все они имеют примерно одинаковый шаблон. Автор статьи как правило пишет: «Я N лет пишу сайты/скрипты в 1С, и никогда не пользовался алгоритмами или структурами данных. Тут же приводятся в пример красно-чёрные деревья или какие-нибудь другие экзотические структуры, которые в области, в которой работает автор не часто увидишь, если увидишь вообще. Такие статьи сводятся к тому, что в конкретной области программисты не используют сложные структуры данных и не решают NP задач.

Сама постановка такого вопроса в корне не верна. Количество специальностей в индустрии растёт постоянно, и человек, который пишет сайты на.net будет заниматься совсем другими вещами, нежели человек, пишущий драйвера для сенсоров на ARM архитектуре под экзотической ОС. Давайте прежде всего определим, что же такое алгоритм. Неформально Кормен определяет алгоритм как строго определённую процедуру, которая принимает одно или несколько значений как ввод, и возвращает одно или несколько значений как результат. Формально алгоритм определяется в разных моделях вычислений: операции, которые можно выполнить на машине Тьюринга или с помощью лямбда-исчислений. Таким образом фактически любой код, который что-то делает, является алгоритмом. Получается, что вопрос «нужны ли программисту алгоритмы» можно перевести как «нужно ли программисту уметь писать код». Правильно такой вопрос должен звучать что-то вроде: «нужно ли программисту в отрасли Х знать продвинутые алгоритмы и детали теории вычислений».

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

Давайте подумаем, что же нужно учить программисту в университете, для того чтобы приобрести необходимые навыки для успешной карьеры. Библиотеки? Фреймворки? Они устаревают, интерфейсы к ним меняются, все они написаны чаще всего под один язык, который студенты могут и не использовать никогда в индустрии. Всех учить писать сайты? Или всех учить писать ОС? Образование должно охватывать как можно большую аудиторию и давать максимально возможный набор навыков. Программист в первую очередь должен уметь анализировать и решать проблемы – это основной навык, которым должны обзавестись выпускники факультетов информатики. Написание кода – это просто необходимый инструмент, который используется для решения задач. Кто может знать какие навыки вам понадобятся в будущем? Таким образом учить теорию – это наиболее оптимально с точки зрения образования. Полученные навыки можно применить в любой области, а выучить библиотеку или фреймворк имея хорошую базу знаний не составит большого труда. Парадоксально то, что люди задающие вопросы про нужность алгоритмов, как правило имеют какие-то знания в этой области. Я не помню ни одного человека, который не имел знаний в области теории вычислений, и с гордостью кричал об этом, утверждая, что ему они не нужны.

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

Знания теории анализа и алгоритмов применяются всеми программистами на самом деле каждый день, просто мы привыкли к этим вещам настолько, что даже не задумываемся над этим. Какую бы задачу вы не решали – будь то простой сайт с выборкой данных из БД, или баш скрипт на сервере, вы будете использовать какие-то структуры данных. Как минимум примитивный массив, а скорее всего и что-то посложнее. Языки дают нам множество различных структур, многие из которых взаимозаменяемы. Часто мы имеем несколько вариаций одного абстрактного типа с разными реализациями. Например, в С++ есть структуры данных vector и list. Чем они отличаются, и какие будут преимущества и недостатки использования одного или другого? Как в С++ реализована map, и чем она отличается от multimap? Как реализован list в Python – через массив или связным списком и как лучше всего с ним работать? Почему в C# нежелательно использовать ArrayList, а вместо него использовать List? Как реализован SortedDictionary и как он повлияет на исполнение программы если будет использован вместо Dictionary? Как работает continuation, когда её нужно использовать, и будут ли какие-то побочные эффекты при её использовании? Когда вы в последний раз использовали каррированные функции, которые есть почти в каждом языке? Если вы думаете, что map в С++ реализована как хэш-таблица, вы ошибаетесь. Она реализована на красно-чёрных деревьях, а хэш-таблицей реализована unordered_map. Отдельно стоит упомянуть динамическое программирование. Понимание что это такое, как можно оптимально переписать рекурсивные функции и что такое мемоизация, часто поможет избежать выстрела себе в ногу. Таким образом просто чтобы полноценно и эффективно использовать язык, на котором вы пишите, уже нужно иметь хотя бы поверхностные знания о структурах данных, что они из себя представляют, и как могут повлиять на исполнение вашей программы.

А как же библиотеки? Ведь они решают столько задач! Чтобы рационально использовать библиотеки, их тоже нужно понимать. Во-первых, функции в библиотеки могут иметь побочные эффекты или поведение, которые вы не будете знать без понимания алгоритмов. Получив баг в таком случае можно долго и упорно пытаться его поймать и решить, когда можно было избежать. Во-вторых, различные инструменты и библиотеки часто нужно «настраивать» - говорить им какие алгоритмы, структуры данных и технологии использовать внутри. Без элементарных знаний вам придётся либо идти читать маны, либо выбирать наугад. В-третьих – есть множество задач, которые нельзя решить простым вызовом API библиотеки или фреймворка. Что вы будете делать в таком случае? Тратить часы на поиски возможных решений и просить помощи у друга? В-четвёртых – множество задач решается очень просто несколькими строчками кода или встроенными средствами языка. Если для решения каждого чиха вы будете тянуть библиотеку, то ваши программы будут гигантскими монстрами, занимая по сотни мегабайт и больше на диске, отжирая всю память на сервере, и при том имея довольно скудный функционал. Кроме того, наличие кучи подключенных библиотек влечёт за собой проблемы совместимости, и программа может падать случайным образом из-за странного поведения нескольких библиотек в одном проекте. Бездумное использование библиотек может привести к довольно плачевным последствиям, и разработчики, которые умеют только использовать библиотеки, но не способны решить даже простую проблему самостоятельно, никогда не будут ценится, потому что их решения будут неконкурентоспособны.

Со мной работал один программист со стажем больше десяти лет. Однажды нам понадобилась функция, которую использованная нами библиотека на тот момент не поддерживала: примитивный text-wrap в одном из визуальных компонентов. Этот «программист» посмотрел, что стандартными средствами это сделать нельзя, и сразу заявил, что реализация такой функции невозможна. Задачу решил интерн-третьекурсник с аналитическим мозгом, который за два часа написал простой алгоритм и внедрил его в нужный компонент. Другой проект в виде сайта на.net мне достался по наследству. Главная страничка представляла собой несколько маленьких графиков, и загружалась почти 10 секунд. Оказалось, что человек, который изначально делал этот проект, нагородил кучу ужасных конструкций из тройных вложенных циклов, которые долго и печально забирали данные из БД, и потом привязывали их к графикам. После небольшого рефакторинга страница стала грузится почти мгновенно.

Может ли программист обойтись без знаний алгоритмов и теории анализа? Может, и таких «программистов» очень много. Только назвать их программистами можно разве что с большой натяжкой. Ко мне на собеседование приходит очень много программистов, со стажем десять-пятнадцать лет, и толком не понимающих что же они делают и почему. У них своя ниша, они ходят от компании к компании, не задерживаясь в них больше года. Как правило, у них есть небольшой набор задач, которые они могут решать, и если сделать шаг в сторону, то человек теряется и ему нужно обучить себя новым навыкам. Таких людей приглашают на проект, и от них избавляются как можно быстрее, потому что они теряют кучу времени, изобретая велосипеды и читая маны чтобы узнать то, что уже должны были знать из университета. У них как правило нет особо никакой карьеры и нестабильный заработок.

В итоге, для чего нужно знать алгоритмы и теорию анализа, если можно выполнять работу и без этих знаний? Чтобы быть квалифицированным специалистом в своей профессии, иметь карьерный рост и уважение коллег. Чтобы эффективно решать поставленные задачи и не изобретать велосипедов. Чтобы не писать монстров с огромным количеством сторонних библиотек, которые занимают сотни мегабайт на диске от отжирают кучу памяти на сервере и регулярно падают по случайной причине в зависимости от фазы луны. Чтобы эффективно и с максимальными возможностями использовать язык, на которым вы пишете. Чтобы принимать информированные и осмысленные решения по выбору библиотеки и технологии для решения проблемы. Если же ваша работа заключается в написание SQL запроса и вбивание команды в консоль, то хочу вас огорчить: вы не программист, вы – пользователь, вам действительно не нужны алгоритмы и иже с ним, и вы зря потратили время в университете потому что для такой работы достаточно закончить курсы или прочитать пару вводных книжек самостоятельно.

Аннотация: Предмет науки программирования. Пример и свойства алгоритма. Парадигмы программирования (директивное, объектно-ориентированное и функционально-логическое программирование).

Эта глава, с которой начинается изучение курса, служит двум основным целям:

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

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

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

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

Предмет науки программирования

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

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

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

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

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

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

Пример и свойства алгоритма

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

Задача 1.1 . Придумайте алгоритм, вводящий натуральное число, большее единицы,который находит наименьший простой делитель этого числа.

Алгоритм решения задачи .

Алгоритм П :

П1 : Положить целое число равным двум и перейти на шаг П2.

П2 : Если делится нацело на , то завершить работу алгоритма, выдав в качестве результата ; иначе перейти на шаг П3.

П3 : Увеличить значение на единицу и перейти на шаг П2.

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

k = 3 k = 4 k = 2
П1: i = 2 П1: i = 2 П1: i = 2
П2: i = 2 П2: i = 2 П2: i = 2
П3: i = 3
П2: i = 3

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

Основные свойства любого алгоритма - это конечность, определенность, вход (ввод), выход (вывод) и эффективность. Рассмотрим их последовательно более подробно.

Конечность . Алгоритм должен всегда заканчиваться после выполнения конечного числа шагов. Алгоритм П удовлетворяет этому условию, так как величина вначале меньше , ее значение увеличивается на единицу к каждому очередному выполнению шага П2, и поэтому выполнение алгоритма будет прекращено на шаге П2 при , если - простое число, или ранее при составном .

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

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

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

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

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

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

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


Алгоритм Кнута-Морриса-Пратта

Алгоритм Кнута-Морриса-Пратта (КМП) получает на вход слово X=xx... x[n] и просматривает его слева направо буква за буквой, заполняя при этом массив натуральных чисел l... l[n], где l[i]=длина слова l(x...х[i]) (функция l определена в предыдущем пункте). Словами: l[i] есть длина наибольшего начала слова x...x[i], одновременно являющегося его концом.

Какое отношение все это имеет к поиску подслова?

Другими словами, как использовать алгоритм КМП для определения того, является ли слово A подсловом слова B?

Решение. Применим алгоритм КМП к слову A#B, где # - специальная буква, не встречающаяся ни в A, ни в B. Слово A является подсловом слова B тогда и только тогда, когда среди чисел в массиве l будет число, равное длине слова A.

Описать алгоритм заполнения таблицы l...l[n].

Решение. Предположим, что первые i значений l...l[i] уже найдены. Мы читаем очередную букву слова (т.е. x) и должны вычислить l.

Другими словами, нас интересуют начала Z слова x...x . Слово Z" является началом и концом слова x...x[i]. Однако не любое слово, являющееся началом и концом слова x...x[i], годится - надо, чтобы за ним следовала буква x.

Получаем такой рецепт отыскания слова Z. Рассмотрим все начала слова x...x[i], являющиеся одновременно его концами. Из них выберем подходящие - те, за которыми идет буква x. Из подходящих выберем самое длинное. Приписав в его конец х, получим искомое слово Z. Теперь пора воспользоваться сделанными нами приготовлениями и вспомнить, что все слова, являющиеся одновременно началами и концами данного слова, можно получить повторными применениями к нему функции l из предыдущего раздела.

Вот что получается:

{таблица l..l[i] заполнена правильно}

while i <> n do begin

{len - длина начала слова x..x[i], которое является

его концом; все более длинные начала оказались

неподходящими}

while (x<>х) and (len>0) do begin

if x=x do begin

{х..x - самое длинное подходящее начало}

{подходящих нет}

Доказать, что число действий в приведенном только что алгоритме не превосходит Cn для некоторой константы C.

Решение. Это не вполне очевидно: обработка каждой очередной буквы может потребовать многих итераций во внутреннем цикле. Однако каждая такая итерация уменьшает len по крайней мере на 1, и в этом случае l окажется заметно меньше l[i]. С другой стороны, при увеличении i на единицу величина l[i] может возрасти не более чем на 1, так что часто и сильно убывать она не может - иначе убывание не будет скомпенсировано возрастанием.

Более точно, можно записать неравенство

l

(число итераций на i-м шаге)<= l[i]-l+1

Остается сложить эти неравенства по всем i и получить оценку сверху для общего числа итераций.

Будем использовать этот алгоритм, чтобы выяснить, является ли слово X длины n подсловом слова Y длины m. (Как это делать с помощью специального разделителя #, описано выше.) При этом число действий будет не более C(n+m}, и используемая память тоже. Придумать, как обойтись памятью не более Cn (что может быть существенно меньше, если искомый образец короткий, а слово, в котором его ищут - длинное).

Решение. Применяем алгоритм КМП к слову А#В. При этом: вычисление значений l,...,l [n] проводим для слова X длины n и запоминаем эти значения. Дальше мы помним только значение l[i] для текущего i - кроме него и кроме таблицы

l...l[n], нам для вычислений ничего не нужно.

На практике слова X и Y могут не находиться подряд, поэтому просмотр слова X и затем слова Y удобно оформить в виде разных циклов. Это избавляет также от хлопот с разделителем.

Написать соответствующий алгоритм (проверяющий, является ли слово X=x...x[n] подсловом слова Y=y...y[m]

Решение. Сначала вычисляем таблицу l...l[n]как раньше. Затем пишем такую программу:

{len - длина максимального качала слова X, одновременно

являющегося концом слова y..j[j]}

while (len<>n) and (j<>m) do begin

while (x<>у) and (len>0) do begin

{начало не подходит, применяем к нему функцию l}

{нашли подходящее или убедились в отсутствии}

if x=y do begin

{x..x - самое длинное подходящее начало}

{подходящих нет}

{если len=n, слово X встретилось; иначе мы дошли до конца

слова Y, так и не встретив X}

Алгоритм Бойера - Мура

Этот алгоритм делает то, что на первый взгляд кажется невозможным: в типичной ситуации он читает лишь небольшую часть всех букв слова, в котором ищется заданный образец. Как так может быть? Идея проста. Пусть, например, мы ищем образец abcd. Посмотрим на четвертую букву слова: если, к примеру, это буква e, то нет никакой необходимости читать первые три буквы. (В самом деле, в образце буквы e нет, поэтому он может начаться не раньше пятой буквы.)

Мы приведем самый простой вариант этого алгоритма, который не гарантирует быстрой работы во всех случаях. Пусть x...х[n] - образец, который надо искать. Для каждого символа s найдем самое правое его вхождение в слово X, то есть наибольшее k, при котором х[k]=s. Эти сведения будем хранить в массиве pos[s]; если символ s вовсе не встречается, то нам будет удобно положить pos[s]=0 (мы увидим дальше, почему).

Как заполнить массив pos?

положить все pos[s] равными 0

for i:=1 to n do begin

В процессе поиска мы будем хранить в переменной last номер буквы в слове, против которой стоит последняя буква образца. Вначале last=n (длина образца), затем last постепенно увеличивается.

{все предыдущие положения образца уже проверены}

while last<= m do begin {слово не кончилось}

if x[m]<>y then begin {последние буквы разные}

last:=last+(n-pos]);

{n - pos] - это минимальный сдвиг образца,

при котором напротив y встанет такая же

буква в образце. Если такой буквы нет вообще,

то сдвигаем на всю длину образца}

если нынешнее положение подходит, т.е. если

x[i]..х[n]=y..y,

то сообщить о совпадении;

Знатоки рекомендуют проверку совпадения проводить справа налево, т.е. начиная с последней буквы образца (в которой совпадение заведомо есть). Можно также немного сэкономить, произведя вычитание заранее и храня не pos[s], а n-pos[s],

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

заменить на

last:=last+(n-u),

где u - координата второго справа вхождения буквы x[n] в образец.

Как проще всего учесть это в программе

Решение. При построении таблицы pos написать

написать

last:=last+n-pos];

Приведенный упрощенный вариант алгоритма Бойера-Мура в некоторых случаях требует существенно больше n действий (число действий порядка mn), проигрывая алгоритму Кнута-Морриса-Пратта.

Пример ситуации, в которой образец не входит в слово, но алгоритму требуется порядка mn действий, чтобы это установить.

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

Настоящий (не упрощенный) алгоритм Бойера-Мура гарантирует, что число действий не превосходит C(m+n) в худшем случае. Он использует идеи, близкие к идеям алгоритма Кнута-Морриса-Пратта. Представим себе, что мы сравнивали образец со входным словом, идя справа налево. При этом некоторый кусок Z (являющийся концом образца) совпал, а затем обнаружилось различие: перед Z в образце стоит не то, что во входном слове. Что можно сказать в этот момент о входном слове? В нем обнаружен фрагмент, равный Z, а перед ним стоит не та буква, что в образце. Эта информация может позволить сдвинуть образец на несколько позиций вправо без риска пропустить его вхождение. Эти сдвиги следует вычислить заранее для каждого конца Z нашего образца. Как говорят знатоки, все это (вычисление таблицы сдвигов и ее использование) можно уложить в C(m+ n) действий.

Алгоритм Рабина

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

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

Привести пример удобной для вычисления функции.

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

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

Привести пример семейства удобных функций.

Решение. Выберем некоторое число p (желательно простое, смотри далее) и некоторый вычет x по модулю p. Каждое слово длины n будем рассматривать как последовательность целых чисел (заменив буквы кодами). Эти числа будем рассматривать как коэффициенты многочлена степени n-1 и вычислим значение этого многочлена по модулю p в точке x. Это и будет одна из функций семейства (для каждой пары p и x получается, таким образом, своя функция). Сдвиг окошка на 1 соответствует вычитанию старшего члена (хn-1 следует вычислить заранее), умножению на x и добавлению свободного члена.

Следующее соображение говорит в пользу того, что совпадения не слишком вероятны. Пусть число p фиксировано и к тому же простое, а X и Y - два различных слова длины n. Тогда им соответствуют различные многочлены (мы предполагаем, что коды всех букв различны - это возможно, если p больше числа букв алфавита). Совпадение значений функции означает, что в точке x эти два различных многочлена совпадают, то есть их разность обращается в 0. Разность есть многочлен степени n-1 и имеет не более n-1 корней. Таким образом, если и много меньше p, то случайному x мало шансов попасть в неудачную точку.

Подобные документы

    Теоретические сведения. Основные понятия. Строка, её длина, подстрока. Понятие о сложности алгоритма. Алгоритмы основанные на методе последовательного поиска. Алгоритмы Рабина, Кнута - Морриса - Пратта, Бойера – Мура.

    курсовая работа , добавлен 13.06.2007

    Организация возможности просмотра текстовых файлов и осуществления поиска нужных слов в тексте. Редактирование текста (шрифт, размер). Алгоритм поиска подстроки в строке (метод Кнута-Морриса-Пратта). Загрузка текста из файла (с расширением.txt).

    курсовая работа , добавлен 29.05.2013

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

    презентация , добавлен 19.10.2014

    Исследование понятия алгоритма, особенностей линейных и разветвляющихся алгоритмов. Свойства алгоритма: понятность, точность, дискретность, массовость и результативность. Составление программы для вычисления значения функции и построение её графика.

    контрольная работа , добавлен 25.03.2013

    Изучение определения, описания и вызова функций, указателей и ссылок на них. Написание функции умножения произвольного столбца двумерного массива на const. Умножение 2 столбцов массива на константы. Составление блок-схемы алгоритма и текста программы.

    лабораторная работа , добавлен 09.01.2012

    Основные свойства алгоритма. Формальный и неформальный исполнитель алгоритма, система его команд. Способы записи алгоритма. Словесное описание, построчная запись, опорный конспект. Характеристики алгоритмического языка. Выполнение алгоритма компьютером.

    презентация , добавлен 04.04.2014

    Теоретические и практические аспекты решения прикладных задач с применением функций и процедур структурного (модульного) программирования. Особенности разработки схемы алгоритма и программы для вычисления массива z на языке Turbo Pascal 7.0, их описание.

    курсовая работа , добавлен 11.12.2009

    Характеристика особливостей реалізації пошуку по масиву методами лінійним, бінарним, по "дереву Фібоначе" та екстраполярним на мові програмування Turbo Pascal. Використання алгоритма Рабіна-Карпа та Кнута-Морріса-Пратта для знаходження підрядка в рядку.

    курсовая работа , добавлен 16.09.2010

    Описание принципа работы генетического алгоритма, проверка его работы на функции согласно варианту на основе готовой программы. Основные параметры генетического алгоритма, его структура и содержание. Способы реализации алгоритма и его компонентов.

    лабораторная работа , добавлен 03.12.2014

    Разработка на языке ассемблера алгоритма контроля, на циклический CRC-код, массива данных хранящегося в некоторой области памяти. Сохранение кода для последующей периодической проверки массива данных. Сообщение об искажении данных. Описание алгоритма.

2.4.1. Понятие базовых алгоритмов

2.4.2. Алгоритмы линейной структуры

2.4.3. Базовые алгоритмы разветвляющихся структур и примеры их программирования

2.4.4. Базовые алгоритмы регулярных циклических структур и примеры их программирования

2.4.5. Базовые алгоритмы итеративных циклических структур и примеры их программирования

2.4.6. Базовые алгоритмы обработки одномерных массивов

2.4.7. Базовые алгоритмы обработки двумерных массивов

2.4.8. Контрольные вопросы по теме «Базовые алгоритмы и примеры их реализации»

2.4.9. Тестовые задания по теме «Базовые алгоритмы и примеры их реализации»

2.4.1. Понятие базовых алгоритмов

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

К базовым алгоритмам императивного программирования можно отнести:

    Простейшие алгоритмы, реализующие базовые алгоритмические структуры.

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

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

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

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

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

2.4.2. Алгоритмы линейной структуры

Пример 2.4.2-1.

где x = -1,4; y = 0,8;переменныеkиm– целого типа, остальные переменные - вещественного типа;[n]- целая часть числаn.

Схема алгоритма и программы на языках QBasic, Pascal, C++ , представлены на рис. 2.4.2-1.

Следует обратить внимание на то, что целая переменная k получила округленное значениеn , а целая переменнаяm - усе­ченное с помощью функцииFIX() до целой части значенияn.

Пример 2.4.2-2 . Вычислить и вывести на экран значения следующих величин:

где x = 2.9512; y = 0.098633;переменныеiиj– целого типа; остальные переменные – вещественного типа.

Схема алгоритма и коды программ представлены на рис. 3.2.1-2.

Рис. 2.4.2-2.

Результаты выполнения программы при указанных выше значе­ниях исходных данных имеют следующий вид:

Пример 2.4.2-3. Вычислить и вывести на экран значение первой космической скорости.

Проведем формализацию. Минимальная скорость, при которой космический аппарат в гравитационном поле Земли может стать искусственным спутником, равна

где – гравитационная постоянная; M – масса Земли;
– расстояние от центра Земли до космического аппарата.

Схема алгоритма и коды программ представлены на рис. 3.2.1-3.

Рис. 2.4.2-3.

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