El verano es la época de los exámenes de acceso. En este momento se está completando el proceso de selección para la Escuela de Análisis de Datos Yandex: se están realizando entrevistas para aquellos que ya aprobaron el examen. El ShAD enseña aprendizaje automático, visión por computadora, análisis de textos en lenguaje natural y otras áreas de la informática moderna. Durante dos años, los estudiantes estudian materias que no suelen incluirse en los programas universitarios, aunque tienen una gran demanda tanto en la ciencia como en la industria. Puedes estudiar no sólo en Moscú: la escuela tiene sucursales en Ekaterimburgo, Minsk, Kiev, Novosibirsk y San Petersburgo. También hay extramuros, donde puedes estudiar viendo videoconferencias y manteniendo correspondencia con profesores de la Escuela de Moscú por correo.

Pero para ingresar al ShAD, es necesario completar con éxito tres etapas: completar un formulario de solicitud en el sitio web, aprobar el examen de ingreso y asistir a una entrevista. Cada año, estudiantes de último año, graduados y estudiantes de posgrado de la Universidad Estatal de Moscú, el Instituto de Física y Tecnología de Moscú, la Escuela Superior de Economía, ITMO, la Universidad Estatal de San Petersburgo, UrFU, NSU ingresan al ShAD, y no todos hacen frente a nuestro pruebas. Este año recibimos solicitudes de 3.500 personas, de las cuales 1.000 fueron admitidas al examen y sólo 350 lo aprobaron con éxito.

Para aquellos que quieran probarse a sí mismos y entender de lo que son capaces, hemos preparado un análisis. examen de admision este año. La opción que elegimos para ti fue resuelta por el 56% de quienes la resolvieron. En esta tabla puedes ver cuántas personas fueron capaces de resolver cada una de las tareas de la misma.

Pero primero me gustaría explicaros qué comprobamos con el examen y cómo abordamos su preparación. En los primeros años de existencia del SAD no existía el examen escrito, ya que todavía había pocas solicitudes, y era posible hablar personalmente con todos los que superaban la prueba online. Pero las entrevistas fueron más largas; Algunos graduados recuerdan haber sido entrevistados durante seis horas y haberles pedido muchas tareas desafiantes. Luego hubo más solicitantes y en 2012 apareció un examen escrito.

La creación de la variante la llevan a cabo los curadores del ShAD de Moscú, uno de los cuales soy yo; Los compañeros de las sucursales les ayudan en la selección de tareas. El número de tareas de la versión no ha cambiado mucho en estos cuatro años: al principio eran siete y el año pasado ocho. Cada opción tiene problemas matemáticos (de cinco a siete) y problemas de algoritmo (uno o dos).

En cuanto a las matemáticas, por supuesto comprobamos si los solicitantes dominan las secciones principales del programa: álgebra, Análisis matemático, combinatoria y teoría de la probabilidad. Pero lo importante para nosotros no son los conocimientos que se consiguen abarrotando y olvidando una semana después de un examen o prueba, como terribles fórmulas de una tabla. Integrales indefinidas o Funciones de distribución de estudiantes; Es por eso que permitimos que los solicitantes lleven consigo cualquier fuente impresa al examen escrito. Mucho más valioso es comprender la esencia de lo que está sucediendo, así como la capacidad de aplicar hechos y métodos estándar en situaciones inusuales. También intentamos mantener la complejidad computacional al mínimo; Incluso los números de dos dígitos rara vez se multiplican. Por lo tanto, en el examen no encontrará ejercicios computacionales rutinarios y tediosos, y muchas tareas le parecerán no estándar y, tal vez, incluso olimpiadas.

En términos de algoritmos, evitamos tareas que requieren conocimiento de estructuras de datos específicas (árboles de búsqueda, tablas hash, etc.) o algoritmos (algoritmos de clasificación rápida, algoritmos para encontrar caminos más cortos en gráficos, etc.). Además, no exigimos a los solicitantes que escriban una implementación del algoritmo inventado en ningún lenguaje de programación; más bien, por el contrario, intentamos disuadir a la gente de todas las formas posibles. De hecho, en un examen escrito lo que más nos interesa no son las habilidades de programación, sino la capacidad de describir claramente un algoritmo y, si es necesario, convencer al lector de que satisface las restricciones de tiempo de ejecución y de cantidad de memoria asignada. Sin embargo, también se aceptan decisiones que contengan código en cualquier idioma que seamos capaces de leer, pero son más difíciles de verificar y, además, deben ir acompañadas de una justificación de su corrección.

