|
КОНЕЦ
айдите длину кратчайшего пути от начального до конечного узла.
Ответ: Длина кратчайшего пути равна 2.
Н
айдите длину кратчайшего пути от «саЬ» к «bat
Ответ-. Длина кратчайшего пути равна 2.
П
еред вами небольшой граф моего утреннего распорядка.
Д
А.
ПРОСНУТЬСЯ
ПРИНЯТЬ ДУШ
ПОЗАВТРАКАТЬ А ПОЧИСТИТЬ ЗУБЫ
ь.
1. ПРОСНУТЬСЯ 1. ПОЧИСТИТЬ ЗУБЫ
ПОЗАВТРАКАТЬ
ПРИНЯТЬ ДУШ
с.
ПРИНЯТЬ ДУШ I. ПРОСНУТЬСЯ
ПОЧИСТИТЬ ЗУБЫ
ПОЗАВТРАКАТЬ
ля каждого из следующих трех списков укажите, действителен он или недействителен.
Ответы. А — недействителен; В — действителен; С — недействителен.
Н
емного увеличим исходный граф. Постройте действительный список для этого графа.
Ответ: 1 — Проснуться; 2 — Сделать зарядку; 3 — Принять душ; 4 — Почистить зубы; 5 — Одеться; 6 — Упаковать обед; 7 — Позавтракать.
Какие из следующих графов также являются деревьями?
А
. ь. с.
Ответы: А — дерево; В — не дерево; С — дерево. В последнем примере дерево просто повернуто набок. Деревья составляют подкатегорию графов, поэтому любое дерево является графом, но граф не обязательно является деревом.
Глава 7
К
С. НАЧАЛО
КОНЕЦ
аков вес кратчайшего пути от начала до конца в каждом из следующих графов?
Ответы: А — 8; В — 60; С — каверзный вопрос (кратчайший путь не существует из-за наличия цикла с отрицательным весом).
Глава 8
Вы работаете в фирме по производству мебели и поставляете мебель по всей стране. Коробки с мебелью размещаются в грузовике. Все коробки имеют разный размер, и вы стараетесь наиболее эффективно использовать доступное пространство. Как выбрать коробки для того, чтобы загрузка имела максимальную эффективность? Предложите жадную стратегию. Будет ли полученное решение оптимальным?
Ответ: Жадная стратегия заключается в том, чтобы выбрать самую большую коробку, помещающуюся в оставшемся пространстве, и повторять это до тех пор, пока еще можно выбрать хотя бы одну коробку. Нет, такое решение оптимальным не будет.
Вы едете в Европу, и у вас есть 7 дней на знакомство с достопримечательностями. Вы присваиваете каждой достопримечательности стоимость в баллах (насколько вы хотите ее увидеть) и оцениваете продолжительность поездки. Как обеспечить максимальную стоимость (увидеть все самое важное) во время поездки? Предложите жадную стратегию. Будет ли полученное решение оптимальным?
Ответ: Выбирайте достопримечательность с наибольшей стоимостью в баллах, которую вы успеете посетить в оставшееся время. Остановитесь, когда таких достопримечательностей не останется. Нет, такое решение оптимальным не будет.
Для каждого из приведенных ниже алгоритмов укажите, является ли этот алгоритм жадным или нет.
Быстрая сортировка.
Ответ: Нет.
Поиск в ширину.
Ответ: Да.
Алгоритм Дейкстры.
Ответ: Да.
Почтальон должен доставить письма в 20 домов. Ему нужно найти кратчайший путь, проходящий через все 20 домов. Является ли эта задача NP-полной?
Ответ: Да.
Имеется задача поиска максимальной клики в множестве людей (кликой называется множество людей, каждый из которых знаком со всеми остальными.) Является ли эта задача NP-полной?
Ответ: Да.
Вы рисуете карту США, на которой два соседних штата не могут быть окрашены в одинаковый цвет. Требуется найти минимальное количество цветов, при котором любые два соседних штата будут окрашены в разные цвета. Является ли эта задача NP-полной?
Ответ: Да.
Глава 9
Предположим, к предметам добавился еще один: МРЗ-плеер. Он весит 1 фунт и стоит $1000. Стоит ли брать его?
Ответ'. Да. Вы сможете положить в рюкзак МРЗ-плеер, iPhone и гитару общей стоимостью $4500.
Предположим, что вы собираетесь в турпоход. Емкость вашего рюкзака составляет 6 фунтов, и вы можете взять предметы из следующего списка. У каждого предмета имеется стоимость; чем она выше, тем важнее предмет:
Вода, 3 фунта, 10
Книга, 1 фунт, 3
Еда, 2 фунта, 9
Куртка, 2 фунта, 5
Камера, 1 фунт, 6
Как выглядит оптимальный набор предметов для похода?
Ответ'. Возьмите воду, еду и камеру.
Нарисуйте и заполните таблицу для вычисления самой длинной общей подстроки между строками blue и clues.
Ответ:
С L V Е S
О
|
О
|
о
|
о
|
о
|
о
|
1
|
О
|
О
|
о
|
о
|
о
|
2
|
о
|
о
|
CL
|
О
|
О
|
3
|
о
|
ВL
U
Е
Глава 10
В примере с Netflix сходство между двумя пользователями оценивалось по формуле расстояния. Но не все пользователи оценивают фильмы одинаково. Допустим, есть два пользователя, Йоги и Пинки, вкусы которых совпадают. Но Йоги ставит 5 баллов любому фильму, который ему понравился, а Пинки более разборчива и ставит «пятерки» только самым лучшим фильмам. Вроде бы вкусы одинаковые, но по метрике расстояния они не являются соседями. Как учесть различия в стратегиях выставления оценок?
Ответ: Можно воспользоваться нормализацией: вы вычисляете среднюю оценку для каждого человека и используете ее для масштабирования оценок. Например, вы определили, что средняя оценка Пинки равна 3, а средняя оценка Йоги - 3,5. Соответственно оценки Пинки немного увеличиваются так, чтобы ее средняя оценка тоже была равна 3,5. После этого оценки можно сравнивать по единой шкале.
Предположим, Netflix определяет группу «авторитетов». Скажем, Квентин Тарантино и Уэс Андерсон относятся к числу авторитетов Netflix, поэтому их оценки оказывают более сильное влияние, чем оценки рядовых пользователей. Как изменить систему рекомендаций, чтобы она учитывала повышенную ценность оценок авторитетов?
Ответ: При применении алгоритма k ближайших соседей можно увеличить вес оценок авторитетов. Предположим, у вас трое соседей: Джо, Дэйв и Уэс Андерсон (авторитет.) Они поставили фильму «Гольф-клуб» оценки 3, 4 и 5 соответственно. Вместо того чтобы вычислять среднее арифметическое их оценок (3 + 4 + 5/ 3 = 4 звезды), вы просто повышаете вес оценки Уэса Андерсона: 3 + 4 + 5 + 5 + 5/ 5 = 4,4 звезды.
У сервиса Netflix миллионы пользователей. В приведенном ранее примере рекомендательная система строилась для пяти ближайших соседей. Пять — это слишком мало? Слишком много?
Ответ: Слишком мало. Если ограничиться малым числом соседей, существует высокая вероятность того, что результаты будут искажены. Существует хорошее эмпирическое правило: для А пользователей следует рассматривать sqrt(N) соседей.
Грокаем
алгоритмы
Иллюстрированное пособие
для программистов и любопытствующих
Адитья Бхаргава
Алгоритмы — это всего лишь пошаговые алгоритмы решения задач, и большинство таких задач уже были кем-то решены, протестированы и проверены. Можно, конечно, погрузиться в глубокую философию гениального Кнута, изучить многостраничные фолианты с доказательствами и обоснованиями, но хотите ли вы тратить на это свое время?
Откройте великолепно иллюстрированную книгу, и вы сразу поймете, что алгоритмы — это просто.
А грокать алгоритмы — это веселое и увлекательное занятие.
С
ISBN: 978-5-496-02541-6
^ППТЕР
9 785496 025416
Заказ книг:
тел.: (812) 703-73-74 books@piter.com
WWW.PITER.COM
каталог книг и интернет-магазин
(в) vk.com/piter_pul @ instagram.com/pl (7) facebook.com/idJ
в
Do'stlaringiz bilan baham: |
