Мектепке Яндекс қабылдау. Деректерді талдау мектебіне кіру

IN Соңғы уақытУкраинаның IT-қауымдастығы Украина мен Ресейдегі білімнің деградациясының проблемаларын жиі талқылайды: университеттер енді кез келген жобаны бір күнде есептеп, оны іске асыруға ынталы кірісетін киборг-бағдарламашыларды шығармайды, бірақ ең жақсы жағдайда алдыңғы қатарда тұрған өзін-өзі үйрететін кодерлер. аудитория ескі түтік қабылдағыштар туралы лекцияларды тыңдаудың орнына бағдарламалау тілдері бойынша кітаптарды оқиды. Иә, бұл адамдарды құттықтауға болады - олардың өздері болашақта жұмыс табу үшін қандай да бір жолмен үйренуге тырысады, бірақ көбінесе әдістеме мен нақты анықталған оқу үдерісінің болмауы өзін-өзі үйрететін адамдарға бағдарламашылармен бәсекелесуге мүмкіндік бермейді. «ескі мектеп». Мен де сол кісілердің бірімін.

Мен негізінен университетте әртүрлі бағдарламалау тілдерін үйрену үшін пайдаландым, көп нәрсені үйрендім, жалдамалы бағдарламашы ретінде және өз жобаларымда тәжірибе жинадым, бірақ менің басымда әлі де бір ретсіздік бар деп ойлаймын, оны шұғыл түрде қандай да бір түрге енгізу керек. құрылымдық формада. Нәтижесінде мен алған білімімді жүйелей бастадым, мәселені тезірек және тиімдірек шешудің нұсқаларын іздей бастадым, маған көмектесетін құралдар класын жазып, бөлектей бастадым. Бірақ бұл да маған ұнамады. Білімде меннен бір иық биік тұрған азаматтардың қатарында болу, олардың тәжірибесінен сабақ алу қажет екені сезілді. Осылайша мен Украинадағы Яндекстің Деректерді талдау мектебіне түсу туралы хабарландыруға тап болдым.

Неліктен мен Деректерді талдау мектебіне барғым келді? Өйткені қазір маған ауа сияқты күрделі есептерді шешу тәжірибесі қажет, ол үшін тек бағдарламалау тілін білу ғана емес, математика мен ықтималдықтар теориясы бойынша жақсы білім базасы қажет. Осындай мәселелерді шешуді үйрену арқылы мен нарықта бәсекеге қабілетті боламын деп ойлаймын - бұл менің негізгі міндетім, жаңа нәрселерді үйренуге деген ұмтылысымның қозғаушы күші. Осындай жоғары ғылыми жобаны жасаған адамдардың үйренері көп және үйрену мүмкіндігі үшін күресуге тұрарлық деп ойлаймын.

Дайындық

Оқуға түсуге өтініш беру үшін егжей-тегжейлі сауалнаманы толтырып, бірнеше математикалық есептерді шешу қажет болды. талдау, ықтималдықтар теориясы, аналитикалық геометрия. Тапсырмалар өте оңай болды, бірақ сауалнаманы толтыру кезінде шешімді емес, тек жауаптарды көрсету керек болғандықтан, қауіпсіздік үшін бұл кезеңнен сенімді өту үшін барлығын екі рет тексеруді жөн көрдім. Мен жұмыстан кейін бір-екі сағат кешкі уақытымды өткізіп, жібердім.

Бір аптадан кейін маған хат келді таныстыру комиссиясыбірінші кезеңнен өтіп, Яндекстің Киевтегі кеңсесіне сұхбаттасуға шақырылған мектептер. Маған сұхбаттар өтетін негізгі тақырыптармен танысуға кеңес берілді. Бір қызығы, сұрақтарға дайындалуға болатын кітаптар да қосылды (мен осыдан төрт жыл бұрын институтта математикалық талдаудан өткенмін, әрине, кітаптардың атын ұмытып қалдым).

Мен сұхбатқа дайындалуға екі апта жұмсауды шештім және күн сайын жұмыстан кейін ұмытып кеткенімді есіме түсірдім және бұрын білмегенімді үйрендім. Сондай-ақ, сызықтық алгебраМен оны нөлден үйренуге тура келді, өйткені олар оны менің электроника факультетімде оқытпады. Айтайын дегенім, егер сіз университетті бітірген болсаңыз және жұмысыңыз математикаға қатысты болмаса, дайындыққа екі аптадан астам уақыт бөлу керек. Осы уақыт ішінде сізде демалыс болғаны жөн, өйткені сізге көп күш пен уақыт жұмсау керек. Теорияға емес, шешуге баса назар аудару керек практикалық тапсырмалар, бұл жұмыс күнінен кейін қиын. Дегенмен, теорияны «басынан аяғына дейін» білу керек, өйткені сұхбаттағы тапсырмалар көбінесе стандартты емес болды.

