Вступительный экзамен в ШАД 2013
Условия задач
Вариант 1
- Найдите
- Дана матрица
размера
x
, где
,
. Найдите ранг матрицы
.
- Имеется множество
{
}. Найдите размер максимального по мощности подмножества
, такого, что
не содержит элементов
, таких, что
.
- На окружности случайно выбирается
точек. Найдите вероятность того, что все они принадлежат некоторой полуокружности.
- Назовем двумерный массив действительных чисел
возрастающим, если для любых
,
. Задача поиска в квадратном возрастающем массиве формулируется так: для заданного возрастающего массива
и некоторого числа
определить, встречается ли число
в массиве
. Покажите, что не существует алгоритма, решающего эту задачу менее чем за
сравнений.
- У линейного преобразования
-мерного пространства существует
собственных векторов, таких, что любые
из них линейно независимы. Найдите всевозможные матрицы, которые могли бы задавать такое преобразование.
- Найдите сумму ряда
, где
-количество единиц в двоичном представлении числа
.
Вариант 2
- Последовательность {
}
определена рекурсивно
,
. Найдите формулу общего члена последовательности.
- Дано множество
{
}. Среди всех его подмножеств равновероятно выбирается
его подмножеств. Найдите вероятность того, что
- Дан массив длины
из нулей и единиц. Найдите в нем подмассив максимальной длины, в котором количество единиц равно количеству нулей. Ограничения:
по времени,
по дополнительной памяти.
- Пусть
. Для каких
?
- Дан неориентированный граф
без петель. Пронумеруем все его вершины. Матрица смежности графа
с конечным числом вершин
(пронумерованных числами от 1 до
) - это квадратная матрица
размера
, в которой значение элемента
равно числу ребер из
-ой вершины графа в
-ю вершину. Докажите, что матрица
имеет отрицательное собственное значение.
- Рассмотрим бесконечный двумерный массив {
}
, состоящий из натуральных чисел, причем каждое число встречается в массиве ровно 8 раз. Докажите, что
.
- Дана матрица из нулей и единиц, причем для каждой строки матрицы верно следующее: если в строке есть единицы, то они все идут подряд (неразрывной группой из единиц). Докажите, что определитель такой матрицы может быть равен только
или
.
смотрите еще Вступительные в ШАД 2012 и Контрольная работа от Яндекс, март 2015 г. и Задачи вступительных экзаменов