Здравствуйте. На выходных читал Stiven S. Skiena ADM, встретил несколько задач. Некоторые совершенно простые, но тем не менее попадались интересные.
Например задача 2-45. Вероятно правильный ответ , получается как частичная сумма гармонического ряда (вероятностей того, что текущий элемент будет меньше уже пройденных), однако с другой стороны, если сравнивать текущий элемент только с текущим минимумом можно получить , что вероятно не верно. Однако почему оно не верно и как это объяснить языком теории вероятности я не знаю.

Задача 2-43 интересная, но как решить её мне неизвестно. Вероятно нужно использовать некую функцию в которой присутствует n и k, хотя возникает вопрос, как при просмотре последнего элемента в исходном множестве, в том случае если в целевом множестве не будет хватать одного элемента вероятность может быть меньше 100%.
Если у вас есть идеи по поводу этих задач, было бы интересно послушать.

Вообще для задачи 2-43 я бы использовал метод Монте-Карло, это был бы идеальный вариант, но вероятно предполагается последовательный перебор элементов

tanglirЧто-то я 43 вообще не понял. Выбрать k элементов из множества в n элементов, чтобы вероятность выбора каждого была k/n? Так она и будет k/n, какие бы элементы мы ни выбрали...

Дано множество . Необходимо заполнить множество элементами из множества S. При этом вероятность того, что каждый элемент из S будет принадлежать подмножеству должна быть одинакова. Вы можете сделать только один проход по элементам множества S чтобы заполнить целевое подмножество.

Должно быть примерно следующее

Кроме того, скорее всего в так называемой probability function будет участвовать счётчик прохода и текущая наполненность множества S'.

tanglirSashaMercuryесли сравнивать текущий элемент только с текущим минимумом можно получить это как? текущий минимум ведь зависит от предыдущих элементов.

Понимаю что нужно выбирать из всех элементов до него. Потому и получается частичная сумма гармонического ряда, о чём я написал с самого начала. Но допустим я отброшу это, и скажу, что я просто буду сравнивать текущий минимум с текущим элементом, тогда вероятность будет 0.5. Если так делать нельзя, то как это объяснить нормальным языком теории вероятности

tanglirSashaMercuryПри этом вероятность того, что каждый элемент из S будет принадлежать подмножеству должна быть одинакова.Что тут подразумевается под "вероятностью"?

что у каждого элемента одинаковые шансы попасть в спасительную шлюпку S'

tanglir>тогда вероятность будет 0.5
В задаче же ни слова о динозаврах, да и вы, наверное, не блондинка - откуда же такие предположения?
>Если так делать нельзя, то как это объяснить нормальным языком теории вероятности
Зависимые/независимые события .
SashaMercuryчто у каждого элемента одинаковые шансы попасть в спасительную шлюпку S'То есть вся соль в "n is unknown". Тогда да, интересная задачка.

я не фанат теории вероятности, но знаю что над той блондинкой с динозавром смеяться не стоит. Это не предположения, а размышление об обосновании некорректности рассуждений, правильный ответ(на мой взгляд) я написал сразу

SashaMercury,

а если n известен ? Тут всё просто ?

tanglirSashaMercury, ну на объём используемой памяти ограничений же нет. Генерируем массив с нужным количеством различных случайных чисел (от 1 до n), потом в один проход... эээ... проходим по исходному множеству и выбираем элементы с соответствующими номерами.

ну а если сгенерируются одинаковые случайные числа ?

'массив с нужным количеством различных случайных чисел '
Как такое сделать ?

Dima TSashaMercuryну а если сгенерируются одинаковые случайные числа ?
игнорируй повторы

Тогда мне не нравится этот вариант. Какое-то 'грязное' решение. Неужели нет другого ?

Dima TSashaMercuryТогда мне не нравится этот вариант. Какое-то 'грязное' решение. Неужели нет другого ?
Насколько я знаю нет ГСЧ без повторов, рано или поздно повторы будут. Так что другого нет.

Изобретай наиболее оптимальный способ отлова повторов:
1. Биткарта. Работает быстро, но при большом диапазоне займет много места.
2. Заполняешь, сортируешь, в один проход проверяешь на повторы, заменяя повторы на новые случайные, затем снова сортируешь, проверяешь и т.д. пока проверка не покажет что повторов нет. Лишнего места не займет, но будут затраты на сортировку.

проход только один. Предполагается именно цикл по элементам, и какая-то функция, сомневаюсь что корректное решение такое

maytonПоскольку официальный язык форума - русский я настоятельно рекомендую
сейчас, и впредь использовать 2 варианта постановки задачи. А именно:

1) Оригинал на иностранном .
2) Русскоязычный перевод постановки топик-стартера приближённый
к оригиналу настолько насколько это возможно.

Игнорирование этого правила - я считаю лицемерием и попыткой показать
своё умственное превосходство над остальными.

Надеюсь мой посыл будет услышан.

