Графовые алгоритмы и структуры данных

Нет в наличии
Акции и скидки Поделиться
  • Артикул:00-01029145
  • Автор: Рафгарден Тим
  • ISBN: 978-5-4461-1272-2
  • Обложка: Мягкая обложка
  • Издательство: Питер (все книги издательства)
  • Город: СПб
  • Страниц: 256
  • Формат: 70х100/16
  • Год: 2019
  • Вес: 344 г
  • Серия: Совершенный алгоритм (все книги серии)

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

Оглавление
Предисловие
О чем эта книга
Навыки, которые вы приобретете
В чем особенность книг этой серии
Для кого эта книга
Дополнительные ресурсы
Благодарности
От издательства
Графы: основы
Термины
Несколько приложений
Измерение размера графа
Число ребер в графе
Разреженные и плотные графы
Решение тестового задания
Представление графа
Списки смежности
Матрица смежности
Сравнение представлений
Решения тестовых заданий
Задачи на закрепление материала
Поиск в графе и его применения
Краткий обзор
Некоторые приложения
Бесплатные графовые примитивы
Обобщенный графовый поиск
Поиск в ширину и в глубину
Правильность алгоритма GenericSearch
Поиск в ширину и кратчайшие пути
Высокоуровневая идея
Псевдокод для алгоритма BFS
Пример
Правильность и время выполнения
Кратчайший путь
Решение тестового задания
Вычисление связных компонент
Связные компоненты
Применения
Алгоритм UCC
Пример
Правильность и время выполнения
Решение тестового задания
Поиск в глубину.
Пример
Псевдокод для алгоритма DFS
Правильность и время выполнения
Топологическая сортировка
Топологические упорядочивания
Когда есть топологическое упорядочивание
Вычисление топологического упорядочивания
Топологическая сортировка посредством алгоритма DFS
Пример
Правильность и время выполнения
Решения тестовых заданий
Вычисление сильно связных компонент
Определение сильно связных компонент
Почему поиск в глубину
Почему обратный граф
Псевдокод для алгоритма Косарайю
Пример
Правильность и время выполнения
Решения тестовых заданий
Структура Всемирной паутины
Веб-граф
"Галстук-бабочка"
Основные выводы
Задача повышенной сложности
Задача по программированию
Алгоритм кратчайшего пути Дейксгры
Задача о кратчайшем пути с единственным истоком
Определение задачи
Несколько допущений
Почему не поиск в ширину
Решение тестового задания
Алгоритм Дейкстры
Псевдокод
Пример
Почему алгоритм Дейкстры правилен
Фиктивная редукция
Плохой пример алгоритма Дейкстры
Правильность с неотрицательными реберными длинами
Реализация и время выполнения
Задачи на закрепление материала
Задача повышенной сложности
Задача по программированию
Куча
Структуры данных: краткий обзор
Выбор правильной структуры данных
Переход на следующий уровень
Поддерживаемые операции
Вставка и извлечение минимума
Дополнительные операции
Применения
Применение: сортировка
Применение: событийный менеджер
Применение: поддержка медианы
Ускорение алгоритма Дейкстры
Почему именно кучи
План
Поддержание инварианта
Время выполнения
Детали реализации
Кучи в виде деревьев
Кучи в виде массива
Реализация операции "Вставить" со временем
Реализация операции "Извлечь минимум" со временем
Задачи на закрепление материала
Задачи повышенной сложности
Задача по программированию
Дерево поиска
Отсортированные массивы
Отсортированные массивы: поддерживаемые операции
Неподдерживаемые операции
Деревья поиска: поддерживаемые операции
Детали реализации
Свойство дерева поиска
Высота дерева поиска
Реализация операции "Отыскать" со временем
Реализация операций "Минимум" и "Максимум" за время
Реализация операции "Предшественник" со временем
Реализация операции "Вывести в отсортированном порядке" со временем
Реализация операции "Вставить" со временем
Реализация операции "Удалить" со временем
Расширенные деревья поиска для операции "Выбрать"
Решение тестового задания
Сбалансированные деревья поиска
Более напряженные усилия для улучшения баланса
Повороты
Задачи на закрепление материала
Задача по программированию
Хеш-таблицы м фильтры Блума
Поддерживаемые операции
Решение тестового задания
Применения
Применение: устранение дублирования
Применение: задача о сумме двух чисел
Применение: поиск в огромных пространствах состояний
Решение тестового задания
Реализация: высокоуровневая идея
Два простых решения
Хеш-функции
Коллизии неизбежны
Разрешение коллизий: сцепление
Разрешение коллизий: открытая адресация
Что делает хеш-функцию хорошей
Решения тестовых заданий
Дополнительные детали реализации
Загрузка против результативности
Управление загрузкой вашей хеш-таблицы
Выбор своей хеш-функции
Выбор стратегии разрешения коллизий
Решение тестового задания
Фильтры Блума: основы
Поддерживаемые операции
Применения
Реализация
Фильтр Блума: эвристический анализ
Эвристические допущения
Доля установленных бит (равных 1)
Вероятность ложного утверждения
Кульминационный момент
Решение тестового задания
Задачи на закрепление материала
Задача по программированию
Приложение В. Краткий обзор асимптотической формы записи
В.1. Суть
В.2. Обозначение О-большое
В.З. Примеры
В.4. Обозначения Омега-большое и Тета-большое
Решения отдельных задач



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

Артикул 00822350

Теория регулирования в информационных системах управления

Теория регулирования в информационных системах управления

420-5% 400 руб.

Купить
×

Диски

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

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

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

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

Календари

Книги

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

Курвиметры

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

Линейки

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

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

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

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

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

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

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

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

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

Охрана труда

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

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

Плакаты

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

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

Полотенца

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

Сувениры

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

Тир

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

Ткани

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

Береты

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

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

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

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

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

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

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

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

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

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

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

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

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

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