Совершенный алгоритм. Жадные алгоритмы и динамическое программирование

Нет в наличии

Акции и скидки Поделиться


  • Артикул:00-01041598
  • Автор: Рафгарден Т.
  • ISBN: 978-5-4461-1445-0
  • Обложка: Мягкая обложка
  • Издательство: Питер (все книги издательства)
  • Город: Санкт-Петербург
  • Страниц: 256
  • Формат: 70x100/16
  • Год: 2022
  • Вес: 642 г
  • Серия: Библиотека программиста (все книги серии)
Развернуть ▼

Алгоритмы - это сердце и душа computer science. Без них не обойтись, они есть везде - от сетевой маршрутизации и расчетов по геномике до криптографии и машинного обучения. «Совершенный алгоритм» превратит вас в настоящего профи, который будет ставить задачи и мастерски их решать как в жизни, так и на собеседовании при приеме на работу в любую IT-компанию.
В новой книге Тим Рафгарден расскажет о жадных алгоритмах (задача планирования, минимальные остовные деревья, кластеризация, коды Хаффмана) и динамическом программировании (задача о рюкзаке, выравнивание последовательностей, кратчайшие пути, оптимальные деревья поиска).
Серия книг «Совершенный алгоритм» адресована тем, у кого уже есть опыт программирования, и основана на онлайн-курсах, которые регулярно проводятся с 2012 года. Вы перейдете на новый уровень, чтобы увидеть общую картину, разобраться в низкоуровневых концепциях и математических нюансах.

