Сортування та пошук даних. Лінійний (послідовний), бінарний (двійковий) метод пошуку. Полегшення подальшого пошуку елементів у множині при обробці даних. Теорія складності обчислень. Використання методів пошуку на практиці. Алгоритм Кнута-Морріса-Пратта.
Аннотация к работе
ЕКОНОМІКО-ПРАВНИЧИЙ КОЛЕДЖ ДЕРЖАВНОГО ВИЩОГО НАВЧАЛЬНОГО ЗАКЛАДУМета - дослідити особливості роботи простих методів пошуку, переваги використання окремих методів на практиці. Завдання: - Проаналізувати ефективність простих методів пошуку.У різних розділах математики та інших наук дані, що мають вигляд інформації, заданої як послідовність рядків і стовпчиків, називають по-різному: матриці - у вищій алгебрі, таблиці - у розрахункових задачах, масиви - у програмуванні. Зазвичай працюють з масивами, які містять числа. Масив є прикладом структурованого типу, тобто він, у свою чергу, складається з елементів іншого типу.Набір даних, в якому проводиться пошук, можна розглядати як структуру, яка містить ключі і дані, і допускає операцію - повернення елемента із заданим ключем. Якщо набір даних під час роботи алгоритму не змінюється - це статичний пошук. Також алгоритми пошуку можна поділити на алгоритми, що використовують невпорядковані набори даних і на алгоритми, що працюють з впорядкованим набором даних. Обчислення елемента, що часто передбачає отримання значення елемента, ключа елемента і т.д. У множині встановлюється барєр, тобто елемент, який задовольняє пошуку.Даний алгоритм є найпростішим алгоритмом пошуку , на відміну, від двійкового пошуку, бо не накладає ніяких обмежень на функцію і має найпростішу реалізацію. Пошук значення функції здійснюється простим порівнянням чергового розглянутого значення (як правило, пошук відбувається зліва направо, тобто від менших значень аргументу до великих) і, якщо значення збігаються (з тією або іншою точністю), то пошук вважається завершеним. У програмуванні лінійний пошук використовується, якщо немає ніякої додаткової інформації про організацію елементів набору даних. Алгоритм полягає в послідовному порівнянні елементів набору даних Масив [i] з шуканим значенням - X.Двійковий (бінарний) пошук (також відомий як метод поділу навпіл) - класичний алгоритм пошуку елемента в відсортованому масиві, який використовує дроблення масиву на половини. Якщо ключ менше значення середини то пошук здійснюється в першій половині елементів, інакше - в другій. Пошук зводиться до того, що знову визначається значення серединного елемента в обраній половині і порівнюється з ключем. Бінарний пошук здійснюється на впорядкованому наборі даних, тобто значення елементів набору даних зростають (зменшуються) зі збільшенням номера елемента. Якщо X = Масив [k], то завдання виконане, X> Масив [k], то це означає, що шуканий елемент розташований нижче Масив [k] (між елементами з номерамиДля проведення порівняльного аналізу простих методів пошуку використовується теорія складності обчислень. Теорія складності обчислень - підрозділ теоретичної інформатики, що займається дослідженням складності алгоритмів, для розвязання задач на основі формально визначених моделей обчислювальних пристроїв. Складність алгоритмів вимірюється за необхідними ресурсами, в основному це тривалість обчислень або необхідний обсяг памяті. Ця теорія виникла з потреби порівнювати швидкодію алгоритмів (наприклад, алгоритмів пошуку і сортування), чітко описувати їх поведінку (час виконання і обсяг необхідної памяті) в залежності від розміру входу. Час виконання алгоритму визначається кількістю тривіальних кроків, необхідних для вирішення проблеми і залежить від розміру вхідних даних Простір алгоритму визначається обємом памяті або місця на носії даних, що використовується алгоритмом.Наприклад, пошук в масивах даних здійснюється за ключем, присвоєним кожному з елементів масиву (в найпростішому випадку сам елемент є ключем). · Метод використовується для знаходження екстремуму цільової функції і в цьому випадку є методом умовної одновимірної оптимізації. Розглянемо прості методи пошуку на задачах: Нехай дано масив елементів Лінійний пошук має на увазі послідовний перегляд всіх елементів масиву А в порядку їх розташування, поки не знайдеться елемент рівний b. if IN then writeln("Елемент,що співпадає з ключем, виявлено.Позиція елемента-",i 1) else writeln("Елемент не виявлено");Слід зазначити, що в загальному випадку при лінійному пошуку серед N елементів потрібно в середньому N / 2 порівнянь в разі успішного пошуку та N порівнянь в найгіршому випадку, і витрати часу для великих масивів тому великі. Знаходження елемента бінарним пошуком здійснюється дуже швидко.Застосування того чи іншого алгоритму пошуку для вирішення конкретної задачі є досить складною проблемою, вирішення якої потребує не лише досконалого володіння саме цим алгоритмом, але й всебічного розглядання того чи іншого алгоритму, тобто визначення усіх його переваг і недоліків. Це пояснює його частіше використання при вирішенні задач пошуку.Функція здійснює пошук першого входження масиву W (розміру m) в масив T, в результаті функція видає номер першого елементу в масиві T починаючи з якого зустрічається масив W. У випадку, якщо масив W не зустрічається в масиві T результат функції рівний-1. Якщо k=0, означає масив W входить в масив T починаючи з номера i 1 і
План
ЗМІСТ
1) РЕФЕРАТ
2) ВСТУП
3) РОЗДІЛ 1. ПОНЯТТЯ АЛГОРИТМУ ПОШУКУ
3.1 Сортування та пошук даних
3.2 Лінійний (послідовний) метод пошуку
3.3 Бінарний (двійковий) метод пошуку
4) РОЗДІЛ 2.ПОРІВНЯЛЬНИЙ АНАЛІЗ
4.1 Теорія складності обчислень
4.2 Використання методів пошуку на практиці
4.3 Результати порівняльного аналізу
5) ВИСНОВКИ
6) ДОДАТКИ
7) СПИСОК ЛІТЕРАТУРИ
РЕФЕРАТ
Обсяг роботи сторінок, таблиця, зображень, джерел, додатка.
Вывод
Застосування того чи іншого алгоритму пошуку для вирішення конкретної задачі є досить складною проблемою, вирішення якої потребує не лише досконалого володіння саме цим алгоритмом, але й всебічного розглядання того чи іншого алгоритму, тобто визначення усіх його переваг і недоліків.
Порівнявши між собою саме бінарний та лінійний методи пошуку, можна визначити , що кожен з методів має свої особливості.
У практичному використанні наведені методи є найпростішими, загальновживаними.
Треба зазначити, що перевірений на практиці бінарний метод пошуку виявився більш швидшим , ефективним та результативним. Це пояснює його частіше використання при вирішенні задач пошуку.
Отже, головна задача, яку має вирішити людина, що розвязує задачі пошуку - це визначення як позитивних, так і негативних характеристик різних алгоритмів пошуку, передбачення кінцевого результату. До того ж, треба враховувати головне - чи можливо взагалі вирішити поставлену задачу за допомогою простих алгоритмів пошуку.
Список литературы
1. «Алгоритмы: введение в разработку и анализ» А.Левитин
2. «Алгоритмы и структуры данных» Н.Вирт (1985)
3. «Основи алгоритмізації та програмування» Співаковський О.В.(1997)
4. «Структуры данных и алгоритмы их обработки на языке программирования Паскаль» Касторнова В.А.