Уақыт «H»

Сөйтіп сұхбат алатын күн де ​​жетті. Таңертең мен Яндекс кеңсесіне келдім, емтихан тапсырушылармен кездестім (олар жақсы жас жігіт пен Мәскеу мемлекеттік университетінің қызы еді), сұхбат басталды. Ол практикалық тапсырмалардан тұрды. Біріншісін шешкеннен кейін емтихан тапсырушы сіздің өткеніңізді түсінгенше немесе сіз өтпегеніңізді түсінбейінше екіншісін береді, сосын үшіншісін береді. Бірінші тапсырма бағдарламалау тақырыбына арналды.

Менің бірінші тапсырмам кез келген бағдарламалау тілінде GCD табу үшін бағдарлама жазу болды. Мектепте информатика мен математикадан олимпиадаларға барғандықтан, оны тез шешіп (жадыдан) келесісіне өттім. Екінші тапсырма х-тің х дәрежесіне туындысын табу. Логарифмнің қасиеттерін білсеңіз, өте оңай тапсырма, бірақ мен бұл қасиетті ұмытып қалдым. Бақытымызға орай, емтихан алушы мені осы бағытқа бағыттап, мәселе тез шешілді. Сұхбатта сауалнамаға қарағанда, енді жауаптар тексерілмей, жауапқа жетелейтін ой пойызы болғанын атап өткім келеді. Қабылдаудың мұндай жүйесі бірыңғай тестілеуді енгізгенге дейін сол KPI-де қолданылған және жеткілікті нәтиже берді жақсы нәтижелер. Мектеп Яндекс PR үшін емес, болашағынан үміт күттіретін жастар дамуда сапалы секіріс жасай алатындай ұйымдастырылғанын байқауға болады.

Келесі тапсырмаларды нақты есіме түсіре алмаймын, тек тақырыптарды ғана есте сақтаймын: n өлшемді матрицаның анықтауышын есептеңіз, мұндағы n – кез келген сан; бар-жоғын тексеріңіз векторлық кеңістікнегіз; бойынша үлестіру функциясының дисперсиясын есептеңіз берілген функцияықтималдық тығыздығы. Орташа алғанда, сұхбат екі сағатқа созылды - біреу ертерек бас тартты, біреу соңғысына дейін отырды.

"Қайталап көріңіз"

Емтихан комиссиясы нәтижелерді адамның тапсырған-өтпегеніне қарамастан пошта арқылы жіберді. Олар маған өтпегенім туралы хабарлама жіберді.

Бір ғажабы, мені оқуға қабылдамаған соң ШАД-ға оқуға деген құштарлық сейілмей, тек күшейе түсті. Биыл мен де мектепке барғым келеді, бірақ алдын ала дайындалуға тырысамын. Алдымен, бүкіл теорияны тағы бір рет еске түсіру керек, содан кейін - тапсырмаларды бөлшектеу және бөлшектеу керек, өйткені олар қабылдау үшін ең алдымен маңызды.

Осы мақаламен мен ресми түрде Яндекс мектебіне қосылуға дайындалу науқанымды бастағым келеді. Мен DOU оқырмандарымен осы бағыттағы ойларым мен әзірлемелерімді бөлісуді жоспарлап отырмын: Менің ойымша, биылғы оқуға түсуге дайындалып жатқан жалғыз мен емеспін.

Жаз - қабылдау емтихандарының уақыты. Дәл қазір Яндекс Деректерді талдау мектебіне іріктеу аяқталуда - емтиханды тапсырғандар үшін әңгімелесу жүргізілуде. Информатика мектебі машиналық оқытуды, компьютерлік көруді, табиғи тілдегі мәтінді талдауды және заманауи информатиканың басқа салаларын үйретеді. Екі жыл бойы студенттер ғылымда да, өндірісте де үлкен сұранысқа ие болғанымен, әдетте университет бағдарламаларына кірмейтін пәндерді оқиды. Сіз тек Мәскеуде ғана емес оқи аласыз - Мектептің Екатеринбург, Минск, Киев, Новосибирск, Санкт-Петербург қалаларында филиалдары бар. Сондай-ақ бар сырттай, онда сіз бейне лекцияларды көру және Мәскеу мектебінің мұғалімдерімен пошта арқылы хат алмасу арқылы оқуға болады.