Аргументация тут следующая, 1) английский тут совершенно не сложный, 2) любой IT-специалист должен знать английский язык на таком уровне, 3) и я уже как-то говорил о том, чем москвич отличается от деревни(мне она больше нравится, кстати), он не стесняется спросить как пройти на какую-нибудь Волхонку 20 или куда-нибудь ещё. Ну и в конце концов, если непонятно кому-то, пусть человек попросит, переведут. У нас в Сообществе(CPP, конечно), целый топик, где я задаю вопросы о том как перевести те или иные вещи из стандарта. ... 'лицемерием и попыткой показать своё...' вы знаете что это не так, Марк.

К следующим задачам(наиболее трудным для понимания) добавлю перевод, к этим смысла уже нет, одна совсем простая, а другую уже перевел выше

maytonНа том спасибо.
ну ладно вам. Лучше бы предложили какую идею :)

Интересно получается, для поиска минимума или максимума необходимо перебрать n элементов, а обновлять значение переменной в которой этот минимум хранится потребуется на порядок раз меньше. Например для 1.000.000.000.000 элементов потребуется в среднем 28 обновлений.

SashaMercuryИнтересно получается, для поиска минимума или максимума необходимо перебрать n элементов, а обновлять значение переменной в которой этот минимум хранится потребуется на порядок раз меньше. Например для 1.000.000.000.000 элементов потребуется в среднем 28 обновлений.

Интересно в том контексте, что от этой избыточности(если это можно так назвать) было бы здорово избавиться.

Dima TSashaMercuryТогда мне не нравится этот вариант. Какое-то 'грязное' решение. Неужели нет другого ?
Насколько я знаю нет ГСЧ без повторов, рано или поздно повторы будут. Так что другого нет.

Изобретай наиболее оптимальный способ отлова повторов:
1. Биткарта. Работает быстро, но при большом диапазоне займет много места.
2. Заполняешь, сортируешь, в один проход проверяешь на повторы, заменяя повторы на новые случайные, затем снова сортируешь, проверяешь и т.д. пока проверка не покажет что повторов нет. Лишнего места не займет, но будут затраты на сортировку.

Кстати, обладает ли такой алгоритм свойством конечность? Особенно при достаточно больших n и k ? Как долго он может выполняться ?


Судя по всему я нашёл решение данной задачи. Например алгоритм R




Добавлю свой перевод обоснования из w.
Согласно алгоритму первоначально необходимо заполнить целевой массив R мощностью k первыми k элементами множества S. Следом необходимо перебрать оставшиеся в S элементы, до тех пор пока они не закончатся. На каждой итерации последнего перебора для каждого элемента s[i] алгоритм генерирует случайное число j из диапазона [1,i]. Если j<=k, то происходит присваивание r[j]<-s[i]. В действительности, на каждой итерации вероятность того, что будет выбран элемент для целевого множества (всего элементов i, хороших k, потому собственно и получаем, прим. пер.). Вероятность того что будет произведена перезапись конкретного элемента j из целевого множества R . Для того чтобы доказать что после окончания алгоритма каждый элемент S имел возможность попасть в целевое множество воспользуемся индукцией. После итерации i-1 вероятность того, что будет выбран элемент для целевого множества. Так как вероятность того что данный элемент будет перезаписан на следующей итерации , вероятность того что он не будет перезаписан на следующей итерации равна.Таким образом, вероятность того что любой элемент из множества S будет присутствовать в целевом множестве после итерации i определяется как произведение двух событий: элемент будет присутствовать в целевом множестве после предыдущей итерации, и не будет перезаписан (будет сохранён) на итерации i. Имеем . Значит результат справедлив для i, и следовательно справедлив по индукции.

Dimitry SibiryakovВообще-то для большого, но известного n, выборка k значений (где k<<n) делается гораздо проще, без сортировки и за k итераций.

Это совсем другая задача

Dima TSashaMercuryпропущено...


Кстати, обладает ли такой алгоритм свойством конечность? Особенно при достаточно больших n и k ? Как долго он может выполняться ?
Теорию вероятностей помню смутно, поэтому формулами не буду умничать, но при k значительно меньше n вероятность выпадения повтора небольшая, т.е. повторные проходы если и будут, то 1-3, не больше.
Самая тяжелая сортировка - первая, т.к. последующие (если будут) сортируют почти отсортированный массив.

Допустим у нас 10 чисел, нам нужно выбрать три. Как долго мы будем случайно выбирать числа прежде чем у нас будет три уникальных ? А если числе 10^12 а уникальных нужно 10^12 - 1. Можем ли мы утверждать что если мы просто будем пропускать повторы мы за обозримый период времени получим множество уникальных чисел ?

Dima TSashaMercury Допустим у нас 10 чисел, нам нужно выбрать три. Как долго мы будем случайно выбирать числа прежде чем у нас будет три уникальных ?
Исходим из того что ГСЧ выдает числа с равной вероятностью.
Как с помощью теории вероятности посчитать не знаю, делаем проще. Тест


Результат5,10,1,1,9,6,6,7,6,9,7,4,3,5,7,5,5,10,2,8,9,9,1,5,10,7,8,4,4,5
в худшем случае 3 прохода для последовательности 5,7,5,5,10



