Главная » Все файлы » Просмотр файлов из архивов » Файлы формата DJVU » Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013)

Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013), страница 14

DJVU-файл Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013), страница 14 Методы дискретной оптимизации (3258): Книга - 8 семестрТ. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013): Методы дискретной оптимизации - DJVU, страница 14 (3258) - Сту2019-09-19СтудИзба

Описание файла

DJVU-файл из архива "Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013)", который расположен в категории "". Всё это находится в предмете "методы дискретной оптимизации" из 8 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр DJVU-файла онлайн

Распознанный текст из DJVU-файла, 14 - страница

а Сделайте заключение, что в приведенном фрагменте кода правильно вычисля- ется значение полинома, который задается коэффициентами ао, аз,..., а„. Глава 2. Прнстулаем к изучению 2.4. Инверсии Пусть А[1 .. п] представляет собой массив из и различных чисел. Если з с з и А(з] > А[2], то пара (з, з) называется инверсией А. а Перечислите пять инверсий массива (2,3,8,6,1). 6. Каюй массив из элементов множества (1, 2,..., и) содержит максимальное количество инверсий? Сюлъю инверсий в этом массиве? в. Какая существует взаимосвязь между временем сортировки методом вставок и юличестаом инверсий во входном массиве? Обоснуйте свой ответ.

а Разработайте алгоритм, определяющий количество инверсий, содержащихся в произвольной перестановке и элементов, время работы которого в наихудшем случае равно гЭ(п 18 и). (Указание: модифицируйте алгоритм сортировки слиянием.) Заключительные замечания В 19б8 году Кнут (Клпбз) опубликовал первый из трех томов, объединенных названием т)зе Аи ог Сотригег Ригйгаттгнй (Искусство программирования) [208- 210]".

Этот первый том стал введением в современные компьютерные алгоритмы с акцентом на анализе времени нх работы, а весь трехтомник до сих пор остается интереснейшим н ценнейшим пособием по многим темам, представленным в данной книге. Согласно Кнуту, слово "алгоритм" происходит от имени персидского математика )Х века аль-Хорезми (а1-КЬоьвалзш1).

Ахо (АЬо), Хопкрофт (Норсгой) и Ульман (\ЛЬпап) [5] являются сторонниками асимптотнчесюго анализа алгоритмов (с использованием обозначений, вводимых в главе 3, включая О-обозначения), являющегося средством сравнения их относительной производительности. Они также популярнзируют применение рекуррентных соотношений для описания времени работы рекурсивных алгоритмов. Кнут [210] с энциклопедичесюй полнотой рассмотрел многие алгоритмы сортировки.

Его сравнение алгоритмов сортировки включает в себя подробный анализ с точным подсчетом шагов, подобный проведенному в этой книге для сортировки методом вставок. В ходе обсуждения Кнутом алгоритма сортировки вставкой приводится несколько вариаций этого алгоритма. Важнейшей из них является сортировка Д.Л. Шелла (ПЛ..

8Ьей), который использовал сортировку методом ггИмеется руссклй перемю зтнх книг: Д. Кнут. Нскусстю лрограммлроволал, т. 1. Ословлыг азгорлтмы. 1-е юд. — Мг И.Д. "Вильямс", 2000; Д. Кнут. Искусство лрогрхммлровалкя, т. 2. Паьучаслеллме алгоратмы, 1-е лзд. — Мз И.Д. "Внлькмс? 2000; Д. Кнут. Искусство лрограммщювалня, т. 1. Сортировка ч ленск, 2-е юд.— Мз И,Д.

"Внльямсз 2000. Кроме того, уме после непнсення данной кннгн вымел очерелной том тнсяэсслма лрограммнювалая": Д. Кнут. Искзсство лрсграмчщювалая, т. й Х Камбаяаторлые алгоритмы, часть 1.— Мг ИЛ "Вюмвмс", 2013. з звк згзз бб Часть а Основы вставок для упорядочения периодических подпоследовательностей, чтобы получить более производительный алгоритм сортировки.

В книге Кнута также описана сортировка слиянием. В ней же упоминается, что в 1938 году была создана механическая машина, способная за один проход объединять две стопки перфокарт. По всей видимости, первым программу для сортировки методом слияния (предназначенную для компьютера Е1УЧАС) в 1945 году разработал Джон фон Нейман (в. чоп Ыепшапп), который был одним из создателей теории вычислительных машин. Ранние этапы развития в области доказательства корректности программ описаны Гризом (Свпез) 11521, который считает, что первая статья по этой теме была написана П.