Бірақ ШАД-ға түсу үшін сіз үш кезеңнен сәтті өтуіңіз керек - сайтта өтініш формасын толтырыңыз, қабылдау емтиханын тапсырыңыз және әңгімелесуге келіңіз. Жыл сайын Мәскеу мемлекеттік университетінің, Мәскеу физика-техникалық институтының, Жоғары экономика мектебінің, ИТМО-ның, Санкт-Петербург мемлекеттік университетінің, УрФУ-дың, НМУ-дың жоғары курс студенттері, магистранттары мен аспиранттары ШАД-ға түседі және олардың барлығы біздің сынақтардан өте алмайды. Биыл 3500 адамнан сауалнама алдық, оның 1000-ы емтиханға жіберілсе, 350-і ғана сәтті өтті.

Өзін-өзі сынап көргісі келетіндер және олардың не қабілетті екенін түсінгісі келетіндер үшін біз биылғы қабылдау емтиханының талдауын дайындадық. Біз сіз үшін таңдаған нұсқаны оны шешкендердің 56% орындады. Бұл кестеде ондағы тапсырмалардың әрқайсысын қанша адам шеше алғанын көруге болады.

Бірақ алдымен мен емтиханмен нені тексеретінімізді және оны дайындауға қалай қарайтынымызды түсіндіргім келеді. SAD пайда болған алғашқы жылдары жазбаша емтихан болған жоқ, өйткені өтініштер әлі аз болды және онлайн тестілеуден өткендердің барлығымен жеке сөйлесуге болады. Бірақ кейін сұхбат ұзағырақ болды; Кейбір түлектер көптеген қиын тапсырмаларды ұсына отырып, алты сағат бойы сұхбат алғанын есіне алады. Содан кейін үміткерлер көп болды - және 2012 жылы жазбаша емтихан пайда болды.

Нұсқаны құруға Мәскеу ШАД кураторлары қатысады, олардың бірі менмін; тапсырмаларды таңдауда оларға филиалдардағы әріптестері көмектеседі. Нұсқадағы тапсырмалар саны осы төрт жылда көп өзгерген жоқ: басында олардың жетеуі болды, ал өткен жылы сегіз болды. Әрбір нұсқада математикалық есептер (бестен жетіге дейін) және алгоритмдік есептер (бір немесе екі) бар.

Математикаға келетін болсақ, біз, әрине, талапкерлердің бағдарламаның негізгі бөлімдерін меңгергенін тексереміз: алгебра, математикалық талдау, комбинаторика және ықтималдықтар теориясы. Бірақ біз үшін маңыздысы - кестедегі қорқынышты формулалар сияқты сынақтан немесе емтиханнан кейін бір аптадан кейін ұмытып кету арқылы қол жеткізілетін және ұмытылатын білім емес. анықталмаған интегралдарнемесе Студенттің үлестіру функциялары; сондықтан біз талапкерлерге жазбаша емтиханға кез келген қағаз көздерін өзімен бірге алуға рұқсат етеміз. Не болып жатқанының мәнін түсіну, сондай-ақ әдеттен тыс жағдайларда стандартты фактілер мен әдістерді қолдану мүмкіндігі әлдеқайда құнды. Біз сондай-ақ есептеу күрделілігін барынша азайтуға тырысамыз; тіпті екі таңбалы сандарды сирек көбейту керек. Сонымен, емтихан кезінде сіз әдеттегі және жалықтыратын есептеу жаттығуларын кездестірмейсіз, және көптеген тапсырмалар стандартты емес және, мүмкін, тіпті олимпиада болып көрінеді.

Алгоритмдерге келетін болсақ, біз нақты деректер құрылымдарын (іздеу ағаштары, хэш кестелері және т.б.) немесе алгоритмдерді (жылдам сұрыптау алгоритмдері, графиктің ең қысқа жол алгоритмдері және т.б.) білуді талап ететін мәселелерден аулақ боламыз. Сонымен қатар, біз үміткерлерден кез келген бағдарламалау тілінде ойлап табылған алгоритмнің орындалуын жазуды талап етпейміз; керісінше, біз мұны кез-келген жолмен жоққа шығарамыз. Шынында да, жазбаша емтиханда бізді бағдарламалау дағдылары емес, алгоритмді нақты сипаттау және қажет болған жағдайда оның жұмыс уақытына және бөлінген жад көлеміне шектеулерді қанағаттандыратынына оқырманды сендіру мүмкіндігі қызықтырады. Дегенмен, біз оқи алатын кез келген тілдегі кодты қамтитын шешімдер де қабылданады, бірақ оларды тексеру қиынырақ және оған қоса, олар әлі де дұрыстық негіздемесімен бірге жүруі керек.