Problema 1

Encuentre el límite de la secuencia (an) para la cual

Respuesta

Solución

Primero demostramos que la secuencia converge. Si un< 0 , Eso un n+1< 0 , por lo que está delimitado desde arriba. Comparemos un Y un n+1:

Vemos que cuando un n ∈(-1;0) hay desigualdad un< a (n+1) , es decir, la secuencia aumenta. Según el teorema de Weierstrass, tiene un límite. Para encontrarlo, vayamos al límite en nuestra relación de recurrencia:
de donde el límite puede ser uno de los números 0, –1 y 4. No es difícil entender que este es 0.

Problema 2

En un plano revestido con rectángulos idénticos con lados 10 y 20 (los rectángulos tienen lados adyacentes), dibuja un círculo aleatorio de radio 4. Calcula la probabilidad de que el círculo tenga puntos comunes con exactamente tres rectángulos.

Respuesta

Solución

Vigilaremos la posición del centro del círculo. Está claro que podemos limitar nuestra consideración al interior de un solo rectángulo. Es fácil ver que para que un círculo corte exactamente tres rectángulos, se deben cumplir dos condiciones: (1) las distancias desde el centro a los dos lados más cercanos del rectángulo deben ser menores que 4; (2) la distancia al vértice más cercano del rectángulo debe ser mayor que 4. Sabiendo esto, podemos representar el conjunto de puntos que satisfacen estas condiciones.

Por lo tanto, la probabilidad requerida es igual a

Problema 3

Dima y Vanya se turnan para completar la matriz de tallas. 2norte×2norte. El objetivo de Vanya es hacer que la matriz resultante tenga un valor propio de 1, y el objetivo de Dima es evitarlo. Dima va primero. ¿Alguno de ellos tiene una estrategia ganadora?

Respuesta

Con la estrategia correcta, Vanya ganará.

Solución

La matriz resultante A tendrá un valor propio de 1 si la matriz A-E será degenerado. Vanya puede lograr esto, por ejemplo, de la siguiente manera. Después de que Dima ingresó algún elemento. un ij, Vanya entra en un nuevo elemento. un ik en la misma línea para que a ik -δ ik =-(a ij -δ ij), Dónde δij– Símbolo de Kronecker. Entonces la suma de los números en cada una de las filas de la matriz A-E será igual a cero, es decir, la matriz A-E será degenerado.

Problema 4

Encuentra el determinante de la matriz. A=(aij), Dónde

Respuesta

Solución

Usemos la fórmula: Resta el anterior de cada fila de la matriz, y luego el anterior de cada columna. La matriz resultante se verá así:

Continuando con el razonamiento por inducción, estamos convencidos de que el determinante de la matriz original es igual al determinante de la matriz identidad, es decir 1.

Problema 5

Dados dos conjuntos de números enteros a Y b y todos los elementos b son diferentes. Necesita encontrar un conjunto de índices. i_1< i_2 <… < i_k , para lo cual el conjunto Automóvil club británico es una permutación de elementos de la matriz b, y la diferencia i_k-i_1 mínimo posible. Límite de tiempo - O(nk)(pero tal vez puedas hacerlo más rápido), de memoria - En).

Solución

Esto se puede hacer en una pasada a través de la matriz a. Cada vez que encontramos un elemento de matriz b, lo registramos y su número en matrices especiales. Al mismo tiempo, mantenemos un segmento I en estos arreglos, en el que esperamos encontrar todos los diferentes elementos. b. Está claro que si el siguiente elemento de la matriz a coincide con el primer elemento del segmento I, entonces claramente no puedo ser más corto segmento que satisface las condiciones del problema, y ​​podemos mover su extremo izquierdo. Si en el siguiente paso entendemos que I contiene todos los diferentes elementos b, entonces soy candidato para la respuesta; en este caso también desplazamos su extremo izquierdo.