Содержание
Предисловие
О чем эта книга
Навыки, которые вы приобретете
В чем особенность книг этой серии
Для кого эта книга?
Дополнительные ресурсы
Благодарности
От издательства
Глава 13. Введение в жадные алгоритмы
13.1. Парадигма проектирования жадных алгоритмов
13.1.1. Парадигмы алгоритмов
13.1.2. Темы жадной парадигмы
13.2. Задача планирования
13.2.1. Постановка
13.2.2. Сроки завершения
13.2.3. Целевая функция
13.2.4. Решение упражнения 13.1.
13.3. Разработка жадного алгоритма
13.3.1. Два частных случая
13.3.2. Дуэльные жадные алгоритмы
13.3.3. Решения упражнений 13.2-13.3.
13.4. Доказательство правильности
13.4.1. Случай отсутствия совпадающих значений: высокоуровневый план
13.4.2. Обмен работами при последовательной инверсии
13.4.3. Анализ стоимости и преимущества
13.4.4. Обработка совпадений значений
13.4.5. Решения упражнений 13.4-13.5
Задачи на закрепление материала
Задачи по программированию
Глава 14. Коды Хаффмана
14.1. Коды
14.1.2. Коды переменной длины
14.1.3. Беспрефиксные коды
14.1.4. Преимущества беспрефиксных кодов
14.1.5. Определение задачи
14.1.6. Решения упражнений 14.1-14.2.
14.2. Коды в виде деревьев
14.2.1. Три примера
14.2.2. Какие деревья представляют беспрефиксные коды?
14.2.3. Определение задачи (в новой формулировке)
14.3. Жадный алгоритм Хаффмана
14.3.1. Построение деревьев путем последовательных слияний
14.3.2. Жадный критерий Хаффмана
14.3.3. Псевдокод
14.3.4. Пример
14.3.5. Более крупный пример
14.3.6. Время выполнения
14.3.7. Решение упражнения 14.3
14.4. Доказательство правильности
14.4.1. Высокоуровневый план
14.4.2. Подробности
Задачи на закрепление материала
Сложные задачи
Задачи по программированию
Глава 15. Минимальные остовные деревья
15.1. Определение задачи
15.1.1. Графы
15.1.2. Остовные деревья
15.1.3. Решение упражнения 15.1
15.2. Алгоритм Прима
15.2.1. Пример
15.2.2. Псевдокод
15.2.3. Простая реализация
15.3. Ускорение алгоритма Прима посредством куч
15.3.1. В поисках времени выполнения, близкого к линейному
15.3.2. Кучевая структура данных
15.3.3. Как использовать кучи в алгоритме Прима
15.3.4. Псевдокод
15.3.5. Анализ времени выполнения
15.3.6. Решение упражнения 15.3
15.4. Алгоритм Прима: доказательство правильности
15.4.1. Свойство минимального узкого места
15.4.2. Интересные факты об остовных деревьях
15.4.3. Доказательство теоремы 15.6 (из свойства минимального узкого места следует минимальное остовное дерево)
15.4.4. Сводя все воедино
15.5. Алгоритм Краскала
15.5.1. Пример
15.5.2. Псевдокод
15.5.3. Простая реализация
15.6. Ускорение алгоритма Краскала с помощью структуры данных Union-Find
15.6.1. Структура данных Union-Find
15.6.2. Псевдокод
15.6.3. Анализ времени выполнения
15.6.4. Быстрая и приближенная реализация структуры данных Union-Find
15.6.5. Решения упражнений 15.5-15.7
15.7. Алгоритм Краскала: доказательство правильности
15.8. Применение: кластеризация с одиночной связью
15.8.1. Кластеризация
15.8.2. Восходящая кластеризация
Задачи на закрепление материала
Задачи повышенной сложности
Задачи по программированию
Глава 16. Введение в динамическое программирование
16.1. Задача о взвешенном независимом множестве
16.1.1. Определение задачи
16.1.2. Естественный жадный алгоритм оказывается безуспешным
16.1.3. Подход «разделяй и властвуй»?
16.1.4. Решения упражнений 16.1-16.2
16.2. Линейно-временной алгоритм для взвешенного независимого множества на путях
16.2.1. Оптимальная подструктура и рекуррентное соотношение
16.2.2. Наивный рекурсивный подход
16.2.3. Рекурсия с кэшем
16.2.4. Восходящая итеративная реализация
16.2.5. Решения упражнений 16.3-16.4.
16.3. Алгоритм реконструкции
16.4. Принципы динамического программирования
16.4.1. Трехшаговый рецепт
16.4.2. Желаемые свойства подзадач
16.4.3. Повторяемый мыслительный процесс
16.4.4. Динамическое программирование против «разделяй и властвуй»
16.4.5. Почему «динамическое программирование»?
16.5. Задача о ранце
16.5.1. Определение задачи
16.5.2. Оптимальная подструктура и рекурренция
16.5.3. Подзадачи
16.5.4. Алгоритм динамического программирования
16.5.5. Пример
16.5.6. Реконструкция
16.5.7. Решения упражнений 16.5-16.6
Задачи на закрепление материала
Задачи повышенной сложности
Задачи по программированию
Глава 17. Расширенное динамическое программирование
17.1. Выравнивание последовательностей
17.1.1. Актуальность
17.1.2. Определение задачи
17.1.3. Оптимальная подструктура
17.1.4. Рекуррентное соотношение
17.1.5. Подзадачи
17.1.6. Алгоритм динамического программирования
17.1.7. Реконструкция
17.1.8. Решение упражнений 17.1-17.3
17.2. Оптимальные бинарные деревья поиска
17.2.1. Обзор бинарного дерева поиска
17.2.2. Среднее время поиска
17.2.3. Определение задачи
17.2.4. Оптимальная подструктура
17.2.5. Рекуррентные соотношения
17.2.6. Подзадачи
17.2.7. Алгоритм динамического программирования
17.2.8. Улучшение времени выполнения
17.2.9. Решения упражнений 17.4-17.5.
Задачи на закрепление материала
Задачи повышенной сложности
Задачи по программированию
Глава 18. Кратчайшие пути повторно
18.1. Кратчайшие пути с отрицательными длинами ребер
18.1.1. Задача о кратчайшем пути с единственным истоком
18.1.2. Отрицательные циклы
18.1.3. Решение упражнения 18.1
18.2. Алгоритм Беллмана-Форда
18.2.1. Подзадачи
18.2.2. Оптимальная подструктура
18.2.3. Рекурренция
18.2.4. Когда следует остановиться?
18.2.5. Псевдокод
18.2.6. Пример
18.2.7. Время выполнения
18.2.8. Маршрутизация интернета
18.2.9. Решения упражнений 18.2-18.3
18.3. Задача о кратчайшем пути для всех пар
18.3.1. Определение задачи
18.3.2. Сведение до кратчайших путей с единственным истоком
18.3.3. Решение упражнения 18.4
18.4. Алгоритм Флойда-Уоршелла
18.4.1. Подзадачи
18.4.2. Оптимальная подструктура
18.4.3. Псевдокод
18.4.4. Обнаружение отрицательного цикла
18.4.5. Резюме и открытые вопросы
18.4.6. Решения упражнений 18.5-18.6
Задачи на закрепление материала
Задачи повышенной сложности
Задачи по программированию
Эпилог: руководство по разработке алгоритмов
Подсказки и решения избранных задач