1-тапсырма

Жауап

Шешім

Алдымен тізбектің жинақталатынын дәлелдейік. Егер а н< 0 , Бұл a n+1< 0 , сондықтан ол жоғарыдан шектелген. Салыстырайық а нЖәне a n+1:

2-тапсырма

Жауап

Шешім

Біз шеңбердің центрінің орнын бақылаймыз. Бір ғана тіктөртбұрыштың ішкі көрінісін қарастыра алатынымыз анық. Шеңбер дәл үш тіктөртбұрышты қиылысуы үшін екі шарт орындалуы керек екенін байқау қиын емес: 1) тіктөртбұрыштың центрінен ең жақын екі қабырғасына дейінгі қашықтық 4-тен кем болуы керек; (2) тіктөртбұрыштың ең жақын төбесіне дейінгі қашықтық 4-тен үлкен болуы керек. Осыны біле отырып, біз осы шарттарды қанағаттандыратын нүктелер жиынын сала аламыз.

Демек, қалаған ықтималдық тең

3-тапсырма

Жауап

Дұрыс стратегиямен Ваня жеңеді.

Шешім

Алынған матрица Аматрица болса, меншікті мәні 1 болады А - Едегенерация болады. Ваня бұған қол жеткізе алады, мысалы, келесідей. Дима біраз элементті енгізгеннен кейін aij, Ваня жаңа элементке кіреді aikсол жолда a ik -δ ik =-(a ij -δ ij), Қайда δijКронеккер символы болып табылады. Содан кейін матрицаның әрбір жолындағы сандардың қосындысы А-Енөлге тең болады, яғни матрица А - Едегенерация болады.

4-тапсырма

Жауап

Шешім

Біз формуланы қолданамыз матрицаның әрбір жолынан алдыңғысын, содан кейін әр бағаннан алдыңғыны алып тастаңыз. Алынған матрица келесідей болады:

5-тапсырма

Шешім

Мұны a массиві арқылы бір өтуде жасауға болады. Біз массив элементімен кездескен сайын б, біз оны және оның нөмірін арнайы массивтерге жазамыз. Сонымен бірге біз осы массивтерде I сегментін сақтаймыз, олардан біз барлық әртүрлі элементтерді табамыз деп үміттенеміз б. Егер a массивінің келесі элементі I сегментінің бірінші элементімен сәйкес келсе, онда I болуы мүмкін емес екені анық. ең қысқаесептің шартын қанағаттандыратын сегмент және біз оның сол жақ ұшын жылжыта аламыз. Егер келесі қадамда менде барлық ерекше элементтер бар екенін түсінетін болсақ б, онда мен жауапқа үміткермін; бұл жағдайда оның сол жақ ұшын да ауыстырамыз.

Баға O(n)есте сақтаудан анық. Баға О(nk)күрделілігін келесідей негіздеуге болады: біз бәрін бір өтуде жасаймыз (демек n) және әр қадамда массивтен элементті іздеу керек б(сондықтан к). Алгоритмді жақсартуға болатыны анық: егер біз алдымен сұрыптасақ бжәне екілік іздеуді пайдаланыңыз, біз аламыз O(n log k). Егер сіз тамаша хэшингті қолдансаңыз, онда сіз күрделілікке қол жеткізе аласыз O(n+k).

6-тапсырма

Шешім

Турнирге қатысатын әр команда өзінен озған командалардың санына тең ұпай алатынына келістік. Алдымен келесі қарапайым лемманы дәлелдейміз:

Лемма.Е командасы К командасынан асып кетпесін. Сонда К Е-ден көп ұпай жинады.

Дәлелдеу.Егер E K-дан аспаса, онда K E командасын, сондай-ақ E командасы жеңген барлық командаларды жеңді.

Енді X командасы Е командасынан ұтылған команда болсын. Егер Е X командасын жеңсе, онда K да Х-ты жеңді. Демек, K X-ты жеңеді. Егер Е X-ті жеңген F командасын жеңсе, онда K-ның да y F жеңетінін ескеріңіз. Демек, K да жеңді. X-ті жеңген F, яғни K X-ті жеңеді. Жалпы алғанда, K E-ді жеңген барлық командаларды, тіпті E-ді жүктеу үшін, яғни E-ден кем дегенде бір команда артық Лемма дәлелденді.