Науром (Р. Хаог). Авторство понятия инварианта цикла Гриз приписывает Р. Флойду (К. %. Р!суд). В учебнике Митчелла (М11спе11) [254) описывается прогресс, достигнутый в области доказательства корректности программ в настоящее время. Глава 3. Рост функций Определенный в главе 2 порядок роста, характеризующий время работы алгоритма, является наглядным показателем эффективности алгоритма, а также позваляет сравнивать производительность различных алгоритмов. Если количество сортируемых элементов п становится достаточно большим, производительность алгоритма сортировки по методу слияний, время работы которого в наихудшем случае возрастает как Й(п )к и), становится выше производительности алгоритма сортировки вставкой, время работы которого в наихудшем случае возрастает как 6(п ). Несмотря на то что в некоторых случаях можно определить точное время работы алгоритма, как это было сделано для алгоритма сортировки методом вставок в главе 2, обычно не стоит тратить лишние усилия для получения оценки с высокой точностью.

Для достаточно больших входных данных постоянные множители и слагаемые низшего порядка, фигурирующие в выражении для точного времени работы алгоритма, подавляются эффектами, вызванными увеличением размера входных данных. Рассматривая входные данные достаточно больших размеров для оценки только такой величины, как порядок роста времени работы алгоритма, мы тем самым изучаем асимитотическую эффективность алгоритмов. Это означает, что нас интересует толью то, как время работы алгоритма растет с увеличением размера входных данных в пределе, когда этот размер увеличивается до бесконечности.

Обычно алгоритм, более эффективный в асимптотическом смысле, будет более производительным для всех входных данных, за исключением очень маленьких. В этой главе приводится несколыю стандартных методов, позволяющих упростить асимптотический анализ алгоритмов. В начале следующего раздела вводится несколько видов "асимптотических обозначений", одним из которых являются уже известные нам 9-обозначения. Далее представлены некоторые соглашения по поводу обозначений„принятых в данной книге. Наконец, в завершающей части главы, рассматривается поведение функций, часто встречающихся в ходе анализа алгоритмов.

Часть 6 Основы 3.1. Аеимптотические обозначения Обозначения, используемые нами для описания асимптотического поведения времени работы алгоритма, используют функции, областью определения которых является множество неотрицательных целых чисел )з = (0,1,2,...). Подобные обозначения удобны для описания времени работы Т(п) в наихудшем случае как функции, определенной только для целых чисел, представляюших собой размер входных данных. Однако иногда удобно изменить толювание асимптотических обозначений тем или иным не совсем корректным образом. Например, можно распространить эти обозначения на действительные числа или, наоборот, ограничить их областью, являющейся подмножеством натуральных чисел.

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

Однако фактически асимптотические обозначения применяются к функциям. Вспомним, что мы охарактеризовали время работы сортировки вставкой в наихудшем случае как апз + 6п + с для некоторых констант а, 6 и с. Записывая время работы сортировки вставкой как 9(пз), мы абстрагируемся от некоторых деталей этой функции. Поскольку асимптотические обозначения применимы к функциям, то то, что мы записываем просто как 9(п ), представляет собой функцию ап + Ьп+ с, которая в данном случае, помимо прочего, описывает время работы сортировки вставюй в наихудшем случае. В этой книге функции, к которым мы применяем асимптотические обозначения, обычно характеризуют время работы алгоритма.

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

Другими словами, часто желательно получить всеобъемлющее утверждение, охватывающее все варианты входных данных, а не только наихудший случай. Мы познакомимся с асимптотическими обозначениями, которые хорошо подходят для характеристики времени выполнения безотносительно ко входным данным. бд Глава 3. Рост функций ев-обозначения В главе 2 было показано, что время работы сортировки вставкой в наихудшем случае составляет Т(п) = ез(пз). Давайте разберемся в смысле данного обозначения. Для заданной функции д(п) запись ез(д(п)) обозначает множество функций ()(д(п)) = (У(п): сугцествуют положительные константы сы сз и пс, такие, что О < с)д(п) < у(п) < сзд(п) для всех и ~ по) Функция з (и) принадлежит множеству ез(д(п)), если существуют положительные константы с) н сз, такие, что при достаточно больших и эта функция может быль заключена в рамки между с)д(п) и сад(п).

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5288
Авторов
на СтудИзбе
417
Средний доход
с одного платного файла
Обучение Подробнее