Оставьте отзыв о товаре
Рекомендуем

Артикул 00-01027143

Алгоритмы. Руководство по разработке

Алгоритмы. Руководство по разработке

1300 руб.

Купить
×

Диски

Журналы и бланки

Журналы для автодорог, дорожного хозяйстваЖурналы для АЗС и АЗГСЖурналы для аптекЖурналы для архивовЖурналы для аттракционовЖурналы для банковЖурналы для бассейновЖурналы для бухгалтерииЖурналы для газовых хозяйств, газораспределительных систем, ГАЗПРОМаЖурналы для гостиниц, общежитий, хостеловЖурналы для грузоподъемных механизмовЖурналы для делопроизводстваЖурналы для драгметалловЖурналы для ЖКХЖурналы для канатных дорог, фуникулеровЖурналы для кладбищЖурналы для конструкторских, научно-техническая документацияЖурналы для лесных хозяйствЖурналы для лифтовЖурналы для медицинских учрежденийЖурналы для МЧСЖурналы для нефтебазЖурналы для нефтепромысла, нефтепроводовЖурналы для образовательных учрежденийЖурналы для парикмахерских, салонов красоты, маникюрных, педикюрных кабинетовЖурналы для проверки и контроля госорганами, контролирующими организациямиЖурналы для промышленностиЖурналы для работ с повышенной опасностьюЖурналы для регулирования алкогольного рынкаЖурналы для сельских хозяйств, ветеринарииЖурналы для складовЖурналы для снегоплавильных пунктовЖурналы для стройки, строительстваЖурналы для тепловых энергоустановок, котельныхЖурналы для транспортаЖурналы для туризмаЖурналы для учреждений культуры, библиотек, музеевЖурналы для церкви, религиозных организацийЖурналы для шахт, рудников, метрополитенов, подземных сооруженийЖурналы для электроустановокЖурналы и бланки для армии, вооруженных силЖурналы и бланки для нотариусов, юристов, адвокатовЖурналы и бланки для организаций пищевого производства, общепита и пищевых блоковЖурналы и бланки для организаций, занимающихся охраной объектов и частных лицЖурналы и бланки для ФТС РФ (таможни)Журналы и бланки по экологииЖурналы и бланки, используемые в торговле, бытовом обслуживанииЖурналы и бланки, относящиеся к нескольким отраслямЖурналы по геодезии, геологииЖурналы по метрологииЖурналы по охране труда и технике безопасностиЖурналы по пожарной безопасностиЖурналы по психологииЖурналы по санитарии, проверкам СЭСЖурналы по связиЖурналы по эксплуатации зданий и сооруженийЖурналы по энергетикеЖурналы, бланки, формы для кадровых работЖурналы, бланки, формы документов для органов прокуратуры и суда, минюста, пенитенциарной системыЖурналы, бланки, формы документов МВД РФ, РосгвардииКомплекты документов и журналовОбложки для журналов и удостоверенийСамокопирующиеся бланки

Знаки безопасности, таблички, стенды