Calificación En) obvio de memoria. Calificación O(nk) La complejidad se puede justificar de la siguiente manera: hacemos todo en una sola pasada (por lo tanto norte) y en cada paso debe buscar un elemento en el array b(de aquí k). Está claro que el algoritmo se puede mejorar: si primero ordenas b y usamos la búsqueda binaria, obtenemos O(n iniciar sesión k). Si usas hash perfecto, puedes lograr complejidad O(n+k).

Problema 6

En 2222, los torneos de voleibol se llevan a cabo según un nuevo sistema. Dicen que el equipo A superior equipo B si A venció a B o cualquier equipo que venció a B. Cada par de equipos juega una vez. Las reglas del voleibol excluyen un empate. El equipo que supera a todos los demás equipos es declarado campeón. (a) Demostrar que definitivamente existirá un campeón. (b) Demostrar que no puede haber exactamente dos campeones.

Solución

Acordemos que cada equipo del torneo reciba puntos iguales al número de equipos que superó. Primero demostramos el siguiente lema simple:

Lema. Deje que el equipo E no supere al equipo K. Entonces K anotó más puntos que E.

Prueba. Si E no vence a K, entonces K ha derrotado al equipo E, así como a todos los equipos que el equipo E ha derrotado.

Ahora sea X el equipo al que venció el equipo E. Si E venció a X, entonces K también venció a X. Entonces K vence a X. Si E venció al equipo F, que venció a X, entonces tenga en cuenta que K también ganó en F. Esto significa que K ganó contra F, que venció a X, es decir, K es superior a X. En total, K es superior a todos los equipos que E ha superado, e incluso a E además, es decir, al menos un equipo más que E. El lema es probado.

(a) Sea A el equipo que ha obtenido el máximo número de puntos. Demostremos que A es un campeón. Digamos que este no es el caso, entonces hay un equipo B al que A no venció. Por el lema encontramos que B obtuvo más puntos que A. Una contradicción.

(b) Tengamos dos campeones: A y B. Jugaron entre ellos; Supongamos, por ejemplo, que gane A. Dado que B es superior a todos los demás equipos (y a A en particular), entonces B venció a algún equipo que venció a A.

Para empezar, supongamos que hay equipos que derrotaron tanto a A como a B. Entonces podemos demostrar que el de ellos (llamémoslo C) que anotó más puntos será el tercer campeón. De hecho, supongamos que E es el equipo al que no venció C. Entonces, en primer lugar, E derrotó a A y a B, y en segundo lugar, E ganó más puntos que C. Una contradicción.

Supongamos ahora que no hay equipos que derrotaron a A y B. Considere el conjunto de todos los equipos que derrotaron a A pero perdieron ante B. Tenga en cuenta que no está vacío (ver arriba). Entre ellos, tomemos el equipo con más puntos. Luego usando el lema podemos establecer que este equipo es el tercer campeón.

Problema 7

Evaluar Integral

Yandex abre una nueva matrícula en la Escuela de Análisis de Datos. Se trata de cursos nocturnos gratuitos de dos años de duración para aquellos que quieran formarse en ciencia de datos y extracción de información de Internet. La escuela requiere una buena preparación matemática y está diseñada principalmente para estudiantes y jóvenes graduados de ingeniería y matemáticas.

Cómo proceder

Debes completar un formulario en el sitio web de la escuela. hasta el 15 de mayo. Después de esto, recibirá un correo electrónico con un enlace a una prueba en línea sobre conceptos básicos de matemáticas y programación. La escuela invitará a todos los que completen con éxito la prueba a realizar un examen escrito, que se llevará a cabo a finales de mayo o principios de junio. Los mejores candidatos del examen deberán pasar una entrevista, tras la cual se tomará una decisión final.

Programa de entrenamiento

En el sitio web de la escuela puedes estudiar los exámenes de años anteriores y descubrir para qué debes prepararte. Podrá conocer a los profesores de la escuela y conocer la nueva dirección "Big Data" en la jornada de puertas abiertas de ShAD. Tomara lugar 19 de abril En la oficina de Yandex en Moscú, debe registrarse para participar.

Las clases en SAD se imparten por las tardes de lunes a viernes. Puedes estudiar en la escuela a tiempo completo o parcial mediante videoconferencias. Durante sus estudios o después de graduarse, los estudiantes pueden realizar una pasantía en Yandex.

