Линейный и интерполяционный поиск
Исследование алгоритмов линейного и интерполяционного поиска, принципов их действия, логики каждого из методов. Анализ формул, примененных в алгоритмах. Описывание эксперимента и сравнительная характеристика интерполяционного и линейного поисков.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | отчет по практике |
| Язык | русский |
| Дата добавления | 15.10.2015 |
| Размер файла | 302,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Федеральное агентство связи
Федеральное государственное образовательное бюджетное учреждение
высшего профессионального образования
«Сибирский государственный университет телекоммуникаций и информатики»
(ФГОБУ ВПО «СибГУТИ»)
ОТЧЕТ
по учебной практике
Выполнил:
студент гр. ИВ-442 /Блинов А.И./
Руководитель практики от университета:
доцент Кафедры ВС/Курносов М.Г./
Новосибирск 2015
Содержание
1. Описание алгоритмов
1.1 Алгоритм линейного поиска (linear_search)
1.2 Алгоритм интерполяционного поиска (interpolating_search)
2. Организация экспериментов
3. Результаты экспериментов
Использованная литература
1. Описание алгоритмов
В данном задании мне требовалось изучить алгоритм интерполяционного поиска, принцып его действия, почему именно такая формула применяется в алгоритме, сравнить работу интерполяционного поиска с линейным поиском.
1.1 Алгоритм линейного поиска (linear_search)
Заключается в пробежке массива и проверкой каждого элемента массива с искомым элементом. Сложность по времени зависит от размера массива, и в худшем случае равна T(n) = O(n).
Псевдокод линейного поиска:
Key - искомый элемент
Array - массив
X - индекс массива
Sizeofarray - размер массива
Function linear_search ( Array[X], Key, Sizeofarray)
For X=0 to Sizeofarray-1 do
If Array[X] == Key
Return X
Else
Return -1;
End for
End function
1.2 Алгоритм интерполяционнго поиска (interpolating_search)
Интерполяция, интерполирование -- в вычислительной математике способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений.
Основан на принципе поиска в телефонной книге или, например, в словаре.
Вместо сравнения каждого элемента с искомым, как при линейном поиске, данный алгоритм производит предсказание местонахождения элемента: интерполирующий поиск производит оценку новой области поиска по расстоянию между ключом и текущим значением элемента. Другими словами, интерполирующий поиск учитывает знак разности между ключом и текущим значением и модуль этой разности и по данному значению производит предсказание позиции следующего элемента для проверки.
В данном задании я применял формулу линейной интерполяции, потому что сам отсортированный массив на графике представляет собой последовательное соединение линейных функций (см. рисунок 1). Например, массив А={1,4,5,8,13}
Рисунок 1
Формула линейной интерполяции:
В математике данная формула позволяет найти значение значение функции f(x) в определённой точке Х, при том что x0 < x < x1 и f(x0) < f(x) < f(x1), если мы знаем f(x0), f(x1), x0 и x1.
Ниже представлен псевдокод интерполяционного поиска.
Key - искомый элемент
Array - массив
Sizeofarray - размер массива
L - левая граница массива (изначально 0)
R - правая граница массива (изначально Sizeofarray - 1)
M - вычисляемая ячейка массива между L и R
Function interpolating_search ( A [Sizeofarray-1], Sizeofarray, Key )
While (( A[L] < Key ) and (A[R] >= Key )) do
M = L + ((Key - A[L] ) * (R - L )) / ( A[R] - A[L] )
if ( A[M] < Key )
L = M + 1
else
if ( A[M] > Key )
R = M - 1
else
return M
End while
if ( A[L] == Key )
Return L
else
Return -1
End function
Логика, лежащая в основе этого метода, проста. Мы знаем, что значения массива не убывают от А[L] (изначально L=0) до А[R] (изначально R=размер_массива - 1), но не знаем, как именно.
Вычисленное по формуле
“M = L + ((Key - A[L] ) * (R - L )) / ( A[R] - A[L] )”
значение индекса -- ожидаемая позиция элемента со значением, равным Key.
После сравнения Key с А[M] алгоритм либо прекращает работу (если они равны), либо продолжает поиск тем же способом среди элементов с индексами либо от L до M-1, либо от M+1 до R , в зависимости от того, меньше ли Key значения А[M] или больше. Таким образом, на каждой итерации размер задачи уменьшается, но, априори, мы не знаем, насколько именно. Поэтому сложность алгоритма, полученная методом неоднократных запусков программы, такова: T(n)=О(log(log(n))).
Простой пример: есть массив Arr[]=”1,2,4,7,11,16,22,28,37,49,52,57,60,62,74,91,93”, (зелёный цвет - это границы поиска, красный цвет - это ключ).
Таблица 1
|
I |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
|
|
Arr[I] |
1 |
2 |
4 |
7 |
11 |
16 |
22 |
28 |
37 |
49 |
52 |
57 |
60 |
62 |
74 |
91 |
93 |
L=0, R=16, Arr[L]=0, Arr[R]=93, key=37 (см. таблицу 1). Действия по коду: алгоритм линейный интерполяционный поиск
Условие цыкла «while»: 0<37 и 93>37 ? - Да. Тогда М=0+((37-1)*(16-0))/(93-1)=6,453…=6 (целочисленный тип данных берёт только целую часть). Arr[6]=22<37. Следовательно, L=M+1.
Таблица 2
|
I |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
|
|
Arr[I] |
1 |
2 |
4 |
7 |
11 |
16 |
22 |
28 |
37 |
49 |
52 |
57 |
60 |
62 |
74 |
91 |
93 |
Теперь L=7, R=16, Arr[L]=28, Arr[R]=93, key=37 (см. таблицу 2). Условие цыкла «while»: 28<37 и 93>37 ? - Да.
M=7+((37-28)*(16-7))/(93-28)=8,24….=8. 37<37 ? - Нет, а 37>37 ? - Нет, следовательно, вернуть значение M. И вправду, Arr[M]=key=37.
2. Организация экспериментов
· Эксперименты проводились на ноутбуке HP Pavilion g6 2137sr
(CPU: AMD A10-4600M APU (with integral video plate). 2.3 GHz, RAM: 8GB)
· Виртуальная операционная система Ubuntu 14.04 x64 (компилятор gcc 4.9.0)
· Ключи компиляции программы : -Wall -о
3. Результаты экспериментов
Таблица 3
Рисунок 2
Таблица 4
Рисунок 3
Таблица 5
|
Поиск ключа с индексом Sizeofarray+1 (несуществующий индекс) |
|||
|
Кол-во элементов |
Время линейного поиска, с |
Время интеполяционного поиска, с |
|
|
300000000 |
2,000002211 |
0 |
|
|
310000000 |
2,000002211 |
0 |
|
|
320000000 |
2,000002211 |
0 |
|
|
330000000 |
3,000003111 |
0 |
|
|
340000000 |
2,000002211 |
0 |
|
|
350000000 |
2,000002211 |
0 |
|
|
360000000 |
2,000002211 |
0 |
|
|
370000000 |
23,00002311 |
0 |
|
|
380000000 |
27,00002711 |
0 |
|
|
390000000 |
59,00006111 |
0 |
|
|
400000000 |
84,00008511 |
0 |
Рисунок 4
Список использованной литературы
1. Программирование интерполяции [электронный реусурс]//Студопедия Ваша школопедия// URL: http://studopedia.ru/3_198520_programmirovanie-interpolyatsii.html
2. Интерполяция [электронный реусурс]//Wikipedia Свободная энциклопедия// URL: https://ru.wikipedia.org/wiki/%C8%ED%F2%E5%F0%EF%EE%EB%FF%F6%E8%FF#.D0.92_.D1.8F.D0.B7.D1.8B.D0.BA.D0.B0.D1.85_.D0.BF.D1.80.D0.BE.D0.B3.D1.80.D0.B0.D0.BC.D0.BC.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.B8.D1.8F
3. Алгоритмы. Введение в разработку и анализ (2006) (Левитин А.): Перевод с английского/ под редакцией С.Г. Трибуга и И.В. Красикова. - Москва: Издательский дом «Вильямс», 2006. - 576с.
Размещено на Allbest.ru
...Подобные документы
Сущность построения, особенности применения и теоретическое обоснование алгоритмов приближенного решения математических задач. Основы численного метода, нахождение интерполяционного полинома методом Лагранжа. Руководство программиста и пользователя.
курсовая работа [527,6 K], добавлен 16.08.2012Теоретические сведения об алгоритмах поиска подстроки в строке. Глобализация информации в сети Internet. Интеллектуальный поиск. Алгоритм последовательного (прямого) поиска, Рабина и их применение. Анализ алгоритмов. Реализация программного кода.
курсовая работа [230,8 K], добавлен 12.02.2009Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".
курсовая работа [2,2 M], добавлен 29.05.2015Построение интерполяционного полинома Ньютона по значениям функции в узлах согласно методу Лагранжа. Составление алгоритмов решения задачи, их реализация на программном уровне на языке Turbo Pascal. Представление результатов работы программы Polinom.
курсовая работа [667,9 K], добавлен 01.10.2010Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
курсовая работа [132,0 K], добавлен 09.12.2008Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели.
курсовая работа [581,5 K], добавлен 13.10.2008Постановка задачи и ее формализация. Поиск значений интерполяционного многочлена в точках x1 и x2. Поиск минимума функции F(x) на отрезке [a;b]. Проверка условий сходимости методов. Тестирование программных модулей. Детализированная схема алгоритма.
курсовая работа [893,0 K], добавлен 04.02.2011Характеристика параметрических методов решения задач линейного программирования: методы внутренней и внешней точки, комбинированные методы. Алгоритм метода барьерных поверхностей и штрафных функций, применяемых для решения задач большой размерности.
контрольная работа [59,8 K], добавлен 30.10.2014Оптимизация движения автобетоносмесителей на строительную площадку с минимализацией времени и средств при строительстве. Расчет технических характеристик здания и определения минимального комплекта машин. Применение методов линейного программирования.
курсовая работа [10,9 M], добавлен 06.03.2015Оптимизационная задача линейного программирования. Виды задач линейного программирования. Принятие решений на основе количественной информации об относительной важности критериев. Выбор средств разработки. Программный комплекс векторной оптимизации.
дипломная работа [1,3 M], добавлен 27.03.2013Теоретическое описание линейного списка с алгоритмами реализации основных операций. Понятия, механизмы объектно-ориентированного программирования. Возможности проектируемого контейнера пользователей, его реализация на основе линейного списка с заголовком.
курсовая работа [475,2 K], добавлен 26.02.2015Формула Симпсона как интеграл от интерполяционного многочлена второй степени, рассмотрение сфер использования. Знакомство с основными особенностями и этапами написания программы для численного интегрирования с помощью формулы Симпсона, анализ примеров.
практическая работа [153,8 K], добавлен 16.03.2015Составление и программная реализация в среде Borland Delphi 7.0 алгоритмов итерационного и рекурсивного вариантов решения задачи поиска с возвращением. Исследование асимптотической временной сложности решения в зависимости от количества ячеек на плате.
курсовая работа [57,5 K], добавлен 25.06.2013Возможности и синтаксис команд MATLAB, листинг программы и описание цикла. Порядок составления программы вычисления коэффициентов алгебраического интерполяционного многочлена и построения сплайн-функции, "склеенной" из кусков многочленов 3-го порядка.
лабораторная работа [30,8 K], добавлен 04.07.2009Применение методов линейного программирования для решения оптимизационных задач. Основные понятия линейного программирования, свойства транспортной задачи и теоремы, применяемые для ее решения. Построение первичного опорного плана и системы потенциалов.
курсовая работа [280,8 K], добавлен 17.11.2011Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.
дипломная работа [2,4 M], добавлен 20.11.2010Строение системы уравнений-ограничений и ее переменных, графический способ решения задач линейного программирования на плоскости. Выражение неизвестных через две независимые переменные, являющиеся координатными осями графика. Значение целевой функции.
лабораторная работа [61,4 K], добавлен 07.01.2011Методы реализации алгоритмов сортировки и алгоритмов поиска на языках программирования высокого уровня. Программирование алгоритмов сортировки и поиска в рамках создаваемого программного средства на языке Delphi. Создание руководства пользователя.
курсовая работа [1,7 M], добавлен 16.04.2012Интерполирование функций методом Лагранжа. Получение функциональной зависимости по экспериментальным данным. Близость интерполяционного многочлена к заданной функции. Интерполяционный полином в форме Лагранжа. Построение интерполяционных графиков.
лабораторная работа [315,8 K], добавлен 24.05.2014Особенности задач линейного программирования. Симплексный метод решения задач линейного программирования. Обоснование выбора языка, инструментария программирования, перечень идентификаторов и блок-схема алгоритма. Логическая схема работы программы.
дипломная работа [2,4 M], добавлен 13.08.2011
