Лекция 15. Математические методы (поиск, сортировка вставкой) (1152917)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

1Воробьева И.А. «Информатика. Язык Питон»Основные математические методы,используемые при решении числовых задач (часть 1)Бинарный поиск и нахождение корня уравнения методом дихотомии. Методысортировки: метод вставки, выбора, метод пузырька, сортировка слиянием.11. МАТЕМАТИЧЕСКИЕ МЕТОДЫ ПОИСКА И СОРТИРОВКИ11.1. Понятие сложности задачиВычислительная сложность (алгоритма) — понятие в информатикеи теории алгоритмов, обозначающее функцию зависимости объёмаработы, которая выполняется некоторым алгоритмом, от размеравходных данных.Мы почти всегда имеем дело с размером входных данных – .

Подработой алгоритма, как правило, считают так называемое «числоэлементарных шагов» алгоритма, например: число сравнений, числообменов между элементами – какие-то ключевые действия алгоритма.Функцию сложности редко выражают в точном числе шаговпопросту потому, что иногда бывает невозможно дать даже оценку этойсложности. Оценку сложности записывают в виде(читается, как«О большое от..»).Существует целый раздел науки, изучающий вычислительнуюсложность, он называется теорией сложности вычислений и являетсядостаточно трудным для изучения.Понятия сложности задачи и сложности алгоритма хоть и неявляются идентичными понятиями (для решения одной и той же задачиможно предложить несколько алгоритмов разной вычислительнойсложности), но все же очень тесно связаны друг с другом.Мы затронем понятие сложности алгоритмов только на оченьповерхностном уровне.

Для начала вычислим пару полезных формул,которые пригодятся для вычисления сложности алгоритмов, которыебудут рассмотрены в этой лекции, а затем попытаемся понять, какимобразом сложность задачи (алгоритма) влияет на его практическуюприменимость.2Воробьева И.А. «Информатика. Язык Питон»Пусть– четное. Тогда легко подсчитать сумму:. (1)Очевидно, что, если (n-1) - четное.Теперь, используя формулы (1) и (2), видим, что для(2)– нечетного:.Таким образом, для четного и нечетного(3)формулы совпадают.Мы уже говорили, что, как правило, говорят не о точном числешагов, а о некой оценке сложности алгоритма.

Например, если выпосчитали, что алгоритм выполняетшагов, где – константа, тогдаговорят, что оценка сложности такого алгоритма. Если получиличисло шагов равное полиному, тогда говорят, чтооценка сложности такого алгоритмаИз формулы отбрасывается все, что при большом росте оказываетсущественно меньшее влияние, на время работы алгоритма чем то, чтоосталось. С точки зрения теории сложности вычислений, алгоритмы счислом шагов равными числом шагов равным-идентичны.Для того чтобы понять почему так, достаточноприблизительно оценить время работы алгоритмов с различнымиоценками сложности.Для начала стоит подсчитать, сколько секунд в году:.Теперь вспомним о тактовой частоте процессора.

Она показывает (вочень сильно огрубленной форме) примерное число элементарныхопераций, производимых компьютером за 1 секунду. Например, еслитактовая частота равна 2,3 ГГц, следовательно, число тактовых операцийможно принять за. Значит, наш компьютер за год непрерывной3Воробьева И.А. «Информатика. Язык Питон»работы сможет свершить (отбросим все константы) порядкаопераций. Допустим еще более серьезное огрубление (что, конечно же,не будет правдой) в пользу компьютера и будем считать егоэлементарную операцию равновесной элементарной операцииалгоритма, т.е.

примем, что время выполнения одной элементарнойоперации алгоритма равносекунды. Теперь можно составитьтаблицу, которая покажет, сколько времени потребуется компьютеру длявыполнения алгоритмов различной сложности в зависимости от роставхода задачи – .Таблица 11.1.1030операцииоперацийопераций1001 000операцииоперацииоперацииоперацийоперацийоперацийоперацийопераций1024---------Из таблицы видно, что алгоритмы, у которых вычислительнаясложность зависит от n как экспонента или факториал, практически неприменимы, так как даже очень небольшой рост n приводит к тому, чтоалгоритм не завершится «никогда» (не при нашей жизни). Заметим, чтоочень широкий класс практических оптимизационных задач как разтаковы, что для них не придумано алгоритмов, которые бы имели оценкисложности лучше, чем экспоненциальная оценка или факториальная.При поиске «хороших» алгоритмов очень большое вниманиеуделяется способам сокращения числа полных просмотров или4Воробьева И.А.

«Информатика. Язык Питон»переборов всех вариантов решений в поисках лучшего (типичныеоптимизационные задачи, например, найти кратчайший путь из всехвозможных).В этой лекции мы рассмотрим один алгоритм поиска и несколькоалгоритмов сортировки.

С задачами поиска, сортировки или фильтрации(напрямую связана с поиском и сортировкой) информациивысталкиваетесь очень часто. Столь же часто речь идет о решении этихзадач на очень больших массивах данных (поиск в интернете, поиск вбольших интернет-магазинах и т.п.), а это значит, что важны практическиреализуемые алгоритмы.11.2. Метод дихотомии (деления отрезка пополам)Метод, который мы рассмотрим, обладает двумя прекраснымисвойствами: он предельно прост, распространяется на многие задачи икрайне эффективен, так как позволяет сокращать число просмотровразличных вариантов решения вдвое за один шаг алгоритма. Этотипичный представитель общего метода "разделяй и властвуй", нокроме разбиения исходной задачи на более мелкие, он позволяетотбрасывать часть задач, даже не рассматривая их.У метода много названий: «дихотомии», «деления отрезка пополам»или «бинарного поиска» -- это все один и тот же метод, на основекоторого строятся алгоритмы решений конкретных задач.Суть метода:метод применим к любой упорядоченнойпоследовательности (дискретной или непрерывной) на ограниченноминтервале (отрезке).1.

