Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Andrey_hello
1 / 1 / 0
Регистрация: 15.01.2014
Сообщений: 15
1

Ответы к задачам из учебника "Кормен. Алгоритмы"

05.02.2015, 12:39. Просмотров 3693. Ответов 0
Метки нет (Все метки)

Раз нигде нет ответов для самоконтроля, предлагаю делиться своими вариантами решений задач здесь.

Задача 5.2-1 и 5.2-2 (Кормен, издание 2, 2005)
a) Вероятность того, что будет нанят один кандидат определится вероятностью нахождения только одного (лучшего) кандидата на первом месте, то есть http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{1}{n}, что равно числу перестановок оставшихся кандидатов на общее число перестановок: http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{(1-n)!}{n!}.

b) Вероятность того, что будет нанято ровно два кандидата равна ответу в пункте a), так как нам требуется лишь, чтобы нужную позицию занял только один кандидат, а именно с рангом (max - 1) - следующий за лучшим.

c) Вероятность того, что будет нанято n кандидатов (то есть все) равна http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{1}{n!}

с-2) Вероятность того, что будет нанято k кандидатов из n равна произведению вероятности того, что худший кандидат (из k лучших) будет на 1-м месте (что равно http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{1}{n}) на вероятность только одной перестановки (по возрастанию) среди оставшихся (k - 1) лучших кандидатов (что равно http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{1}{(k-1)!}). Итого: http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{1}{n}\frac{1}{(k-1)!}

Если в последнюю формулу подставлять вместо k количество из a), b), c) , то есть 1, 2, n для проверки, то результаты сходятся.

Добавлено через 6 часов 57 минут
Задача 5.2-3 (Кормен, издание 2, 2005)
Тут я не пойму при чём здесь индикаторные случайные величины - надо ещё в интернете покопаться.
А так получилось, что:
Вероятность выпадения одной грани кубика http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{1}{6},
математическое ожидание очков для одного кубика http://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{i=1}^{6}i\frac{1}{6}=\frac{21}{6}=3,5

Для n кубиков просто надо сложить n МО одного кубика = http://www.cyberforum.ru/cgi-bin/latex.cgi?3,5n

Добавлено через 14 минут
Задача 5.2-4 (Кормен, издание 2, 2005)

То же непонятно про индикаторные случайные величины.

В задаче получаются зависимые события.
Первый посетитель получит свою шапку с вероятностью http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{1}{n}.

Второй с вероятностью того, что его шапка осталась среди оставшихся - http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{n-1}{n} умножить на вероятность получения своей шапки из этих оставшихся - http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{1}{n-1}, итого: http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{n-1}{n}\frac{1}{n-1}=\frac{1}{n}

И так у всех оставшихся посетителей вероятность равна http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{1}{n}.

И математическое ожидание количества шапок для одного посетителя равно вероятности (так как значение события равно единице).

Математическое ожидание количества посетителе получивших свои шляпы равно сумме математических ожиданий для каждого посетителя = http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{1}{n}n=1

----------
Если заглянет кто - нибудь из знающих людей напишите, пожалуйста, правильно или не правильно.

Добавлено через 16 часов 23 минуты
Задача 5.2-5 (Кормен, издание 2, 2005)

Терзают меня сомнения, но всё же:

Количество возможных пар будет: http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{n(n-1)}{2}

Если можно считать (в этом моё сомнение), что вероятность для каждой пары быть инверсной независима от таких же вероятностей для остальных пар, то такую вероятность для одной пары можно принять равной 0,5.
МО числа инверсий определится как сумма вероятностей 0,5 от 1 до числа пар и будет равна:
http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{n(n-1)}{4}

-------
Посчитать через обычную формулу математического ожидания не удаётся, непонятно как её составить. Если составить в цифрах, то вроде как сходится результат.
Возьмём ряд из 3-х элементов

перестановка | количество инверсий
123 | 0
132 | 1
213 | 1
231 | 2
312 | 2
321 | 3
Вероятность каждой 1/6, значит МО инверсий получается
http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{1}{6}(1+1+2+2+3)=\frac{3}{2}
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.02.2015, 12:39
Ответы с готовыми решениями:

Есть ли ответы к упражнениям книги "Алгоритмы" автор С. Дасгупта?
Добрый день Скажите, где можно получить решения упражнений для книги "Алгоритмы" автор С....

Принципиальные алгоритмы игры "Тетрис"
Каковы принципиальные алгоритмы игры "Тетрис"? Это двумерный массив, который с определенной...

Алгоритмы из учебника
задача: допустим мы сравниваем сортировка ставками как 8*n^2 ходов, а сортировка слиянием как...

Поиск и вывод строки по заданному шаблону (с использованием симоволов "?", "*", "+")
Добрый день Имею такое задание: необходимо написать программу, которая сможет найти в файле...

Алгоритм роста "квадрата" или как работает "черный ящик"
Хочу спросить совета по нахождению формулы для "черного ящика", который на входе принимает 2...

0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.02.2015, 12:39

Из пункта "А" приехать в пункт "Б" и показать возможные траектории движения
Задача вот такая: надо из пункта "А" приехать в пункт "Б" и показать возможные траектории движения....

Критерии вхождения "шара" в "ящик"
Дано: Ящик (С параметрами: высота, длина, ширина), n шаров в этом ящике (С радиусами ri)....

Чем отличаются два понятия: "Абстрактный тип данных" и "Структура данных"?
Чем отличаются два понятия: "Абстрактный тип данных" и "Структура данных"?


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.