где гарантия того что в следующий раз не потребуется 10 проходов ?

Dima TSashaMercuryгде гарантия того что в следующий раз не потребуется 10 проходов ?
Нужны гарантии: берешь и гоняешь алгоритм в цикле, собирая статистику.

Тогда мы говорим о статистике. Ни о чём более.

SS
Судя по всему я нашёл решение данной задачи. Например алгоритм R




Добавлю свой перевод обоснования из w.
Согласно алгоритму первоначально необходимо заполнить целевой массив R мощностью k первыми k элементами множества S. Следом необходимо перебрать оставшиеся в S элементы, до тех пор пока они не закончатся. На каждой итерации последнего перебора для каждого элемента s[i] алгоритм генерирует случайное число j из диапазона [1,i]. Если j<=k, то происходит присваивание r[j]<-s[i]. В действительности, на каждой итерации вероятность того, что будет выбран элемент для целевого множества (всего элементов i, хороших k, потому собственно и получаем, прим. пер.). Вероятность того что будет произведена перезапись конкретного элемента j из целевого множества R . Для того чтобы доказать что после окончания алгоритма каждый элемент S имел возможность попасть в целевое множество воспользуемся индукцией. После итерации i-1 вероятность того, что будет выбран элемент для целевого множества. Так как вероятность того что данный элемент будет перезаписан на следующей итерации , вероятность того что он не будет перезаписан на следующей итерации равна.Таким образом, вероятность того что любой элемент из множества S будет присутствовать в целевом множестве после итерации i определяется как произведение двух событий: элемент будет присутствовать в целевом множестве после предыдущей итерации, и не будет перезаписан (будет сохранён) на итерации i. Имеем . Значит результат справедлив для i, и следовательно справедлив по индукции.

Сразу не стал писать, но вот что меня смутило. В доказательстве чётко выделены события которые приведут к тому, что после i итерации элемент будет в целевом массив. Однако к таким событиям почему-то не отнесли вероятность того что конкретный элемент появится в целевом массиве именно на i итерации. Непонятно почему это не оговаривается.

Здравствуйте.
Решал на днях несколько задач. По трём из них у меня возникли некоторые вопросы. Возможно у кого-то будут соображения.

Перевод.
Первая задача не требует перевода, добавлю перевод 2 и 3:
4 -29
Некий Мистер Дал утверждает что разработал новую структуру данных типа очередь с приоритетом. Данная структура поддерживает операции Insert, Maximum, Extract Maximum, каждая из этих операций имеет асимптотику О(1). Докажите что он ошибается. (Подсказка: .... используйте тот факт что время исполнения сортировки

4 -30
БД содержит 10^4 записей в отсортированном порядке. 60% записей используются часто, остальные 40% редко. Предлагается два варианта организации БД:
1. Использовать одномерный массив и бинарный поиск
2. Создать два массива, в первом будет 60% записей(к ним обращение будет чаще всего), во втором остальные 40. Сначала ищем в первом, если не нашли, идём во второй. Бинарный поиск в каждом из массивов.

Какой подход лучше? Какой подход лучше если в обоих случаях использовать неотсортированный массив и линейный поиск ?


Мои соображения.
По задаче 3-28 вопросов практически нет, её можно решить следующим образом:



Q1) Может быть есть опечатки, но тут всё понятно. Вопрос такой: можно ли решить данную задачу иначе за линейное время(без использования деления) ?

Q2) Со второй задачей сложнее. Очевидным был бы следующий ответ: Так как Extract Maximum выполняется за O(1) то в таком случае сортировка возможна за O(n). Но 1. Зачем остальные части условия ? 2. Разве существует доказательство того что сортировка не может быть реализована за O(n) ?
Следовательно рассуждаю я скорее всего неверно(при решении данной задачи). Есть ли у вас какие-то идеи ?

Q3) Решение третьей задачи кажется совсем простым. В первом случае нужно задать такой вопрос, что лучше, log(n) или 2log(n) ? Конечно лучше хранить всё в одномерном упорядоченном массиве и использовать двоичный поиск.
Теперь пусть массивы будут неупорядоченны, и поиск будет линейный. В таком случае лучше разделить массив на два массива, и сначала осуществить поиск в первом массиве, а затем во втором. Но дело в том, что все рассуждения выше, как вы понимаете, относятся только к операции Search. Как провести комплексное рассуждение и сравнение я не знаю. Подскажите пожалуйста

White Owl
SSБД содержит 10^4 записей в отсортированном порядке. 60% записей используются часто, остальные 40% редко.

Ну как же вы так? Ай-ай-ай! В нашей профессии английский надо знать как родной.
"10К имен, из которых 40% известны как "хорошие клиенты" и кто совместно генерирует 60% запросов к базе"

Моё перевод упрощён, но корректен.
Дословный перевод будет такой:
База данных содержит 10^4 отсортированных имён. (Далее идём of whom, значит 'которых') 40% известны как хорошие клиенты(имена и клиенты в данном случае синонимы) и на них совместно приходится 60% запросов к базе данных. И т.д.