(а) Ең көп ұпай жинаған команда А болсын. А-ның чемпион екенін дәлелдейік. Олай емес делік, онда А жеңбеген В командасы бар. Лемма бойынша біз B A ұпайынан көп ұпай жинады деп аламыз. Қайшылық.

(b) Бізде екі чемпион бар делік: А және В. Олар бір-бірімен ойнады; Мысалы, А жеңіске жетсін.В барлық басқа командалардан (және, атап айтқанда, А) жоғары болғандықтан, В А командасын жеңген кейбір команданы жеңді.

Алдымен А және В екеуін де жеңген командалар бар деп есептейік. Сонда олардың ең көп ұпай жинаған біреуі (оны С деп атаймыз) үшінші чемпион болатынын көрсетуге болады. Шынында да, Е С-дан жеңілмеген команда болсын. Содан кейін, біріншіден, Е А және В екеуін де жеңді, екіншіден, Е С-ден көп ұпай жинады. Қайшылық.

Енді А және В екеуін де жеңген командалар жоқ делік. А жеңген, бірақ В-дан жеңілген барлық командалардың жиынтығын қарастырайық. Оның бос емес екенін ескеріңіз (жоғарыдан қараңыз). Олардың ішінде ең көп ұпай жинаған топты алыңыз. Содан кейін лемманы қолдана отырып, біз бұл команданың үшінші чемпион екенін анықтай аламыз.

7-тапсырма

Білім

2017 жылы ShAD (Деректерді талдау мектебі) Яндекс енгізіңіз.

Сәлеметсіз бе!

Менің атым Владимир, мен 26 жастамын. Менің бірнеше жоғары білімім бар (инженер-металлург және экономика және кәсіпорынды басқару). Екі білімімді де Мәскеу болат және қорытпалар институтында алдым. Қазіргі уақытта мен өндірісті басқарудың ақпараттық жүйелерінің сатушысы болып табылатын отандық IT-компаниялардың бірінде Жоба менеджері болып жұмыс істеймін. Жұмыс барысында мен деректерді жинақтау және тасымалдау, Enterprise Service Bus (ESB) көмегімен әртүрлі жүйелерді біріктіру қажеттілігіне үнемі тап боламын. Мен ШАД туралы бір жыл бұрын естідім, бірақ алдыңғы жыл өте қарбалас болды - екінші жоғары және магистратурада дипломдық жұмыстарды тапсыру, аспирантураға қабылдау. Сонымен қатар, ұзаққа созылған, жұмыс іссапарлары көп болды. Қазіргі уақытта ол соншалықты бос емес, сондықтан мен дайындық және қабылдау мәселесімен айналысамын деп ойлаймын. Ағымдағы датаға өзімді мүлде дайын емес сияқты сезінемін;) Барлық институт матан ұмытылды. Комбинаторика мен тер.верде материалды өз бетімше оқыдым. Бағдарламалауда мен Python тілін өз бетімше үйрендім (курстер және степик бойынша курстардың көмегімен). Менің ойымша, оқыту күрделілігі мен жүктемесі бойынша келесідей бөлінеді: Матан - 50%, Комбинаторика және Тер.Вер. - 30%, Бағдарламалау - 20%.

Неліктен бұл қызметті пайдалануды шештіңіз? Бәрі оңай. Менің ойымша, бұл маған динамиканы қадағалауға көмектеседі және маған көмектесе алатын немесе көмектесе алатын адамдарды табуға көмектеседі :)

Тоқтату критерийлері

SAD бағдарламасына тіркелу. Міндетті түрде күндізгі бөлім үшін емес, жақсырақ бюджеттік орын үшін.

Жеке ресурстар

Бұл тапсырманың ресурстары уақыт және ақпарат болып табылады. Уақыт тығыз, tk. жұмыс, іссапарлар және студенттерді оқыту.

Сізге курстарға немесе репетиторға төлеу үшін ақша қажет болуы мүмкін. Ақшаға қатысты ерекше проблемалар жоқ.

Жасыл мақсат

Мен болашақта маған көмектесетін бірегей білім алу үшін ШАД-ға түскім келеді. Бұл білімді мүлдем бірегей адамдар береді, олармен танысу менің өмірімде артық болмайтынына сенімдімін. Сонымен қатар, бұл тәуелсіздікті, өзін-өзі ұйымдастыруды және өз мақсаттарыңызға жету қабілетін дәлелдеу үшін жақсы сынақ.

