Билет с экзамена



Вступительный экзамен в Школу анализа данных.

Даны 2012 гирек разной массы. Они разбиты на две группы (по 1006 в каждой), внутри которых упорядочены по массе. Предлжите способ за 11 взвешиваний найти 1006-ую гирьку по массе среди всех.

2π

Вычислите r (sin x)8 dx.

0

Докажите, что многочлен с действительными коэффициентами, принимающий на действительной оси только положительные значения, может быть представ- лен в виде суммы квадратов многочленов с действительными коэффициентами.



Какую наибольшую дисперсию может иметь случайная величина, принимающая значения в отрезке от 0 до 1?

В множестве из n человек каждый может знать или не знать другого (если A знает B, отсюда не следует, что B знает A). Все знакомства заданы булевой матрицей n × n. В этом множестве может найтись или не найтись знаменитость

— человек, который никого не знает, но которого знают все. Предложите алго- ритм, который бы находил в множестве знаменитость или говорил, что ее в этом множестве нет. Сложность по времени — O(n), сложность по памяти — O(1).

Рассмотрим случайную перестановку на n элементах. Докажите, что данные k

k

элементов окажутся в одном цикле с вероятностью 1 .

Есть неизвестная нам квадратичная форма Q в n-мерном пространстве. Разре- шается задавать вопрос вида «Чему равно Q(v)?». Какое минимальное число вопросов надо задать, чтобы определить, является ли форма Q положительно определенной?








sitemap
sitemap