Обработка строк

Поиск

Сортировка

Важные типы задач

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

В этом разделе кратко рассматриваются наиболее важные типы задач:

ü сортировка;

ü поиск;

ü обработка строк;

ü задачи из теории графов;

ü комбинаторные задачи;

ü геометрические задачи;

ü численные задачи.

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

Задача поиска связана с нахождением заданного значения, называемого клю­чом поиска (search key), среди заданного множества. Существует огромное количество алгоритмов поиска, так что есть из чего выби­рать. Их сложность варьируется от самых простых алгоритмов поиска методом последовательного сравнения, до чрезвычайно эффективных, но ограниченных алгоритмов бинарного поиска, а также алгоритмов, основанных на представлении базового множества в иной, более подходящей для выполнения поиска форме. По­следние из упомянутых здесь алгоритмов имеют особое практическое значение, поскольку применяются в реально действующих приложениях, выполняющих вы­борку и хранение массивов информации в огромных базах данных.

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

В связи с быстрым увеличением в последнее время количества приложений, связанных с обработкой нечисловых данных, интерес ученых и специалистов-практиков все больше привлекают алгоритмы обработки строк. Строкой (string) называется последовательность символов, взятых из заранее определенного алфа­вита. Практический интерес представляют, например, текстовые строки, состоя­щие из букв, цифр и специальных символов; битовые строки, состоящие из нулей и единиц; последовательности генов, которые могут быть смоделированы с по­мощью строк символов, взятых из четырехсимвольного алфавита {А, С, G, Т}. Тем не менее стоит отметить, что алгоритмы обработки строк стали важны для вычислительной техники очень давно — с тех пор, как появились первые языки программирования и соответствующие им программы — компиляторы.

Существует одна специфическая задача, которая привлекла особое внимание специалистов по информатике. Речь идет о поиске заданного слова в строке текста. Ее назвали поиском подстрок (string matching). Для выполнения такого специ­фического поиска разработано несколько алгоритмов.

Дата добавления: 2017-01-13