Жаз - қабылдау емтихандарының уақыты. Дәл қазір Яндекс Деректерді талдау мектебіне іріктеу аяқталуда - емтиханды тапсырғандар үшін әңгімелесу жүргізілуде. Информатика мектебі машиналық оқытуды, компьютерлік көруді, табиғи тілдегі мәтінді талдауды және заманауи информатиканың басқа салаларын үйретеді. Екі жыл бойы студенттер ғылымда да, өндірісте де үлкен сұранысқа ие болғанымен, әдетте университет бағдарламаларына кірмейтін пәндерді оқиды. Сіз тек Мәскеуде ғана емес оқи аласыз - Мектептің Екатеринбург, Минск, Киев, Новосибирск, Санкт-Петербург қалаларында филиалдары бар. Сондай-ақ сырттай бөлім бар, онда бейне-дәрістерді көру және Мәскеу мектебінің мұғалімдерімен пошта арқылы хат алмасу арқылы оқуға болады.

Бірақ ШАД-ға түсу үшін сіз үш кезеңнен сәтті өтуіңіз керек - сайтта өтініш формасын толтырыңыз, қабылдау емтиханын тапсырыңыз және әңгімелесуге келіңіз. Жыл сайын Мәскеу мемлекеттік университетінің, Мәскеу физика-техникалық институтының, Жоғары экономика мектебінің, ИТМО-ның, Санкт-Петербург мемлекеттік университетінің, УрФУ-дың, НМУ-дың жоғары курс студенттері, магистранттары мен аспиранттары ШАД-ға түседі және олардың барлығы біздің сынақтардан өте алмайды. Биыл 3500 адамнан сауалнама алдық, оның 1000-ы емтиханға жіберілсе, 350-і ғана сәтті өтті.

Өзін-өзі сынап көргісі келетіндер және олардың не қабілетті екенін түсінгісі келетіндер үшін біз биылғы қабылдау емтиханының талдауын дайындадық. Біз сіз үшін таңдаған нұсқаны оны шешкендердің 56% орындады. Бұл кестеде ондағы тапсырмалардың әрқайсысын қанша адам шеше алғанын көруге болады.

Бірақ алдымен мен емтиханмен нені тексеретінімізді және оны дайындауға қалай қарайтынымызды түсіндіргім келеді. SAD пайда болған алғашқы жылдары жазбаша емтихан болған жоқ, өйткені өтініштер әлі аз болды және онлайн тестілеуден өткендердің барлығымен жеке сөйлесуге болады. Бірақ кейін сұхбат ұзағырақ болды; Кейбір түлектер көптеген қиын тапсырмаларды ұсына отырып, алты сағат бойы сұхбат алғанын есіне алады. Содан кейін үміткерлер көп болды - және 2012 жылы жазбаша емтихан пайда болды.

Нұсқаны құруға Мәскеу ШАД кураторлары қатысады, олардың бірі менмін; тапсырмаларды таңдауда оларға филиалдардағы әріптестері көмектеседі. Нұсқадағы тапсырмалар саны осы төрт жылда көп өзгерген жоқ: басында олардың жетеуі болды, ал өткен жылы сегіз болды. Әрбір нұсқада математикалық есептер (бестен жетіге дейін) және алгоритмдік есептер (бір немесе екі) бар.

Математикаға келетін болсақ, біз, әрине, талапкерлердің бағдарламаның негізгі бөлімдерін: алгебра, есептеу, комбинаторика және ықтималдықтар теориясын меңгергенін тексереміз. Бірақ біз үшін маңыздысы - бұл сынақтан немесе емтиханнан кейін бір аптадан кейін ұмытылатын және белгісіз интегралдар кестесіндегі қорқынышты формулалар немесе Студенттің үлестіру функциясы сияқты қол жеткізген білім емес; сондықтан біз талапкерлерге жазбаша емтиханға кез келген қағаз көздерін өзімен бірге алуға рұқсат етеміз. Не болып жатқанының мәнін түсіну, сондай-ақ әдеттен тыс жағдайларда стандартты фактілер мен әдістерді қолдану мүмкіндігі әлдеқайда құнды. Біз сондай-ақ есептеу күрделілігін барынша азайтуға тырысамыз; тіпті екі таңбалы сандарды сирек көбейту керек. Сонымен, емтихан кезінде сіз әдеттегі және жалықтыратын есептеу жаттығуларын кездестірмейсіз, және көптеген тапсырмалар стандартты емес және, мүмкін, тіпті олимпиада болып көрінеді.