Выбирается «середина отрезка».2. Оценивается состояние последовательности в этой «середине» ипринимается решение, какую из «половин отрезка» (левую илиправую) можно отбросить.3. Далее задача решается аналогично, но на «отрезке» вдвое короче.5Воробьева И.А. «Информатика. Язык Питон»Давайте представим, что нам надо найти какое-то заданное число –«КЛЮЧ поиска» в упорядоченной последовательности длины из чисел.Очевидноерешение–просмотретьпоэлементновсюпоследовательность.

Сложность– не большая, но если эта задачаявляется только частью другой, более сложной задачи, то существенноесокращение числа шагов было бы очень желательно (посмотрите таблицу11.1. для строки). А вот, что нам даст применение метода дихотомиик данной задаче поиска. Приведем сразу решение, записанное напсевдокоде.Алгоритм бинарного поиска на псевдокоде.– упорядоченный массив длины . – ключ поиска.– левая граница, – правая граница индексов поиска.Алгоритм возвращает флагв случае успеха (ключнайден по индексу ) и, если ключа нет в массиве.SEARCH_BIN( a, b, X )Flag  FalseWHILE a ≤ b AND NOT Flag:c  (a + b) // 2 # целочисленное деление (найти середину отрезка)IF K = X[c] THEN:Flag  True # ключ найден по индексуELSE IF K < X[c] THEN:b  c – 1 # обновляем правую границуELSE K > X[c]:a  c + 1 # обновляем левую границуЧисло шагов алгоритма –Сложность алгоритма –Мы получили предельно хорошую оценку сложности решения.Рассмотрим, как работает алгоритм на конкретных примерах.6Воробьева И.А.

«Информатика. Язык Питон»Пример 11.1. Поиск в массиве для ключа K=91 методом бинарного поиска.Массив (n=8) 2 6 15 25 33 60 61 90ключ K=91a= 1, b = 8Шаг 1c = (1 + 8)//2 = 42 6 15 25 33 60 61 90a=5Шаг 2c = (5 + 8)//2 = 62 6 15 25 33 60 61 90a=7Шаг 3c = (7 + 8)//2 = 72 6 15 25 33 60 61 90a=8Шаг 4c = (8 + 8)//2 = 82 6 15 25 33 60 61 90a = 9  Flag = False (ключ не найден)Массив (n=8) 2 6 15 25 33 60 61 90ключ K=2a= 1, b = 8Шаг 1c = (1 + 8)//2 = 42 6 15 25 33 60 61 90b=3Шаг 2c = (1 + 3)//2 = 22 6 15 25 33 60 61 90b=1Шаг 3c = (1 + 1)//2 = 12 6 15 25 33 60 61 90 Flag = True (ключ найден по индексу = 1)7Воробьева И.А.

«Информатика. Язык Питон»Одним из применений данного метода является алгоритм поискакорня уравнениядля монотонных функций, изменяющих знакна отрезке, что приведет к неравенству:. Тогдаобновление границ на очередном шаге алгоритма происходит поправилу:Если, тогда.Иначе. Процесс повторяется до техпор, пока длина отрезкане станет меньше заданной точностипоиска решения.11.3. Сортировка11.3.1.

Сортировка вставкойОдним из наиболее простых и естественных методов внутреннейсортировки является сортировка вставкой. Идея алгоритма оченьпроста. Пусть имеется массив ключей. Для каждогоэлемента массива, начиная со второго, производится сравнение сэлементами с меньшим индексом (элементпоследовательносравнивается с элементами) и до тех пор, пока дляочередного элементавыполняется соотношение, приэтомименяются местами. ЕСЛИ удается встретить такой элемент, что, ИЛИ ЕСЛИ достигнута нижняя граница массива,производится переход к следующему шагу сортировки: обработкеследующего элемента(пока не будет обработан последнийэлемент массива).Чтобы избежать лишних «обменов», так как это три операции, а неодна можно сначала сохранитьв переменную-буфер , и сдвигатьвправо элементы:пока выполняется. А потом вставить на нужную позицию (см.

алгоритм напсевдокоде).Легко видеть, что в лучшем случае (когда массив уже упорядочен)для выполнения алгоритма с массивом из элементов потребуетсясравнение и 0 пересылок. В худшем случае (когда массивупорядочен в обратном порядке) потребуетсясравнений и8Воробьева И.А. «Информатика. Язык Питон»столько же пересылок. Таким образом, можно оценивать сложностьметода простых включений как.Алгоритм сортировки вставкой на псевдокоде.– массив длины .– временная переменная для «элемента-вставки».INSERTION_SORT( X )FOR j=2 TO n:K  X[j] # зафиксируем очередной элемент для вставки# поиск места для вставки K среди элементов X[1 .. j – 1] сосдвигомij–1WILE i > 0 AND X[i] > K:X[i + 1]  X[i] # сдвиг элементов вправоii–1X[i+1]  K # вставкаСложность алгоритма –Достоинства: сортировка «на месте», т.е.

Характеристики

Тип файла PDF

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

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

Список файлов лекций