Вспомогательные знаки, таблички-наклейкиЗапрещающие знакиЗнаки для инвалидовЗнаки для уборки и сбора мусораЗнаки на автомобильЗнаки пожарной безопасностиЗнаки электробезопасностиИнформационные знаки для строительных площадокМедицинские и санитарные знакиНаклейкиПредписывающие знакиПредупреждающие знакиСтендыУказательные знакиЭвакуационные знакиЮмористические знаки

Календари

Книги

Букинистическая литератураГОСТы, ОСТыДетская литератураДомашний кругДругоеИскусство. Культура. ФилологияКниги в электронном видеКниги издательства "Комсомольская правда"Компьютеры и интернетКосмосНаука. Техника. МедицинаНормативные правовые актыОбщественные и гуманитарные наукиОхрана труда, обеспечение безопасностиПодарочные книгиПутешествия. Отдых. Хобби. СпортРелигия. Оккультизм. ЭзотерикаРостехнадзорСанПины, СП, МУ, МР, ГНСборники рецептур блюд для предприятий общественного питанияСНиП, СП, СО,СТО, РД, НП, ПБ, МДК, МДС, ВСНУчебный годХудожественная литератураЭкономическая литератураЭнциклопедии, справочники, словари

Курвиметры

Ленты с тиснением

Линейки

Авиационные и военные линейкиДетские линейкиМедицинские линейкиПортновские линейкиТехнические линейкиТрафареты с чертежными шрифтамиЧертежные линейки

Маркировочная продукция

Маркировка трубопровода "Вода"Маркировка трубопровода "Воздух"Маркировка трубопровода "Газ"Маркировка трубопровода "Жидкость"Маркировка трубопровода "Кислота"Маркировка трубопровода "Пар"Маркировка трубопровода "Прочие вещества"Маркировка трубопровода "Щелочь"

Материалы для типографии (мини-типографии)

Бумага для оргтехникиКлейПереплетные материалыПленка для печати и ламинацииФольга для тиснения

Металлические изделия (металлическая мебель, конструкции, навесы)

Металлическая мебельМеталлические изделия для дачи и дома

Носки и портянки

Одноразовая одежда

Охрана труда

Печати и штампы

Медицинские печати и штампыОснастки, самонаборные штампыПечати и штампы для бухгалтерии и делопроизводстваПечати и штампы для водителейПечать фирмы (организации, компании, подразделения, отдела)Штампы по техническому контролю, учету и хранению

Плакаты

Погоны министерств и ведомств

Подарки нашим покупателям

Полотенца

Портреты знаменитых людей

Сувениры

Бизнес сувениры, корпоративные подаркиБрелкиГимн России. Эксклюзивное графическое оформление в багетном обрамленииГудки и Рожки охотничьиЗажигалкиКружки для термопереносаКружки подарочныеПодарочные наборы игрПредметы интерьераСувениры, подарки для мужчин

Тир

Рогатки спортивные

Ткани

Товары "Юнармия"

Береты

Товары для дома и офиса

Грамоты и благодарностиИндикаторы стерилизацииКанцелярские товарыКаски, защитные очки, маскиКухонные принадлежностиОгнетушителиПланы эвакуацииСамоспасателиСредства дезинфекцииТовары для ремонтаФитолампы и прожекторыХозяйственные товарыЭлектроудлинители, тройники, катушкиЭлектроустановочные изделия

Товары для здоровья, БАДы

Аюрведические товарыСредства гигиены, косметика из минералов Мертвого моря

Товары для развития, игрушки

Бумажные модели

Товары для спорта, туризма и охоты

Походные сумки, рюкзаки и мешочки для храненияСигнальное снаряжениеТовары для фитнеса

Удостоверения, Свидетельства

Зачетные книжки, студенческие билетыУдостоверения для спортивных секцийУдостоверения рабочих различных специальностей

Упаковка, упаковочные материалы

Коробки картонные

Членские книжки

ГК, ГСК, членские книжки, пропуска и пр.Садоводческие книжки, членские книжки СНТ
;