Адитья Бхаргава – Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих (страница 32)
Предположим, имеются четыре хеш-функции, которые получают строки.
1. Первая функция возвращает «1» для любого входного значения.
2. Вторая функция возвращает длину строки в качестве индекса.
3. Третья функция возвращает первый символ строки в качестве индекса. Таким образом, все строки, начинающиеся с «a», хешируются в одну позицию, все строки, начинающиеся с «b», — в другую и т.д.
4. Четвертая функция ставит в соответствие каждой букве простое число: a = 2, b = 3, c = 5, d = 7, e = 11 и т.д. Для строки хеш-функцией становится остаток от деления суммы всех значений на размер хеша. Например, если размер хеша равен 10, то для строки «bag» будет вычислен индекс 3 + 2 + 17 % 10 = 22 % 10 = 2.
В каком из этих примеров хеш-функции будут обеспечивать хорошее распределение? Считайте, что хеш-таблица содержит 10 элементов.
5.5 Телефонная книга, в которой ключами являются имена, а значениями — номера телефонов. Задан следующий список имен: Esther, Ben, Bob, Dan.
5.6 Связь размера батарейки с напряжением. Размеры батареек: A, AA, AAA, AAAA.
5.7 Связь названий книг с именами авторов. Названия книг: «Maus», «Fun Home», «Watchmen».
Глава 6
Примените алгоритм поиска в ширину к каждому из этих графов, чтобы найти решение.
6.1 Найдите длину кратчайшего пути от начального до конечного узла.
6.2 Найдите длину кратчайшего пути от «cab» к «bat».
6.3 Перед вами небольшой граф моего утреннего распорядка.
Для каждого из следующих трех списков укажите, действителен он или недействителен.
6.4 Немного увеличим исходный граф. Постройте действительный список для этого графа.
6.5 Какие из следующих графов также являются деревьями?
Глава 7
7.1 Каков вес кратчайшего пути от начала до конца в каждом из следующих графов?
Глава 8
8.1 Вы работаете в фирме по производству мебели и поставляете мебель по всей стране. Коробки с мебелью размещаются в грузовике. Все коробки имеют разный размер, и вы стараетесь наиболее эффективно использовать доступное пространство. Как выбрать коробки для того, чтобы загрузка имела максимальную эффективность? Предложите жадную стратегию. Будет ли полученное решение оптимальным?
8.2 Вы едете в Европу, и у вас есть 7 дней на знакомство с достопримечательностями. Вы присваиваете каждой достопримечательности стоимость в баллах (насколько вы хотите ее увидеть) и оцениваете продолжительность поездки. Как обеспечить максимальную стоимость (увидеть все самое важное) во время поездки? Предложите жадную стратегию. Будет ли полученное решение оптимальным?
Для каждого из приведенных ниже алгоритмов укажите, является ли этот алгоритм жадным или нет.
8.3 Быстрая сортировка.
8.4 Поиск в ширину.
8.5 Алгоритм Дейкстры.
8.6 Почтальон должен доставить письма в 20 домов. Ему нужно найти кратчайший путь, проходящий через все 20 домов. Является ли эта задача NP-полной?
8.7 Имеется задача поиска максимальной
8.8 Вы рисуете карту США, на которой два соседних штата не могут быть окрашены в одинаковый цвет. Требуется найти минимальное количество цветов, при котором любые два соседних штата будут окрашены в разные цвета. Является ли эта задача NP-полной?
Глава 9
9.1 Предположим, к предметам добавился еще один: MP3-плеер. Он весит 1 фунт и стоит $1000. Стоит ли брать его?
9.2 Предположим, что вы собираетесь в турпоход. Емкость вашего рюкзака составляет 6 фунтов, и вы можете взять предметы из следующего списка. У каждого предмета имеется стоимость; чем она выше, тем важнее предмет:
• Вода, 3 фунта, 10
• Книга, 1 фунт, 3
• Еда, 2 фунта, 9
• Куртка, 2 фунта, 5
• Камера, 1 фунт, 6
Как выглядит оптимальный набор предметов для похода?
9.3 Нарисуйте и заполните таблицу для вычисления самой длинной общей подстроки между строками
Глава 10
10.1 В примере с Netflix сходство между двумя пользователями оценивалось по формуле расстояния. Но не все пользователи оценивают фильмы одинаково. Допустим, есть два пользователя, Йоги и Пинки, вкусы которых совпадают. Но Йоги ставит 5 баллов любому фильму, который ему понравился, а Пинки более разборчива и ставит «пятерки» только самым лучшим фильмам. Вроде бы вкусы одинаковые, но по метрике расстояния они не являются соседями. Как учесть различия в стратегиях выставления оценок?
10.2 Предположим, Netflix определяет группу «авторитетов». Скажем, Квентин Тарантино и Уэс Андерсон относятся к числу авторитетов Netflix, поэтому их оценки оказывают более сильное влияние, чем оценки рядовых пользователей. Как изменить систему рекомендаций, чтобы она учитывала повышенную ценность оценок авторитетов?
10.3 У сервиса Netflix миллионы пользователей. В приведенном ранее примере рекомендательная система строилась для пяти ближайших соседей. Пять — это слишком мало? Слишком много?