La Escuela de Análisis de Datos existe desde 2007 y en ella se han graduado más de 300 especialistas, muchos de los cuales se dedican a la ciencia y trabajan en Yandex y otras grandes empresas de TI en Rusia y en el extranjero. Existen sucursales de SAD en San Petersburgo (dentro del Centro de Ciencias de la Computación), Novosibirsk, Ekaterimburgo, Minsk y Kiev.

¡Hola! ¡Nos complace felicitarlo por su admisión a la Escuela de Análisis de Datos! Más cerca de septiembre, el curador de su sucursal escribirá sobre cuestiones organizativas.

Resulta que estoy en la escuela. Y, estoy casi seguro, el estudiante de mayor edad allí. Con las parejas no habrá ningún problema, incluso podrás ir a la pista de patinaje (excepto que los paseos con un instructor tendrán que reprogramarse para el fin de semana). Y ahora lo que hice.

Un conocido sugirió probar suerte: “tú puedes”. La selección online fue un infierno y oscuridad, sufrí durante cuatro horas. Aunque, debo admitir, leí un poco: en las tareas de programación simplemente traduje programas de pseudocódigo a C++, y simplemente resolví un problema matricial sin encontrar la clave, usando Excel. No sabía qué era un “índice de inercia positivo” (¿escribí correctamente este nombre?). Tuve que buscarlo y resultó ser solo el número de elementos positivos en la expansión diagonal de una forma cuadrática.

Bueno, la segunda etapa es el examen presencial. Compré un lector electrónico, me cubrí de notas y comencé a prepararme. Lo que más temía eran las terribles integrales: cualquier estudiante de primer año me superaría en esto. Bueno, pongámonos manos a la obra. Esto es lo que nos ofrecieron los Yandexoids durante el examen (se redujeron las condiciones de las tareas).

1. ¿Cuántas formas hay de pasar de (0,0,0) a (? norte, 2norte, 3norte), ¿si puedes hacer pasos en +1 a lo largo de cualquiera de los ejes?
2. Encuentra la derivada 319 en cero de la función (x²+17) / (x 4 −5x²+4)
3. ¿Cuántas permutaciones conmutan con (123)(456)?
4. En un triángulo equilátero A B Cárea 1 seleccione un punto METRO. Encuentre la expectativa del área. A.B.M..
5. ∫ 1 / √1+e X dx
6. Demuestre que una matriz entera no tiene valores propios racionales (no enteros).
7. Hay bidones de gasolina en la vía circular. Hay un coche con un consumo de combustible conocido y un depósito vacío de capacidad ilimitada. Para O( norte) operaciones, averigua desde qué bote debes partir para que, mientras recolectas combustible, puedas recorrer todo el camino y no quedarte vacío (o decir que esto es imposible).

Resolví 6 problemas, excepto, por supuesto, la integral. Es cierto que me preocupé y resolví 2 y 3 incorrectamente (¡con la técnica correcta!)

Durante la entrevista, te preguntaron más sobre cosas personales: ¿por qué decidiste ir a la escuela, te resulta difícil con el trabajo, está bien que todos sean más jóvenes que tú? Hubo un retraso en la respuesta de cuatro días (en los primeros días, periódicamente sacudía mi correo electrónico a través de la web cuando mi pareja se alejaba). Y finalmente respondieron.

Experiencia de admisión positiva. Me recordé a mí mismo como un luchador. Finalmente compré un lector electrónico (y no me despido del dispositivo, la compra fue acertada).

Experiencia negativa. Debería haberme calmado, entonces las tareas 2 y 3 habrían funcionado. No valía la pena resolver la integral en absoluto, ni dedicar más tiempo a las integrales en su preparación. Finalmente, la preparación tal como estaba fue de poca utilidad. Saqué los teoremas, recordé cómo se justifica tal o cual cosa, pero todo lo que se necesitaba era un registro de permutaciones.

Educación

En 2017, ingrese a la Escuela de Análisis de Datos Yandex.

¡Hola!