Алгоритмдерге келетін болсақ, біз нақты деректер құрылымдарын (іздеу ағаштары, хэш кестелері және т.б.) немесе алгоритмдерді (жылдам сұрыптау алгоритмдері, графиктің ең қысқа жол алгоритмдері және т.б.) білуді талап ететін мәселелерден аулақ боламыз. Сонымен қатар, біз үміткерлерден кез келген бағдарламалау тілінде ойлап табылған алгоритмнің орындалуын жазуды талап етпейміз; керісінше, біз мұны кез-келген жолмен жоққа шығарамыз. Шынында да, жазбаша емтиханда бізді бағдарламалау дағдылары емес, алгоритмді нақты сипаттау және қажет болған жағдайда оның жұмыс уақытына және бөлінген жад көлеміне шектеулерді қанағаттандыратынына оқырманды сендіру мүмкіндігі қызықтырады. Дегенмен, біз оқи алатын кез келген тілдегі кодты қамтитын шешімдер де қабылданады, бірақ оларды тексеру қиынырақ және оған қоса, олар әлі де дұрыстық негіздемесімен бірге жүруі керек.

1-тапсырма

Жауап

Шешім

Алдымен тізбектің жинақталатынын дәлелдейік. Егер а н< 0 , Бұл a n+1< 0 , сондықтан ол жоғарыдан шектелген. Салыстырайық а нЖәне a n+1:

2-тапсырма

Жауап

Шешім

Біз шеңбердің центрінің орнын бақылаймыз. Бір ғана тіктөртбұрыштың ішкі көрінісін қарастыра алатынымыз анық. Шеңбер дәл үш тіктөртбұрышты қиылысуы үшін екі шарт орындалуы керек екенін байқау қиын емес: 1) тіктөртбұрыштың центрінен ең жақын екі қабырғасына дейінгі қашықтық 4-тен кем болуы керек; (2) тіктөртбұрыштың ең жақын төбесіне дейінгі қашықтық 4-тен үлкен болуы керек. Осыны біле отырып, біз осы шарттарды қанағаттандыратын нүктелер жиынын сала аламыз.

Демек, қалаған ықтималдық тең

3-тапсырма

Жауап

Дұрыс стратегиямен Ваня жеңеді.

Шешім

Алынған матрица Аматрица болса, меншікті мәні 1 болады А - Едегенерация болады. Ваня бұған, мысалы, келесі жолмен қол жеткізе алады. Дима біраз элементті енгізгеннен кейін aij, Ваня жаңа элементке кіреді aikсол жолда a ik -δ ik =-(a ij -δ ij), Қайда δijКронеккер символы болып табылады. Содан кейін матрицаның әрбір жолындағы сандардың қосындысы А-Енөлге тең болады, яғни матрица А - Едегенерация болады.

4-тапсырма

Жауап

Шешім

Біз формуланы қолданамыз матрицаның әрбір жолынан алдыңғысын, содан кейін әр бағаннан алдыңғыны алып тастаңыз. Алынған матрица келесідей болады:

5-тапсырма

Шешім

Мұны a массиві арқылы бір өтуде жасауға болады. Біз массив элементімен кездескен сайын б, біз оны және оның нөмірін арнайы массивтерге жазамыз. Сонымен бірге біз осы массивтерде I сегментін сақтаймыз, олардан біз барлық әртүрлі элементтерді табамыз деп үміттенеміз б. Егер a массивінің келесі элементі I сегментінің бірінші элементімен сәйкес келсе, онда I болуы мүмкін емес екені анық. ең қысқаесептің шартын қанағаттандыратын сегмент және біз оның сол жақ ұшын жылжыта аламыз. Егер келесі қадамда менде барлық ерекше элементтер бар екенін түсінетін болсақ б, онда мен жауапқа үміткермін; бұл жағдайда оның сол жақ ұшын да ауыстырамыз.

Баға O(n)есте сақтаудан анық. Баға О(nk)күрделілігін келесідей негіздеуге болады: біз бәрін бір өтуде жасаймыз (демек n) және әр қадамда массивтен элементті іздеу керек б(сондықтан к). Алгоритмді жақсартуға болатыны анық: егер біз алдымен сұрыптасақ бжәне екілік іздеуді пайдаланыңыз, біз аламыз O(n log k). Егер сіз тамаша хэшингті қолдансаңыз, онда сіз күрделілікке қол жеткізе аласыз O(n+k).

6-тапсырма

Шешім

