Вступительный экзамен в ШАД 2012

Условия задач

1. Даны 2012 гирек разной массы. Они разбиты на две группы (по 1006 в каждой), внутри которых упорядочены по массе. Предложите способ за 11 взвешиваний найти 1006-ую гирьку по массе среди всех.
2. Вычислите $\int_{0}^{2\pi}\sin^8 x dx$
3. Докажите, что многочлен с действительными коэффициентами, принимающий на действительной оси только положительные значения, может быть представлен в виде суммы квадратов многочленов с действительными коэффициентами.
4. Какую наибольшую дисперсию может иметь случайная величина, принимающая значения в отрезке от 0 до 1?
5. В множестве из n человек каждый может знать или не знать другого (если A знает B, отсюда не следует, что B знает A). Все знакомства заданы булевой матрицей n × n. В этом множестве может найтись или не найтись знаменитость — человек, который никого не знает, но которого знают все. Предложите алгоритм, который бы находил в множестве знаменитость или говорил, что ее в этом множестве нет. Сложность по времени — O(n), сложность по памяти — O(1).
6. Рассмотрим случайную перестановку на n элементах. Докажите, что данные k элементов окажутся в одном цикле с вероятностью 1/k
7. Есть неизвестная нам квадратичная форма Q в n-мерном пространстве. Разрешается задавать вопрос вида «Чему равно Q(v)?». Какое минимальное число вопросов надо задать, чтобы определить, является ли форма Q положительно определенной?

смотрите еще Контрольная работа от Яндекс, март 2015 г. и Задачи вступительных экзаменов