Добавлен: 17.06.2023
Просмотров: 197
Скачиваний: 5
С поиском человечество сталкивается каждый день. Например, ученики на занятиях немецкого языка, постоянно сталкиваются с тем, что обращаются к словарю, для того, чтобы найти перевод того или иного слова. Этот случай является ярким примером динамического поиска информации, так как слова в словаре не могут изменить своего положения и всегда остаются на своих местах. В качестве примера динамического поиска можно привести такой случай: при работе с новой поступающей корреспонденцией, работники почтового отделения, постоянно сортируют письма по получателям, а потом ищут этих людей, в некоем городе, для того чтобы получатель получил свое сообщение.
В следующих главах курсовой работ, будет уделено особое внимание популярным алгоритмам поиска данных.
3.1. Алгоритм линейного поиска
Данный алгоритм поиска данных считается наиболее простым алгоритмом, так как он очень прост и удобен в реализации. Этот алгоритм выполняет свою работу следующим образом: он производит проход по массиву от начала и до конца. Если, искомое значение было найдено, то алгоритм заканчивает успешно свою работу, но, если искомого значения не оказалось в массиве, то алгоритм заканчивает свою работу неудачей.
Как простейший алгоритм поиска, этот алгоритм эффективно работает только в массивах, которые содержат лишь малое количество элементов. Но преимущество данного алгоритма следующее – при своей работе он не требует выделения дополнительной памяти.
Как уже было сказано, работа линейного поиска оканчивается только с двумя значениями – «успех» и «неудача».
На рисунке 21 показана блок схема алгоритма линейного поиска
Рис.21. Блок схема алгоритма линейного поиска
Также, для лучшего понятию материала необходимо рассмотреть листинг программы алгоритма линейного поиска:
Рис. 22. Листинг программы
Рассматриваемый алгоритм сортировки имеет сложность O(N), что характеризует его как простейший алгоритм.
3.2. Поиск делением пополам
Поиск делением пополам наиболее усовершенствованный, чем линейный поиск и выполняет свою работу следующим образом: он разбивает массив, в котором произойдет поиска, на две части, и производит поиск искомого элемента в каждой из них. [16]
Как и линейный поиск, поиск делением пополам заканчивает свою работу только в двух случаях, если поиск закончился «удачей», либо «неудачей».
Для того, чтобы понять то, как именно работает данный алгоритм поиска данных, необходимо рассмотреть следующую блок схему:
Рис. 23. Блок схема алгоритма поиска делением пополам
По данной блок схеме видно, что работа алгоритма происходит только в уже упорядоченном массиве, и в данном массиве используется условие First < Last. Для того, чтобы найти искомое значение, алгоритм делит массив на две части. В том случае, если индекс Pos окажется равным первому элементу, то переменная отобразит ложное значение, и, следовательно, искомого значения не окажется в массиве. Ну, а если индекс Pos окажется равным (или меньше) последнего значения, то поиска делением пополам закончится «успешно».[3]
На рисунке 24 рассмотрим листинг программы алгоритм поиска делением пополам:
Рис. 24. Листинг программы
Рассматриваемый алгоритм поиска делением пополам очень быстр в своей работе, но имеет также недостаток – он работает, как уже было сказано только в упорядоченном массиве.
3.3. Прямой поиск строки
Еще один алгоритм поиска данных – это алгоритм прямого поиска строки. Алгоритм прямого поиска строки работает таким образом: поэтапно сравнивает первый символ искомого слова с первым и последующими символами слов, которые имеются в изучаемом тексте. В случае, если при сравнении первого символа искомого слова со вторым символом слова в тексте, совпадение не было зарегистрировано программой, то в этой ситуации, она производит сдвиг слова в тексте, и начинает сравнивать искомое слово со вторым словом в тексте. И это сравнение происходит до тех пор, пока совпадение не будет равно 100%, то есть слово будет найдено, либо поиск окончиться неудачей, то есть слово не найдено в искомом тексте.[10]
На рисунке 25 можно увидеть, как именно производит свою работу алгоритм прямого поиска строки:
Рис. 25. Поиск прямой строки
На рисунке видно, то происходит поиск слова «abaa» в тексте Т, и для того, чтобы программа зафиксировала совпадение, алгоритму необходимо было три раза произвести сдвиг слова.
Рис. 26. Листинг алгоритма поиска прямой строки
Чем меньше алгоритму необходимо будет производить сдвиг слова, тем быстрее будет работать сам алгоритм.
3.4 Алгоритм Кнута, Мориса, Пратта
Рассматриваемый алгоритм поиска данных был разработан в 1970 году группой ученых Дональдом Кнутом, Морисом Д. и Пратт В. Второе название этого алгоритма КМП-алгоритм. Этот алгоритм работает следующим образом: алгоритм производит сравнение основной части искомого слова со словами в тексте, и при фиксировании совпадения нескольких символов, программа самостоятельно выполнит все необходимые сдвиги в тексте и сама найдет все оставшиеся символы в тексте. Следовательно, слово будет найдено, но если совпадений не будет обнаружено, то, значит, искомого слова в тексте не имеется.
Данный алгоритм работает лучше, чем прямой поиск строки, так как сдвиг в таком алгоритме происходит не на один символ, а сразу не насколько, следовательно, время работы алгоритма также уменьшается, то есть он работает очень быстро.[21]
На рисунке 27 показан пример работы КМП-алгоритма:
Рис.27. КМП-алгоритм
Также, для лучшего понятия КМП-алгоритма необходимо рассмотреть листинг алгоритма:
Рис. 28. Листинг алгоритма Кнута, Мориса, Пратта
Также, один существенный плюс данного алгоритма таков, что работа алгоритма будет успешна даже в том случае, если перед несовпадением символов текста, будет зафиксировано несколько совпадений. То есть, в случае, если в тексте будет некоторая орфографическая ошибка, искомое слово все равно было найдено.
3.5 Алгоритм Боуера-Мура
Алгоритм Боуера-Мура был разработан в 1975 году, в качестве улучшенного варианта КМП-алгоритма.
Представим, как работает алгоритм. В рассматриваемом алгоритме поиск происходит с конца слова. Для этого образно разобьем слово на составляющие. Допустим, что z из алфавита величина Rz – это расстояние от самого правого в слове вхождения z до правого конца слова. При прохождении текста алгоритм зафиксировал расхождение между искомым словом и текстом, которое равно z. И в данном случае, для того, чтобы символ искомого слова совпал с символом z в исследуемом тексте, алгоритм производит сдвиг символа до тех пор, пока они не совпадут.
Для того, чтобы лучше понять как именно работает данный алгоритм необходимо рассмотреть следующий рисунок:
Рис. 29. Алгоритм Боуера-Мура
Преимущество данного алгоритма заключается в том, что он эффективен даже в таких текстах, которые не были подвергнуты предварительной сортировке.
На рисунке 30 показан листинг программы алгоритма Боуера-Мура:
Рис. 30. Листинг алгоритма Боуера-Мура
Данная глава курсовой работы была посвящена алгоритмам поиска данных. Все они работают по-разному, но нацелены на нахождение искомого элемента в некотором массиве. Для того чтобы, понять какой из рассмотренных алгоритмов лучший необходимо рассмотреть следующую таблицу:
Следовательно, выбор остается только за пользователем, так как выбор алгоритмов у него очень обширен.
Заключение
Итак, мир информационных технологий не стоит на месте, а находится в постоянном развитии. Основная задача информационных технологий – как можно более эффективно и быстро работать с огромным количеством информации. Но для того чтобы с ней эффективно работать, информацию необходимо структурировать, то есть сортировать. В данной курсовой работе было рассмотрено понятие «сортировки данных», а также изучены наиболее популярные алгоритмы сортировки данных. Сортировка данных отвечает за удобное распределение данных в неком массиве или файле, для того, чтобы в конечном итоге, обеспечить быстрый поиск данных. Также в данной курсовой работе особое внимание было уделено алгоритмам поиска данных, которые также отвечают за быстрое нахождение пользователями всей интересующей их информации.
В данной курсовой работе все пример алгоритмов были рассмотрены на основе языка программирования Паскаль. Этот язык программирования высокого уровня очень легок в использовании, имеет удобный алфавит, с которым может справиться, любой, даже неопытный пользователь. Следовательно, этот язык очень хорош для обучения молодых начинающих программистов. Этот язык программирования был рассмотрен в первой главе курсовой работы, были изучены его преимущества, алфавит, зарезервированные слова, знаки пунктуации и многое другое. Также, в первой главе курсовой работы было уделено внимание термину «Алгоритмы», рассмотрены способы их представления, уделено внимание сложности работы алгоритма.
Во второй главе данной курсовой работы особое внимание было уделено алгоритмам сортировки – внутренней и внешней. Как было выяснено алгоритмов сортировок очень много, и перед каждым пользователь предоставлен широкий их выбор. В данной курсовой работе внимание было уделено таким алгоритмам внутренней сортировки, как сортировка обменом, выбором, методом Шелла, Хоара, вставкой. Все эти алгоритма работают по-разному, какие-то быстрее, какие-то медленнее, например, алгоритм сортировки обменом, работает очень медленно, но при своей работе он не требует выделения дополнительной памяти ЭВМ. Сортировка выбором и включением, работают быстро, но только в массивах с малым количеством элементов. На смену этим простым методам пришли более усовершенствованные алгоритмы сортировок, такие как сортировки методом Шелла и Хоара. Сортировка методом Шелла очень сложна в использовании, но очень эффективна. Скорость работы данного алгоритма, также мала. Наиболее оптимальным алгоритмом, на сегодняшний день, является сортировка методом Хоара, которая и работает очень быстро, легка в использовании.
Также, были рассмотрены алгоритмы внешней сортировки, такие как сортировка простым и естественным слиянием. Алгоритм сортировки простым слиянием очень прост в использовании, но для своей работы требует выделения дополнительной памяти. Ему на смену пришел более усовершенствованный алгоритм естественным слиянием, который работает очень быстро.
Алгоритмов поиска данных, также как и сортировок существует очень много. В данной курсовой работе были рассмотрены следующие алгоритмы: линейный поиска, поиск делением пополам, прямой поиск строки, КМП-алгоритм, алгоритм Боуера-Мура. Линейный поиск – это простейший алгоритм поиска данных, и работает он очень медленно. Ему на смену пришел алгоритм поиска делением пополам, который работает очень быстро, но только в упорядоченном массиве. Для того, чтобы решить все эти недочеты первых двух алгоритмов были разработаны КМП-алгоритм, Алгоритма Боуера-Мура, прямой поиск строки, которые работают очень эффективно.
Итак, по проделанной работе можно сделать следующий вывод – алгоритмов сортировки и поиска существует огромное количество, и все они работают по-разному. Сказать, какой алгоритм самый лучший невозможно, так как работа алгоритма зависит от тех условий, которые задает сам пользователь, и только он сам может сделать выбор в пользу того, или иного алгоритма.