Полный разбор экзамена ШАД-2019

    Привет! Меня зовут Азат, я студент 3 курса Факультета Компьютерных Наук ВШЭ. На днях ко мне обратился знакомый с Экономики ВШЭ и попросил помочь с решением задач вступительного экзамена в ШАД. Мы с однокурсником Даниилом посмотрели на задания, они показались нам довольно сложными, но очень интересными, захотелось поломать над ними голову. В итоге мы прорешали 1 из вариантов 2019 года и хотим показать наши решения миру.



    Задача 1


    Заполните третий столбец матрицы

    $ \frac{1}{6} \left( \begin{array}{ccc} 5&-2&?\\-2&2&?\\-1&-2&? \end{array} \right) $


    если известно, что это матрица ортогональной проекции на некоторую плоскость.

    Решение
    Назовём эту матрицу $A$, воспользуемся свойством ортогональных проекторов:
    $A^2=A$ и займёмся арифметикой:

    $ A^2 = \frac{1}{36} \left( \begin{array}{ccc} 5&-2&x\\-2&2&y\\-1&-2&z \end{array} \right) \left( \begin{array}{ccc} 5&-2&x\\-2&2&y\\-1&-2&z \end{array} \right) = \frac{1}{36} \left( \begin{array}{ccc} 29-x & * & * \\ -14-y & * & * \\ -1 - z & * & * \end{array} \right) $


    $ = \frac{1}{6} \left( \begin{array}{ccc} 5&-2&x\\-2&2&y\\-1&-2&z \end{array} \right) = A $



    Нам необязательно считать 2 и 3 столбец, информации в первом достаточно для решения, на экзамене так можно было бы сэкономить время.

    Получаем тривиальную систему:

    $ \left\{ \begin{array}{l} 29-x = 5 \cdot 6 \\ -14-y = -2 \cdot 6 \\ -1-z = -1 \cdot 6 \end{array} \right. \Leftrightarrow \left\{ \begin{array}{l} 29 - x=30 \\ -14 -y = -12 \\ -1-z = -6 \end{array} \right. \Leftrightarrow \left\{ \begin{array}{l} x = -1 \\ y=-2 \\ z = 5 \end{array} \right. $



    Таким образом, мы заполнили 3 столбец, получив в итоге матрицу

    $ A = \frac{1}{6} \left( \begin{array}{ccc} 5&-2&-1\\-2&2&-2\\-1&-2&5 \end{array} \right) $




    Задача 2


    Что вы можете сказать о сходимости (абсолютной или условной) ряда $\sum_{n=1}^{\infty} (n+2019)a_n$, если известно, что ряд $\sum_{n=1}^{\infty} (n-2019)a_n$ сходится (а) абсолютно, (б) условно?

    Решение
    Введём обозначения:

    $ S = \sum_{n=1}^{\infty} (n+2019)a_n, T = \sum_{n=1}^{\infty} (n-2019)a_n. $


    $ S' = \sum_{n=1}^{\infty} |n+2019| |a_n|, \; T' = \sum_{n=1}^{\infty} |n-2019| |a_n| $


    $ A = \sum_{n=1}^{\infty} a_n, \; A' = \sum_{n=1}^{\infty} |a_n| $



    Докажем вспомогательное утверждение (1).

    Ряд $\sum_{n=1}^{\infty}(n + a)a_{n}$ сходится $\Rightarrow A' = \sum_{n=1}^{\infty}a_{n}$ сходится $\forall a \in \mathbb{Z}$.

    Для этого представим второй ряд как $\sum_{n=1}^{\infty} \frac{(n+a)a_{n}}{n+a} $ (кроме, может быть, выколотой точки -a).

    Заметим, что ряд можно представь как $ \sum_{n=1}^\infty \alpha_n \beta_n $, где $ \alpha_n = \frac{1}{n+a}, \beta_n =(n + a)a_n$. Отбросим члены до $n = max(1, -a + 1) $, это не повлияет на сходимость. Тогда выполнены все условия признака Дирихле сходимости ряда. А именно:

    1. Последовательность частичных сумм $ B_n = \sum_{k=1}^n \beta_k $ ограничена, так как ряд $ \sum_{n=1}^\infty \beta_n $ сходится.
    2. $ \alpha_n \geqslant \alpha_{n+1} $
    3. $ \lim_{n\to\infty} \alpha_n = 0 $

    Значит, ряд сходится. Хорошо, теперь приступим к заданию.

    a) T сходится абсолютно, то есть ряд $T' = \sum_{n=1}^{\infty} |n - 2019| |a_n| $ сходится. Разобьём эту сумму:

    $ T' = \sum_{n=1}^{2018} |n - 2019| |a_n| + \sum_{n=2019}^{\infty} |n-2019| |a_n| = \ldots $


    Мы можем без влияния на сходимость заменить первые $ 2018 $ элементов, тогда получим:

    $ \ldots = \sum_{n=1}^{2018} (n - 2019) |a_n| + \sum_{n=2019}^{\infty} (n-2019) |a_n| = \sum_{n=1}^{\infty} (n - 2019) |a_n| $


    Отсюда, пользуясь утверждением (1), получаем что $ \sum_{n=1}^{\infty} |a_n| $ сходится.

    Выкинем первые $ 2018 $ членов каждого из этих рядов (опять же, это не влияет на их сходимость) и рассмотрим разность:

    $ S'-T' = \sum_{n=2019}^{\infty} ((n+2019) - (n-2019))|a_n| = 4038 \sum_{n=2019}^{\infty} |a_n| $


    А мы уже знаем, что ряд $ A' = \sum_{n=1}^{\infty} |a_n| $ сходится. Тогда получается, что ряд $ S' = T'+A' $ — это сумма 2 сходящихся рядов. Ну значит и он сам сходящийся.

    б) $ T $ сходится условно, то есть ряд $ T $ сходится, а ряд $ T' $ — нет.

    Докажем, что тогда ряд $ S $ тогда тоже сходится условно.

    Опять же, из сходимости ряда $ T $ с помощью утверждения (1) следует сходимость ряда $ A $. Из тех же соображений о разности, что и в предыдущем пункте, применённых теперь к $ S $ и $ T $, получим, что ряд $ S $ сходится. Осталось лишь доказать, что ряд $ S' $ не сходится.

    Будем действовать от противного. Пусть $ S' $ сходится. Тогда, отбросив первые $ 2018 $ членов $ S' $ и $ T' $, поймём, что:

    $ \sum_{n=2019}^{\infty} |n-2019||a_n| \leq \sum_{n=2019}^{\infty} |n+2019||a_n| $


    так как $ |n+2019| \geq |n-2019| \; \forall n \geq 2019 $.

    Но эти ряды положительные, поэтому если сходится больший из них, то сходится и меньший. Значит $ T' $ сходится, противоречие.

    Задача 3


    Алёна очень любит алгебру. Каждый день, заходя на свой любимый алгебраический форум, она с вероятностью $\frac14$ находит там новую интересную задачу про группы, а с вероятностью $\frac{1}{10}$ интересную задачку про кольца. С вероятностью $\frac{13}{20}$ новых задач на форуме не окажется. Пусть $X$ — это минимальное число дней, за которые у Алёны появится хотя бы одна новая задача про группы и хотя бы одна про кольца. Найдите распределение случайной величины $X$. В ответе должны участвовать только компактные выражения (не содержащие знаков суммирования, многоточий и пр.).

    Решение
    Нам нужно найти $ P[X = k] $. Для этого надо понять на пальцах, в каком случае $ X = k $. Первый случай — когда в каждый из предыдущих $ k - 1 $ дней либо не было задач, либо были только про группы, а в $k$-ый попалась задача про кольца. Второй случай — когда в каждый из предыдущих $ k - 1 $ дней либо не было задач, либо были только про кольца, а в $k$-ый попалась задача про группы. На самом деле мы оба раза учли не подходящий случай, когда все предыдущие $k-1$ дней задач не было вообще. С поправкой на это ответ будет таким:

    $ P[x=k] = \left( \left( \frac{13}{20} + \frac{1}{4} \right)^{k-1} - \left( \frac{13}{20} \right)^{k-1}\right) \cdot \frac{1}{10} + $


    $ \left( \left( \frac{13}{20} + \frac{1}{10} \right)^{k-1} - \left( \frac{13}{20} \right)^{k-1}\right) \cdot \frac{1}{4} $



    Задача 4


    Дан массив $ \text{A[1:n]}$ вещественных чисел, отсортированный по возрастанию, а также числа $p$, $q$, $r$. Предложите алгоритм, строящий массив $\text{B[1:n]}$, состоящий из чисел $px^2 + qx + r$, где $x \in \text{A}$, также отсортированный по возрастанию. Ограничение по времени — $O(n)$, по дополнительной памяти — $O(n)$.

    Решение
    $ A = [x_1, \ldots, x_n] $, $ x_1 \leq \ldots \leq x_n $.

    Сначала предположим, что $ p > 0 $.

    Изобразим нашу функцию.



    Заметим, что:

    1. $ \forall x: x > -\frac{q}{2p} $ после применения $ f(x) $ порядок остаётся прежним.
    2. $ \forall x: x \leq -\frac{q}{2p} $ после применения $ f(x) $ порядок будет обратным.

    То есть для «правой» части после применения к каждому значению функции $f$ подпоследовательность остаётся правильно отсортированной, для левой части она становится отсортированной в обратном порядке.

    Тогда бинпоиском за $ O(\log{n}) $ найдём место в $ A $, в котором массив делится на эти самые доли. Сделаем reverse левой части. Применим ко всем элементам функцию $ f $. Получили 2 отсортированных массива. С помощью процедуры merge за $ O(n) $ по времени и по памяти получим целиком отсортированный массив.

    В случае $ p < 0 $ решим задачу для $ -f $, а затем сделаем reverse всего массива и домножим каждое значение $ f(x) $ на -1. Получим правильный результат.

    В случае $ p = 0 $ порядок зависит от знака $ q $.

    1. $ q > 0 \Rightarrow f(x_i) \leq f(x_{i+1}) \, \forall i $
    2. $ q < 0 \Rightarrow f(x_i) \geq f(x_{i+1}) \, \forall i $

    И построение в этом случае сводится к применению функции ко всем значениям. Только в случае $ q < 0 $ за $ O(n) $ надо ещё сделать reverse. В случае когда $ q \geq 0 $ порядок уже правильный.

    Задача 5


    Вещественнозначная функция $ f $ определена на отрезке $ [a;b] $ $ (b-a \geqslant 4) $ и дифференцируема на нём. Докажите, что найдётся точка $ x_0 \in (a;b) $, для которой

    $ f'(x_0) < 1 + f^2(x_0). $



    Решение
    Давайте докажем от противного. Пусть $ \forall x \in (a; b): f'(x) \geq 1 + f^2(x) $.

    Сначала посмотрим, что будет происходить при равенстве:

    $ f'(x) = 1 + f^2(x) $


    $ \frac{df}{dx} = 1 + f^2 \Leftrightarrow \int \frac{df}{1+f^2} = \int dx $


    $ arctg(f) = x + C \Rightarrow f(x) = tg(x+C) $



    Обозначим эту функцию как $ g(x) = tg(x+C) $. Заметим, что $ f'(x) \geq g'(x) \; \forall x \in (a; b) \Rightarrow f(x) - f(a) \geq g(x) - g(a) \; \forall x \in (a; b) $. То есть мы пользуемся тем, что функция $ f $ растёт не менее быстро, получаем, что и разница с изначальной точкой будет не меньше, чем у $ g $.

    Функция $ g $ у нас имеет константу $ C $. Примем значение этой константы таким, что $ g(a) = f(a) $. Тогда:

    $ f(x) - f(a) \geq g(x) - g(a) \Leftrightarrow f(x) \geq g(x) $



    Мы знаем, что $ b - a \geq 4 $. Тогда на $ (a; b) $ существует хотя бы одна точка $ x' $ такая, что $ x'+C = \frac{\pi}{2} + \pi k $ (потому что шаг $ \pi < 4 $). В этой точке $ g(x') = +\infty $. При этом мы знаем, что $ f(x') \geq g(x') \Rightarrow f(x') = +\infty $.

    Получили, что в какой-то из точек $ (a; b) $ функция уходит на бесконечность. А значит функция терпит разрыв, то есть не является непрерывной, а это дано нам в условии. Получили противоречие.

    Задача 6


    Квадратная вещественная матрица $ A $ такова, что $ A^\text{T} = p(A) $, где $ p(x) $ — многочлен с ненулевым свободным членом. Докажите, что $ A $ обратима. Верно ли, что для любого оператора $ \varphi : \mathbb{R}^n \to \mathbb{R}^n $ найдётся многочлен $ p(x) $ и некоторый базис, в котором матрица $ \varphi $ удовлетворяет условию $A^\text{T} = p(A)$?

    Решение
    В начале, покажем, что $ A = p(A^T) $, распишем подробно:

    $ A = (A^T)^T = (p(A))^T = (p_n A^n + \ldots + p_1 A + p_0 E)^T $


    $ = (p_n (A^n)^T + \ldots + A^T + p_0 E) = (p_n (A^T)^n + \ldots + A^T + p_0 E) = p(A^T) $



    Отсюда можно получить, что $ A = p(A^T) = p(p(A)) $.

    1. Будем доказывать от противного. Пусть матрица $ A $ необратима. Тогда существует вектор $ x \neq 0 $ такой, что $ Ax = 0 $. Тогда ещё можно сказать, что $ x^T Ax = 0 $. Теперь распишем это:

    $ 0 = x^T A x = x^T p(A^T) x = x^T (p_n (A^T)^n + \ldots + p_1 A^T + p_0 E ) x $


    $ = p_n (x^T A^T) (A^T)^{n-1} x + \ldots + p_1 x^T A^T x + p_0 x^T E x $


    Теперь пользуемся тем, что $ x^T A^T = (Ax)^T = 0 $:

    $ 0 = \ldots = p_0 x^T x = p_0 \| x \| $


    Но мы знаем, что $p_0 \neq 0 \Rightarrow \| x \| = 0 \Rightarrow x = 0 $. Получили противоречие.

    2. Рассмотрим линейный оператор $ \phi $ с матрицей $ A = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} $ в стандартном базисе.

    Тогда в любом другом базисе матрица будет иметь вид $ B = C^{-1} A C $, где $ C $ — матрица перехода.

    Заметим, что $ A^2 = 0 $, значит $ A^n = 0 \; \forall n \geq 2 $. Тогда $ B^n = C^{-1} A^n C = 0 \; \forall n \geq 2 $.

    Пусть $ B^T = p(B) $. Так как все степени выше 1 обнуляются, $ B^T = \alpha B + \beta E $.

    При этом $ \beta = 0 $, так как иначе, пользуясь первым пунктом, можем получить, что матрица $ B $ обратима, а это не так (т.к. $ \operatorname{det} B = \operatorname{det} A = 0 $).

    Вспомним, что $ B = p(B^T) = p(p(B)) $.

    Распишем: $ B = \alpha (\alpha B) = \alpha^2 B \Rightarrow (1-\alpha^2) B = 0 $.

    Теперь рассмотрим несколько случаев:

    1. $ \alpha = -1 $:

    Подставим в другое место:

    $ B^T = p(B) = -B \Rightarrow B + B^T = 0 $



    Наша матрица размерности всего 2, поэтому вполне можем расписать поэлементно:

    $ \left\{ \begin{array}{l} b_{11} + b_{11} = 0 \\ b_{12} + b_{21} = 0 \\ b_{21} + b_{12} = 0 \\ b_{22} + b_{22} = 0 \end{array} \right. \Rightarrow \left\{ \begin{array}{l} b_{11} = b_{22} = 0 \\ b_{12} = -b_{21} \\ \end{array} \right. $



    Но мы знаем что $ \operatorname{det} B = \operatorname{det} A = 0 $. Распишем определитель:

    $ \operatorname{det} B = 0 \cdot 0 - b_{12}(-b_{12}) = b_{12}^2 = 0 \Rightarrow b_{12} = b_{21} = 0 \Rightarrow B = 0 $

    .
    Получили противоречие. Матрица оператора $ \phi $ в стандартном базисе ненулевая, она не может быть нулевой в другом базисе.

    2. $ \alpha = 1 $:

    Тогда после подстановки получаем $ B^T = p(B) = B $. Тогда $ B^T B = B^2 = 0 $.

    При этом

    $ (B^T B)_{ii} = \sum_{k=1}^n (B_{ki})^2 = 0 \; \forall i \Rightarrow B_{ki} = 0 \; \forall k, i \Rightarrow B = 0 $


    И снова получаем противоречие.

    3. $ \alpha \neq \pm 1$.

    Здесь тогда тоже получаем, что $ (1-\alpha)^2 B = 0 \Rightarrow B = 0 $.

    Значит нет многочлена и базиса в котором матрица $ A $ оператора $ \phi $ представима, как $ A^T = p(A) $. Что и требовалось доказать.

    Задача 7


    Дан граф с $ 30 $ вершинами. Известно, что для любых $ 5 $ вершин в графе есть цикл длины $ 5 $, содержащий эти вершины. Докажите, что найдётся $ 10 $ вершин, попарно соединённых рёбрами друг с другом.

    Решение
    Сначала покажем, что диаметр графа $ \operatorname{diam} G \leq 2 $.

    Выберем 2 самые удалённые друг от друга вершины $ u $ и $ v $ и 3 произвольные. По условию дано, что любые 5 вершин составляют цикл. Значит есть и цикл, состоящий из этих 5 вершин. В этом цикле путь от $ u $ до $ v $ будет максимум 2 (видно на картинке). Значит $ \operatorname{diam} G \leq 2 $.



    Теперь зафиксируем произвольную вершину $ v \in G $. Мы уже сделали вывод, что до любой другой вершины графа расстояние от $ v $ равно либо 1, либо 2. Покажем, что на «‎втором уровне»‎ не больше $ 2 $ вершин:



    Будем доказывать от противного. Пусть есть вершины $ a, b, c \in L_2 $. Возьмём ещё одну произвольную вершину $ x \in G $. Снова, эти вершины составляют цикл. Но тогда, как бы мы ни разместили вершины в этом цикле, расстояние от $ v $ до хотя бы одной из вершин $ a $, $ b $ или $ c $ будет равно 1, получили противоречие.



    Получили, $ |L_2| \leq 2 \Rightarrow |L_1| \geq 30 - 1 - 2 = 27 $, то есть каждая вершина имеет степень не меньше $ 27 $.

    Теперь попробуем с этой информацией найти клику (вершины, попарно соединённые рёбрами — то, что требуется в условии) длины 10. Найти клику размера 10 в графе $ G $ — это то же самое, что найти независимое множество (то есть вершины, между которыми вообще нет рёбер) того же размера 10 в обратном графе $ \overline{G} $.

    Рассмотрим $ \overline{G} $. Если в изначальном графе $ G $ у нас степень вершины $ v $ $ \operatorname{deg}v \geq 27 \; \forall v \in G $, то в обратном $ \operatorname{deg}\overline{v} \leq 2 \; \forall \overline{v} \in \overline{G}$.

    Тогда обратный граф состоит из набора «цепей» (1) и «циклов» (2). Другие структуры невозможны из-за жёсткого ограничения $ \operatorname{deg} \overline{v} \leq 2 $.



    В компонентах вида (1) можно найти независимое множество размера $ \left \lceil{\frac{m}{2}}\right \rceil $, вида (2) — $ \left \lfloor{\frac{m}{2}}\right \rfloor $.

    Пусть $ k $ — общее количество компонент в обратном графе, а $ k_1 $ — количество «цепочек». Тогда размер максимального независимого множества будет равен:

    $ | I | = \sum_{i=1}^{k_1} \left \lceil{\frac{m_i}{2}}\right \rceil + \sum_{i=k_1 + 1}^{k} \left \lfloor{\frac{m_i}{2}}\right \rfloor \text{при условии} \sum_{i=1}^{k} m_i = 30 $



    Понятно, что это число будет минимальным, если мы по возможности будем округлять вниз, при этом с наибольшими потерями. Этого можно добиться, например, взяв 10 компонент размера 3. Тогда получим нижнюю оценку.

    $ | I | \geq \sum_{i=1}^{10} \left \lfloor{\frac{3}{2}}\right \rfloor = 10 $



    То есть мы показали, что в обратном графе $ \overline{G} $ максимальное независимое множество имеет размер 10 или больше, то есть в графе $ G $ существует клика размера 10 или больше. Что и требовалось доказать.

    Задача 8


    Найдите предел

    $ \lim_{n \to \infty} \sum_{k=n}^{5n} C_{k-1}^{n-1} \left( \frac15 \right)^n \left( \frac45 \right)^{k-n}. $



    Решение
    Здесь нужно по виду формулы догадаться о теории вероятностей.

    Введём случайную величину:

    $ \xi_{n} = \# \text{бросков монетки до выпадания} \; n \, \text{орлов} $


    Пусть монетка неправильная — орёл выпадает с вероятностью $ \frac{1}{5} $.

    Тогда $ P[\xi_n = k] $ это в точности значение под знаком суммирования:

    $ P[\xi_n = k] = C_{k-1}^{n-1} \left( \frac15 \right)^n \left( \frac45 \right)^{k-n} $



    $ C_{k-1}^{n-1} $ — это количество возможных размещений $ n - 1 $ орлов (ещё 1 выпадает в конце).
    $ \left( \frac{1}{5} \right)^n $ — это вероятность выпадения орлов на выбранных позициях.
    $ \left( \frac{4}{5} \right)^{k-n} $ — это вероятность выпадения решек на оставшихся позициях.

    Тогда наш предел превращается в

    $ \lim_{n \to \infty} P[\xi_n \leq 5n]. $


    Заметим, что вероятность события $ \xi_n \leq 5n $ можно интерпретировать по-другому. Это вероятность того, что за $ 5n $ бросков выпадет $ \geq n $ орлов.

    Введём новую случайную величину:

    $ S_{5n} = \# \text{орлов после} \, 5n \, \text{подбрасываний} $


    При этом величину можно представить как сумму элементарных:

    $ S_{5n} = \sum_{i=1}^{5n} \eta_i, \eta_i = I\{\text{в} \, i \, \text{бросок выпал орёл} \} $


    Тогда

    $ \mathbb{E} S_{5n} = \sum_{i=1}^{5n} \mathbb{E} \eta_i = 5n \cdot \frac15 = n $


    Применим центральную предельную теорему к $ S_{5n} $. Получим:

    $ \lim_{n \to \infty} P[\xi_n \leq 5n] = \lim_{n \to \infty} P[S_{5n} \geq n] = \lim_{n \to \infty} P[S_{5n} - n \geq 0] = $


    $ \lim_{n \to \infty} P[\frac{S_{5n} - n}{\sigma\sqrt{n}} \geq 0] = P[\eta \geq 0], \eta \sim N(0, 1) $



    Вспоминаем, что у нас нормальное распределение симметрично относительно матожидания и получаем итоговый ответ:

    $ \lim_{n \to \infty} P[\xi_n \leq 5n] = P[\eta \geq 0] = \frac12 $




    Заключение


    В целом экзамен довольно сложный. Мой знакомый пожаловался, что подготовиться непросто. Это действительно так — нужно не только знать обширную математическую теорию, но и иметь навык решения олимпиадных задачек, в ШАДе дают именно такие. Поэтому для подготовки нужно много тренироваться, вспоминать теорию и набивать руку.

    Если у вас есть другие идеи решения задач или какие-то замечания, смело пишите мне в телеграм @Azatik1000. Всегда рад ответить!

    Азат Калмыков, куратор в «ШАД Helper»

    Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

    Какое задание показалось вам наиболее интересным?

    • 12,5%13
    • 8,3%22
    • 8,3%32
    • 8,3%42
    • 8,3%52
    • 16,7%64
    • 45,8%711
    • 45,8%811
    Реклама
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее

    Комментарии 21

    • НЛО прилетело и опубликовало эту надпись здесь
        0

        "Задачи нацелены на конкретную группу людей (студентов 2-4 курсов)"
        Да, допустим. И что?


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

          0
          «получать мало» — это сколько?
          0
          Кто-то знает курсы к этому экзамену? Как я понимаю, университетской базы будет явно недостаточно.
            0
            Насколько я понимаю, автор вместе с другими олимпиадниками и создает такой
              0
              ШАД Helper называется если что
                0
                Это классические задачи по матанализу и линейной алгебре 1-4 курсы любого технического вуза.
                • НЛО прилетело и опубликовало эту надпись здесь
                    +1

                    Действительно, зачем в школе анализа данных мат анализ?
                    /s

                    • НЛО прилетело и опубликовало эту надпись здесь
                        0

                        Ненуачо, а программисты в вашем представлении не должны и представлять как работают компиляторы?
                        АД — все-таки следствие математики, и какие-то вещи знать стоит.

                          +2

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

                            0
                            Есть много вещей которые «стоит знать». Если посмотреть на программу ШАДа, то многие темы выходят за пределы математики и касаются прикладных областей. Да

                            Тут скорее вопрос в том, что >50% экзамена построена вокруг школьного теорвера и матана/линейнки 2 курса.

                            Если этот экзамен рассчитан на целевую аудиторию студентов 2-5 курсов, то вопросы кажутся резонными (матан/линейка/теорвер — минимальная общая база технарей)

                            А вот применять этот экзамен как общую линейку «насколько вы готовы ворваться в пучины АД», как-то не выходит. По крайней если не целиться стать суровым ресерчером.
                        0
                        Тут весь вопрос в том, чему именно учат в ШАДе (я честно говоря не знаю, не учился там). Но в целом обработка данных — это мат. статистика, которая вырастает из теории вероятности (на саму статистику задач, судя по всему нет как раз потому что не везде ее проходят, а вот на теорвер есть. При этом нет какого чрезмерного усложнения, стохастичских процессов, многомерных пространств и.т.д). Линейная алгебра — это по сути теория работы с пространсвами, описываемыми математическими функциями — те самые наборы данных, которые далеко не всегда сводятся к простому наборы чисел. Линейная алгебра позволяет их описывать и с ними работать. Не совсем уверен, нужны ли в анализе сходимости рядов, но не удивлюсь что нужны, доказывать что какая-нибудь аппроксимирующая функция на бесконечности сходится к аппроксимируемой.

                        По сути вся эта «чрезмерная математика» — это и есть по существу анализ данных. А программирование на питоне — это просто интерфейс, который позволяет использовать математические инструмент, не понимая его работы. Из за наличия такого инструмента, со дной стороны работать становистя гораздо проще, с другой появляется огромное количество людей, которые способны только в известной заранее ситуации применить известную заранее функцию. Для такой работы действительно не надо никаких знаний. Но такой сотрудник отличается от математика примерно так же, как монтажник с молотком — от инжерена-конструктора.
                        • НЛО прилетело и опубликовало эту надпись здесь
                            0

                            По поводу третьего пункта: отчисляются всё-таки из "шадика" из-за того, что находят работу в Яндексе или по специальности..

                        0
                        1-4 курса — как-то сурово… пару семестров максимум

                        Изучал подобное NN лет назад на заочке. Ничего не пригодилось, только один раз булеву алгебру вспомнил (было много условий if, решил использовать конъюктивную нормальную форму, чтобы сократить запись… стало короче, но неочевидно, в итоге оставил как есть).

                        Если нравится решать подобные задачки — почему бы нет, дело хорошее. Если интересно в свободное время вышивать крестиком — то лучше вышивать крестиком. Если хочется работы в Яндексе или корочку от ШАД — то нужно играть по их правилам.
                        0
                        более чем достаточно. Матан в помощь, Фихтенгольц рулит.
                        +2
                        Отличная статья!
                          +1
                          Задача 7:
                          Выберем самую большую клику в графе. Допустим, её размер 9 или меньше (и покажем противоречивость допущения). Тогда каждая из оставшихся вершин, которых как минимум 21, не имеет ребра с хотя бы одной вершиной из этой клики (иначе она вошла бы в клику). Принцип Дирихле: в клике есть вершина (A), которая не имеет рёбер с тремя вершинами (B,C,D) вне клики. Никакая пятёрка вершин, содержащая A и не связанные с ней B,C,D, не может составить цикл. Следовательно, размер максимальной клики больше 9.
                            +1
                            Задача 6(пункт 2):
                            Почему бы нам не рассмотреть нулевой оператор? Тогда сразу A^T=0, а p(A)=k_0*E(все остальное занулится). Видно, что p(A)!=0, т. к. k_0!=0 по условию ==> исходное утверждение неверно.

                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                            Самое читаемое