Турнирге қатысатын әр команда өзінен озған командалардың санына тең ұпай алатынына келістік. Алдымен келесі қарапайым лемманы дәлелдейміз:

Лемма.Е командасы К командасынан асып кетпесін. Сонда К Е-ден көп ұпай жинады.

Дәлелдеу.Егер E K-дан аспаса, онда K E командасын, сондай-ақ E командасы жеңген барлық командаларды жеңді.

Енді X командасы Е командасынан ұтылған команда болсын. Егер Е X командасын жеңсе, онда K да Х-ты жеңді. Демек, K X-ты жеңеді. Егер Е X-ті жеңген F командасын жеңсе, онда K-ның да y F жеңетінін ескеріңіз. Демек, K да жеңді. X-ті жеңген F, яғни K X-ті жеңеді. Жалпы алғанда, K E-ді жеңген барлық командаларды, тіпті E-ді жүктеу үшін, яғни E-ден кем дегенде бір команда артық Лемма дәлелденді.

(а) Ең көп ұпай жинаған команда А болсын. А-ның чемпион екенін дәлелдейік. Олай емес делік, онда А жеңбеген В командасы бар. Лемма бойынша біз B A ұпайынан көп ұпай жинады деп аламыз. Қайшылық.

(b) Бізде екі чемпион бар делік: А және В. Олар бір-бірімен ойнады; Мысалы, А жеңіске жетсін.В барлық басқа командалардан (және, атап айтқанда, А) жоғары болғандықтан, В А командасын жеңген кейбір команданы жеңді.

Алдымен А және В екеуін де жеңген командалар бар деп есептейік. Сонда олардың ең көп ұпай жинаған біреуі (оны С деп атаймыз) үшінші чемпион болатынын көрсетуге болады. Шынында да, Е С-дан жеңілмеген команда болсын. Содан кейін, біріншіден, Е А және В екеуін де жеңді, екіншіден, Е С-ден көп ұпай жинады. Қайшылық.

Енді А және В екеуін де жеңген командалар жоқ делік. А жеңген, бірақ В-дан жеңілген барлық командалардың жиынтығын қарастырайық. Оның бос емес екенін ескеріңіз (жоғарыдан қараңыз). Олардың ішінде ең көп ұпай жинаған топты алыңыз. Содан кейін лемманы қолдана отырып, біз бұл команданың үшінші чемпион екенін анықтай аламыз.

7-тапсырма

Яндекс Деректерді талдау мектебіне жаңа қабылдау ашады. Бұл мәліметтерді өңдеу және талдау және интернеттен ақпарат алу саласында білім алғысы келетіндерге арналған тегін екі жылдық кешкі курстар. Мектеп жақсы математикалық дайындықты қажет етеді және ең алдымен инженерлік-математикалық мамандықтардың студенттері мен жас түлектеріне арналған.

Не істеу керек

Сізге мектеп сайтындағы форманы толтыру қажет 15 мамырға дейін. Осыдан кейін сізге математика және негізгі бағдарламалау бойынша онлайн тестке сілтеме бар электрондық хат келеді. Тестілеуді сәтті тапсырғандардың барлығын мектеп мамыр айының соңы – маусым айының басында өтетін жазбаша емтиханға шақырады. Емтиханның ең жақсы нәтижелері әңгімелесуден өтуі керек, содан кейін түпкілікті шешім қабылданады.

Оқыту бағдарламасы

Мектеп веб-сайтында сіз өткен жылдардағы емтихан тапсырмаларын зерттеп, не үшін дайындалу керектігін біле аласыз. ШАД Ашық есік күнінде мектеп мұғалімдерімен танысып, жаңа «Үлкен деректер» бағыты туралы біле аласыздар. Ол орын алады 19 сәуірЯндекстің Мәскеудегі кеңсесінде қатысу үшін тіркелу қажет.

SHAD сабақтары жұмыс күндері кешкі уақытта өткізіледі. Бейнелекциялар бойынша мектепте жеке немесе сырттай оқуға болады. Оқу кезінде немесе оқуды бітіргеннен кейін студенттер Яндекс-те тәжірибеден өте алады.

Деректерді талдау мектебі 2007 жылдан бері жұмыс істейді және 300-ден астам мамандарды шығарды, олардың көпшілігі ғылыммен айналысады, Яндекс пен Ресейдегі және шетелдегі басқа да ірі IT компанияларында жұмыс істейді. ШАД филиалдары Санкт-Петербургте (Компьютерлік ғылымдар орталығының ішінде), Новосибирскте, Екатеринбургте, Минскте және Киевте бар.