Mi nombre es Vladimir, tengo 26 años. Tengo varios estudios superiores (ingeniero metalúrgico y economía y gestión empresarial). Recibí ambas educaciones en el Instituto de Acero y Aleaciones de Moscú. Actualmente trabajo como gerente de proyectos en una de las empresas nacionales de TI, que es proveedor de sistemas de información para la gestión de producción. En el trabajo, me enfrento constantemente a la necesidad de agregar y transferir datos, integrar varios sistemas utilizando Enterprise Service Bus (ESB). Escuché sobre SHAD hace un año, pero el año anterior estuve muy ocupado: aprobé tesis en el segundo grado superior y maestría, ingresé a la escuela de posgrado. Además, hubo muchos viajes de negocios largos y de trabajo. De momento no estoy tan ocupado, así que estoy pensando en abordar por fin el tema de la preparación y la admisión. A día de hoy me siento un poco más que desprevenido;) Toda la matanza del instituto ha sido olvidada. Estudié el material sobre combinatoria y teoría por mi cuenta. En términos de programación, aprendí Python por mi cuenta (con la ayuda de cursos en Courser y Steppe). Creo que en cuanto a complejidad y carga de trabajo la preparación se distribuirá de la siguiente manera: Matan - 50%, Combinatoria y Ter.Ver. - 30%, Programación - 20%.

¿Por qué decidiste utilizar este servicio? Es sencillo. Creo que me ayudará a seguir la dinámica y, tal vez, encontrar personas que puedan ayudarme o a quienes pueda ayudar :)

Criterios de finalización

Inscripción en el ShAD. No necesariamente para estudiar a tiempo completo, pero preferiblemente para un lugar económico.

Recursos personales

Los recursos para esta tarea son el Tiempo y la Información. El tiempo apremia, porque... trabajo, viajes de negocios y enseñanza a estudiantes.

Es posible que necesites dinero para pagar cursos o un tutor. No hay problemas especiales con el dinero.

Objetivo ecológico

Quiero ingresar a SAD para adquirir conocimientos únicos que me ayudarán en el futuro. Este conocimiento lo proporcionan personas completamente únicas, cuyo conocimiento, estoy seguro, será absolutamente útil en mi vida. Además, este es un buen desafío para demostrar independencia, autoorganización y capacidad para alcanzar tus objetivos.

Recientemente, la comunidad informática ucraniana discute a menudo los problemas de la educación degradante en Ucrania y Rusia: las universidades ya no gradúan programadores cyborg que calculan cualquier proyecto en un día y comienzan a implementarlo diligentemente, sino, en el mejor de los casos, programadores autodidactas que están en Las últimas filas del público, en lugar de escuchar conferencias sobre viejos receptores de válvulas, leen libros sobre lenguajes de programación. Sí, se puede felicitar a estas personas: ellos mismos están tratando de aprender de alguna manera para encontrar un trabajo en el futuro, pero a menudo la falta de metodología y un proceso de aprendizaje claramente definido no permite que los autodidactas compitan con los "viejos". programadores de la escuela. Yo soy uno de estos individuos.

Usé principalmente mis días universitarios para estudiar varios lenguajes de programación, aprendí mucho, gané experiencia trabajando como programador contratado y en mis propios proyectos, pero siento que todavía hay un lío en mi cabeza que necesita urgentemente solucionarse. tipo de forma estructurada. Como resultado, comencé a sistematizar los conocimientos adquiridos, buscar opciones para resolver el problema de manera aún más rápida y eficiente, anotar y resaltar una clase de herramientas que me ayudarían con esto. Pero ni siquiera esto me convenía. Sentí que era necesario encontrarme en compañía de personas que estaban muy por encima de mí en conocimientos, para adoptar su experiencia. Entonces me encontré con un anuncio de contratación para la Escuela de Análisis de Datos de Yandex en Ucrania.

¿Por qué tenía tantas ganas de ir a la Escuela de Análisis de Datos? Porque ahora necesito práctica para resolver problemas complejos como el del aire, donde no solo se necesita conocimiento de un lenguaje de programación, sino también una buena base de conocimientos en matemáticas y teoría de probabilidades. Creo que aprendiendo a resolver estos problemas seré más competitivo en el mercado, y ésta es mi tarea principal, la fuerza impulsora de mi deseo de aprender cosas nuevas. Creo que las personas que crearon un proyecto tan altamente científico tienen mucho que aprender y vale la pena luchar por tener la oportunidad de aprender.

Preparación

Para solicitar la admisión, era necesario completar un formulario de solicitud detallado y resolver varios problemas matemáticos. análisis, teoría de la probabilidad, geometría analítica. Las tareas fueron muy fáciles, pero como al completar el cuestionario era necesario indicar solo las respuestas, y no la solución, para estar seguro, decidí revisar todo un par de veces para aprobar este escenario con seguridad. Dediqué un par de horas de la tarde a esto después del trabajo y lo envié.

Una semana después, recibí una carta del comité de admisiones de la escuela indicando que había pasado la primera etapa y que me invitaron a una entrevista en la oficina de Yandex en Kiev. Me aconsejaron que me familiarizara con los principales temas sobre los que se realizarían las entrevistas. Lo bueno fue que las preguntas también incluían libros que podían usarse para prepararme (hace cuatro años estudié análisis matemático en el instituto y, por supuesto, olvidé los nombres de los libros).

Decidí pasar dos semanas preparándome para la entrevista y todos los días después del trabajo recordaba lo que había olvidado y aprendía lo que no sabía antes. En particular, tuve que aprender álgebra lineal desde cero, ya que no se enseñaba en mi departamento de electrónica. Quiero decir que si ya te graduaste de la universidad y tu trabajo no está relacionado con las matemáticas, entonces necesitas dedicar más de dos semanas a la preparación. Es muy recomendable que tengas vacaciones durante este tiempo, ya que necesitas dedicar mucho esfuerzo y tiempo. El énfasis no debe ponerse en la teoría, sino en la resolución de problemas prácticos, lo cual es difícil de lograr después de una jornada laboral. Sin embargo, también es necesario conocer la teoría "de principio a fin", ya que las tareas de la entrevista a menudo no eran estándar.

Hora "H"

Así llegó el día de la entrevista. Por la mañana llegué a la oficina de Yandex, conocí a los examinadores (eran un chico joven y una chica agradables de la Universidad Estatal de Moscú) y comenzó la entrevista. Consistía en problemas prácticos. Después de resolver el primero, te dan el segundo, luego el tercero, y así sucesivamente hasta que el examinador entienda que pasaste, o tú entiendas que reprobaste. La primera tarea fue sobre el tema de la programación.

Mi primera tarea fue la siguiente: escribir un programa para encontrar GCD en cualquier lenguaje de programación. Como en el colegio asistía a concursos de informática y matemáticas, lo resolví rápidamente (de memoria) y pasé al siguiente. La segunda tarea es encontrar la derivada de x elevado a x. Es una tarea bastante fácil si conoces las propiedades del logaritmo, pero olvidé esta misma propiedad. Afortunadamente, el examinador me indicó esta dirección y el problema se resolvió rápidamente. Quiero enfatizar que durante la entrevista, a diferencia del cuestionario, no se verificaron las respuestas, sino la línea de pensamiento que condujo a la respuesta. Este sistema de admisión también se utilizó en el mismo KPI antes de la introducción de las pruebas unificadas y dio resultados bastante buenos. Está claro que la escuela no fue organizada para Yandex PR, sino para que los jóvenes prometedores pudieran dar un salto cualitativo en el desarrollo.

No recuerdo exactamente las tareas posteriores, sólo recuerdo los temas: calcular el determinante de una matriz de tamaño n, donde n es cualquier número; comprobar si un espacio vectorial es una base; calcular la varianza de la función de distribución para una función de densidad de probabilidad dada. En promedio, la entrevista duró dos horas: algunos se dieron por vencidos temprano, otros se quedaron sentados hasta el último minuto.

"Pruébalo otra vez"

La comisión examinadora envió los resultados por correo, independientemente de si la persona aprobó o no. Me enviaron una notificación de que no pasé.

Sorprendentemente, después de que no me aceptaron, el deseo de estudiar en ShAD no desapareció, sino que solo se intensificó. Este año también quiero intentar ingresar a la escuela, pero estoy tratando de prepararme con anticipación. Para empezar, es necesario recordar nuevamente toda la teoría y luego analizar y analizar las tareas, ya que son las que son principalmente importantes a la hora de aplicar.

Con este artículo quiero comenzar oficialmente mi campaña de preparación para unirme a Yandex School. Planeo compartir mis pensamientos y desarrollos en esta dirección con los lectores de DOU: creo que no soy el único que se está preparando para la admisión este año.