Sommaren är det dags för inträdesprov. Just nu närmar sig urvalet till Yandex Data Analysis School sitt slut – intervjuer pågår för de som redan klarat provet. SHAD lär ut maskininlärning, datorseende, textanalys av naturligt språk och andra områden inom modern datavetenskap. Under två år läser studenterna ämnen som vanligtvis inte ingår på högskoleprogrammen, även om de är mycket efterfrågade både inom naturvetenskap och industri. Du kan studera inte bara i Moskva - skolan har filialer i Jekaterinburg, Minsk, Kiev, Novosibirsk, St. Petersburg. Det finns också en korrespondensavdelning där du kan studera genom att titta på videoföreläsningar och korrespondens med lärare i Moskvaskolan via post.

Men för att komma in i ShAD måste du klara tre steg - fyll i ett frågeformulär på webbplatsen, klara inträdesprovet och kom för en intervju. Varje år går seniora studenter, utexaminerade och doktorander från Moskva State University, MIPT, HSE, ITMO, St. Petersburg State University, UrFU, NSU in i ShAD, och alla klarar inte av våra tester. I år fick vi enkäter från 3 500 personer, varav 1 000 antogs till provet, och endast 350 klarade det framgångsrikt.

För den som vill prova sig fram och förstå vad han är kapabel till har vi förberett en analys av årets antagningsprov. Alternativet som vi har valt åt dig löstes av 56 % av de som löste det. I den här tabellen kan du se hur många personer som kunde lösa var och en av uppgifterna i den.

Men först skulle jag vilja förklara vad vi kontrollerar med tentamen och hur vi går tillväga för att förbereda det. Under de allra första åren av ShADs existens fanns det ingen skriftlig tentamen, eftersom det fortfarande var få ansökningar och det var möjligt att prata med alla som klarade onlinetestet personligen. Men intervjuerna blev också längre; några alumner minns att de blivit intervjuade i sex timmar, vilket ger många utmanande problem. Sedan var det fler sökande – och 2012 dök en skriftlig tentamen upp.

Kuratorerna för Moscow ShAD är involverade i skapandet av versionen, en av dem är jag; kollegor från filialerna hjälper dem med valet av arbetsuppgifter. Antalet problem i varianten har inte förändrats mycket under dessa fyra år: först var det sju av dem, och förra året var det åtta. Varje alternativ har matematiska problem (från fem till sju) och algoritmiska problem (ett eller två).

När det gäller matematik kontrollerar vi givetvis om de sökande är flytande inom programmets huvudområden: algebra, matematisk analys, kombinatorik och sannolikhetsteori. Men det som är viktigt för oss är inte kunskapen som uppnås genom att proppa och glöms bort en vecka efter provet eller tentan - som hemska formler från tabellen över obestämda integraler eller Elevens fördelningsfunktion; det är därför vi tillåter sökande att ta med sig eventuella papperskällor till den skriftliga tentamen. Mycket mer värdefullt är en förståelse för essensen av vad som händer, liksom förmågan att tillämpa standardfakta och metoder i ovanliga situationer. Vi försöker också hålla beräkningskomplexiteten till ett minimum; även tvåsiffriga tal måste multipliceras sällan. Så på provet kommer du inte att hitta rutinmässiga och tråkiga beräkningsövningar, och många uppgifter kommer att verka icke-standardiserade och kanske till och med Olympiad.

I delen som rör algoritmer undviker vi uppgifter som kräver kunskap om specifika datastrukturer (sökträd, hashtabeller etc.) eller algoritmer (snabbsorteringsalgoritmer, algoritmer för att hitta kortaste vägarna på grafer etc.). Dessutom kräver vi inte att sökande skriver en implementering av den uppfunna algoritmen på något programmeringsspråk; snarare till och med tvärtom - på alla möjliga sätt avråder vi från detta. I det skriftliga provet är vi faktiskt inte mest intresserade av programmeringsförmåga, utan av förmågan att tydligt beskriva algoritmen och, om nödvändigt, övertyga läsaren om att den uppfyller begränsningarna för driftstiden och mängden tilldelat minne. Men beslut som innehåller kod på vilket språk vi än kan läsa accepteras också, men de är svårare att verifiera och dessutom måste de fortfarande åtföljas av en motivering för riktighet.

Problem 1

Hitta gränsen för sekvensen (a n) för vilken

Svar

Lösning

Först bevisar vi att sekvensen konvergerar. Om en< 0 , då a n + 1< 0 , så det är avgränsat från ovan. Jämföra en och a n + 1:

Det ser vi för a n ∈ (-1; 0) ojämlikheten en< a (n+1) , det vill säga sekvensen ökar. Enligt Weierstrass-satsen har den en gräns. För att hitta det, låt oss gå till gränsen i vår återkommande relation:
varav gränsen kan vara ett av siffrorna 0, –1 och 4. Det är inte svårt att förstå att detta är 0.

Uppgift 2

På ett plan belagt med identiska rektanglar med sidorna 10 och 20 (rektanglarna ligger intill varandra), rita en slumpmässig cirkel med radie 4. Hitta sannolikheten att cirkeln har gemensamma punkter med exakt tre rektanglar.

Svar

Lösning

Vi kommer att övervaka positionen för cirkelns mittpunkt. Det är tydligt att man kan begränsa hänsynen till det inre av en rektangel. Det är lätt att se att för att cirkeln ska skära exakt tre rektanglar måste två villkor vara uppfyllda: (1) avståndet från mitten till rektangelns två närmaste sidor måste vara mindre än 4; (2) avståndet till rektangelns närmaste hörn måste vara större än 4. Genom att veta detta kan vi rita en uppsättning punkter som uppfyller dessa villkor.

Därför är den eftersökta sannolikheten

Problem 3

Dima och Vanya turas om att fylla i storleksmatrisen 2n × 2n... Vanyas mål är att få den resulterande matrisen att ha ett egenvärde på 1, och Dimas mål är att förhindra honom. Dima går först. Har någon av dem en vinnande strategi?

Svar

Med rätt strategi kommer Vanya att vinna.

Lösning

Den resulterande matrisen A kommer att ha ett egenvärde 1 om matrisen A - E kommer att vara degenererad. Vanya kan till exempel uppnå detta enligt följande. Efter att Dima gick in i något element en ij, Vanya går in i ett nytt element ett ik på samma linje så att a ik -δ ik = - (a ij -δ ij), var δ ijÄr Kronecker-symbolen. Sedan summan av talen i var och en av raderna i matrisen A - E kommer att vara lika med noll, det vill säga matrisen A - E kommer att vara degenererad.

Problem 4

Hitta matrisens determinant A = (a ij), var

Svar

Lösning

Låt oss använda formeln Subtrahera från varje rad i matrisen den föregående, och sedan från varje kolumn den föregående. Den resulterande matrisen kommer att se ut så här:

Om vi fortsätter resonemanget genom induktion ser vi att determinanten för den ursprungliga matrisen är lika med determinanten för identitetsmatrisen, dvs. ett.

Problem 5

Givet två arrayer av heltal a och b, och alla element bär olika. Det krävs för att hitta en uppsättning index i_1< i_2 <… < i_k för vilken uppsättningen a, ..., aär en permutation av elementen i array b och skillnaden i_k - i_1 lägsta möjliga. Tidsgräns - O (nk)(men du kanske kan snabbare), från minnet - O (n).

Lösning

Detta kan göras i en passage genom arrayen a. Varje gång vi stöter på ett element i arrayen b, skriver vi den och dess nummer i speciella arrayer. Samtidigt upprätthåller vi segment I i dessa arrayer, där vi hoppas kunna hitta alla de olika elementen b... Det är tydligt att om nästa element i arrayen a sammanfaller med det första elementet i segment I, så kan jag helt klart inte vara kortast ett segment som uppfyller problemets tillstånd, och vi kan flytta dess vänstra ände. Om vi i nästa steg förstår att I innehåller alla olika element b, då är jag en kandidat för ett svar; i detta fall flyttar vi också dess vänstra ände.

Kvalitet O (n) från minnet är uppenbart. Kvalitet O (nk) i komplexitet kan motiveras på följande sätt: vi gör allt i en omgång (därav n) och måste vid varje steg söka efter ett element i arrayen b(härifrån k). Det är klart att algoritmen kan förbättras: om du först sorterar b och använd binär sökning, får vi O (n log k)... Om du använder perfekt hash kan du uppnå komplexiteten O (n + k).

Problem 6

År 2222 hålls volleybollturneringar enligt ett nytt system. De säger att Team A överträffar lag B om A slår B eller något lag som slår B. Varje lagpar spelar 1 gång. Oavgjort är uteslutet av volleybollreglerna. Mästaren är laget som överträffar alla andra lag. (a) Bevisa att det definitivt finns en mästare (b) Bevisa att det inte kan finnas exakt två mästare.

Lösning

Låt oss komma överens om att varje lag får poäng för turneringen lika med antalet lag som det har passerat. Först bevisar vi följande enkla lemma:

Lemma. Låt Lag E inte vara överlägset Lag K. Då fick K fler poäng än E.

Bevis. Om E inte överstiger K så besegrar K lag E, liksom alla lag som lag E besegrat.

Låt nu X vara det lag som besegrades av lag E. Om E vann över X, så vann K över X. Så, K är överlägset X. Om E vann över lag F, som vann över X, så noterar vi att K vann också i F. Det betyder att K har vunnit över F, vilket har vunnit över X, det vill säga K är överlägset X. Totalt är K överlägset alla lag som överträffat E, och även E till start, dvs. är, minst ett lag mer än E Lemmat är bevisat.

(a) Låt A vara det lag med högst poäng. Låt oss bevisa att A är en mästare. Låt oss säga att så inte är fallet, då finns det ett lag B, som A inte har överträffat. Med lemma finner vi att B har tjänat fler poäng än A. En motsägelse.

(b) Anta att vi har två mästare: A och B. De spelade med varandra; låt till exempel vinna A. Eftersom B är överlägset alla andra lag (och A i synnerhet), så besegrade B något lag som vann över A.

Låt oss till att börja med säga att det finns lag som har vunnit både A och B. Då kan det visas att det av dem (låt oss kalla det C), som fått flest poäng, blir tredje mästare. Låt E faktiskt vara ett lag som inte har överträffat C. Sedan besegrade E för det första både A och B, och för det andra fick E fler poäng än C. En motsägelse.

Anta nu att det inte finns några lag som vann både A och B. Tänk på uppsättningen av alla sådana lag som vann A men förlorade B. Observera att den inte är tom (se ovan). Bland dem, låt oss ta laget med flest poäng. Sedan, med hjälp av lemma, kan vi fastställa att detta lag är den tredje mästaren.

Problem 7

Beräkna integralen

Yandex öppnar en ny registrering för School of Data Analysis. Detta är en gratis tvåårig kvällskurs för dig som vill utbilda dig i databehandling, dataanalys och informationssökning från Internet. Skolan kräver god matematisk bakgrund och är främst utformad för studenter och unga utexaminerade från ingenjörs- och matematikspecialiteter.

Hur man fortsätter

Du måste fylla i ett formulär på skolans hemsida till 15 maj... Du kommer sedan att få ett e-postmeddelande med en länk till online-quizet i matematik och programmering. Alla som klarar provet kommer att bjudas in av skolan till en skriftlig tentamen, som äger rum i slutet av maj - början av juni. De bästa enligt provresultaten kommer att behöva gå igenom en intervju, baserat på resultatet av vilken det slutliga beslutet kommer att fattas.

Träningsprogram

På skolans hemsida kan du studera de gångna årens tentamensuppgifter och ta reda på vad du ska förbereda dig på. Det kommer att vara möjligt att bekanta sig med skolans lärare och lära sig om den nya riktningen "Big Data" på ShADs öppna dag. Det kommer att ske 19 april på Yandex-kontoret i Moskva måste du registrera dig för att delta.

Lektioner på ShAD hålls på kvällarna på vardagar. Du kan studera i skolan personligen eller i frånvaro, genom videoföreläsningar. Under sina studier eller efter examen kan studenterna ta praktik på Yandex.

School of Data Analysis har funnits sedan 2007 och har utexaminerat mer än 300 specialister, av vilka många är engagerade i vetenskap, arbetar i Yandex och andra stora IT-företag i Ryssland och utomlands. ShAD-filialer finns i St. Petersburg (inom Computer Science Center), Novosibirsk, Jekaterinburg, Minsk och Kiev.

Hej! Vi är glada att gratulera dig till din antagning till School of Data Analysis! Närmare september kommer kuratorn för din filial att skriva om organisationsfrågorna.

Det visar sig att jag är i skolan. Och nästan säkert den äldsta studenten där. Det blir inga problem med par, du kommer till och med att kunna gå till skridskobanan (om du inte åker med en instruktör kan du behöva skjuta upp det till helgen). Och nu vad jag gjorde.

En bekant föreslog att pröva lyckan: "du kan." Onlineval var helvete och mörker, det plågades i fyra timmar. Även om jag måste erkänna att jag läste lite: i programmeringsuppgifter översatte jag helt enkelt program från pseudokod till C ++, och till och med ett problem på matriser, utan att plocka upp en nyckel, löste jag det helt enkelt direkt med Yoksel. Jag visste inte vad ett "positivt tröghetsindex" är (skrev jag det här namnet korrekt?) - jag var tvungen att hitta det, det visade sig bara vara antalet positiva element i den kvadratiska formens diagonala expansion.

Tja, det andra steget är en undersökning ansikte mot ansikte. Jag köpte en lässal, täckte mig med anteckningar och började förbereda mig. Mest av allt var han rädd för hemska integraler: vilken förstaklassstudent som helst skulle överträffa mig i detta. Tja, till saken. Detta är vad Yandex föreslog oss i examen (villkoren för problemen är förkortade).

Hur många vägar finns det att gå från (0,0,0) till ( n, 2n, 3n), om du kan ta +1 steg längs någon av axlarna?
Hitta den 319:e derivatan vid noll av (x² + 17) / (x 4 −5x² + 4)
Hur många permutationer pendlar med (123) (456)?
I en liksidig triangel ABC område 1 välj en punkt M... Hitta det förväntade området ABM.
∫ 1 / √1 + e x dx
Visa att en heltalsmatris inte har rationella (icke-heltals) egenvärden.
Det finns dunkar med bensin på den runda vägen. Det finns en bil med en känd bränsleförbrukning och en tom tank med obegränsad kapacitet. För O ( n) operationer, ta reda på från vilken kapsel du behöver starta, så att du samlar bränsle kan köra hela vägen och inte stanna tom (eller säga att detta är omöjligt).

Jag löste 6 problem - förutom, förstås, integralen. Det är sant att jag blev orolig och jag bestämde mig för 2 och 3 felaktigt (med rätt metod!)

På intervjun frågade de mer om personliga saker: varför bestämde du dig för att gå i skolan, är det inte svårt för dig med jobbet, inget att alla är yngre än du? Det tog fyra dagar att svara (de första dagarna skakade jag med jämna mellanrum min post via webben när min partner vände sig bort). Och till slut svarade de.

Positiv erfarenhet från antagning. Jag kom ihåg mig själv som en fighter. Jag köpte äntligen ett läsrum (och jag skiljer mig inte från enheten, köp till punkten).

Negativ erfarenhet. Jag borde ha lugnat ner mig, då skulle problem 2 och 3 komma ut. Det var inte värt att lösa integralen alls – eller att ägna mer tid åt att förbereda integralen. Slutligen, förberedelser som det var gjorde lite. Jag skärpte upp satserna, kom ihåg hur den eller den saken är berättigad, men av det här goda krävdes bara registrering av permutationer.

Utbildning

Under 2017, registrera dig i ShAD (School of Data Analysis) Yandex.

Hej!

Jag heter Vladimir, jag är 26 år gammal. Jag har flera högre utbildningar (metallurgiingenjör samt ekonomi och företagsledning). Jag fick båda utbildningarna vid Moskvainstitutet för stål och legeringar. För tillfället arbetar jag som projektledare i ett av de inhemska IT-företagen, som är en leverantör avystem. På jobbet står jag ständigt inför behovet av att aggregera och överföra data, integrera olika system med hjälp av Enterprise Service Bus (ESB). Jag hörde talas om SHAD för ett år sedan, men föregående år var mycket hektiskt - leverans av examensarbeten på andra högre och magisterexamen, antagning till forskarskolan. Dessutom blev det en hel del utdragna, affärsresor. För tillfället är det inte så laddat, så jag tänker äntligen ta itu med frågan om förberedelser och antagning. Vid det aktuella datumet känner jag mig lite mer än helt oförberedd;) Alla institut matan är bortglömda. Jag studerade materialet på egen hand i kombinatorik och ter.tro. Jag lärde mig Python på egen hand (med hjälp av kurser om markörer och stepics). Jag tror att när det gäller komplexitet och belastning kommer utbildningen att fördelas enligt följande: Matan - 50%, Combinatorics och Ter.Ver. - 30%, Programmering - 20%.

Varför valde du att använda den här tjänsten? Det är enkelt. Jag tror att det kommer att hjälpa mig att spåra dynamiken och kanske hitta folk som kan hjälpa mig, eller som jag kan hjälpa :)

Kompletterande kriterium

Inskrivning i ShAD. Inte nödvändigtvis för en heltidsavdelning, men gärna för en budgetplats.

Personliga resurser

Resurserna för denna uppgift är tid och information. Tiden är knapp, tk. arbete, tjänsteresor och utbildning av elever.

Du kan behöva pengar för att betala för kurser eller en handledare. Det är inga speciella problem med pengar.

Målets hållbarhet

Jag vill gå till ShAD för att få unik kunskap som kommer att hjälpa mig i framtiden. Denna kunskap tillhandahålls av helt unika människor, bekanta med vilka, jag är säker på, inte kommer att vara överflödiga i mitt liv. Dessutom är detta en bra utmaning för att bevisa självständighet, självorganisering och förmåga att nå uppsatta mål.

Nyligen har det ukrainska IT-samhället ofta diskuterat problemen med förnedrande utbildning i Ukraina och Ryssland: universiteten släpper redan inte cyborgprogrammerare, som beräknar vilket projekt som helst på en dag och flitigt börjar implementera det, men i bästa fall självlärda. kodare som står på de bakre raderna i publiken, istället för att lyssna på föreläsningar om gamla rörmottagare läser de böcker om programmeringsspråk. Ja, dessa människor kan gratuleras - de försöker själva på något sätt lära sig för att hitta ett jobb åt sig själva i framtiden, men ofta tillåter bristen på metodik och en väldefinierad inlärningsprocess inte självlärda människor att konkurrera med "old school" programmerare. Jag tillhör också sådana personer.

Jag använde främst min universitetsbänk för att studera olika programmeringsspråk, lärde mig mycket, fick erfarenhet av att arbeta som programmerare för uthyrning och i egna projekt, men jag känner att det fortfarande finns en enda röra i mitt huvud som akut måste föras in i vissa. typ av strukturerad form. Som ett resultat av detta började jag systematisera den kunskap jag fick, leta efter alternativ för att lösa problemet ännu snabbare och mer effektivt, skriva ner och lyfta fram en klass av verktyg som skulle hjälpa mig med detta. Men inte ens det passade mig. Jag kände att det var nödvändigt att vara i sällskap med människor som ligger huvud och axlar över mig i kunskap, för att ta till sig deras erfarenheter. Så jag stötte på en annons om rekrytering till School of Data Analysis från Yandex i Ukraina.

Varför ville jag gå på Högskolan för dataanalys? För jag behöver nu övningen att lösa komplexa problem som luft, där du inte bara behöver kunskap om ett programmeringsspråk, utan en bra kunskapsbas i matematik och sannolikhetsteori. Jag tror att jag genom att lära mig lösa sådana problem blir mer konkurrenskraftig på marknaden – och detta är min grundläggande uppgift, drivkraften bakom min vilja att lära mig nya saker. Jag tror att människor som har skapat ett så mycket vetenskapligt projekt har mycket att lära och värt att kämpa för lärandemöjligheter.

Träning

För att ansöka om antagning var det nödvändigt att fylla i ett detaljerat frågeformulär och lösa flera mattproblem. analys, sannolikhetsteori, analytisk geometri. Uppgifterna var mycket enkla, men eftersom det av säkerhetsskäl var nödvändigt att endast ange svaren, och inte lösningen, när jag fyllde i frågeformuläret, bestämde jag mig för att dubbelkolla allt ett par gånger för att gå igenom detta stadium för Säker. Spenderade ett par kvällstimmar efter jobbet på den och skickade den.

En vecka senare fick jag ett brev från skolans antagningskommitté där det stod att jag hade klarat det första steget och blev inbjuden till en intervju på Yandex-kontoret i Kiev. Jag fick rådet att bekanta mig med de huvudsakliga ämnen som intervjuerna kommer att äga rum om. En trevlig stund var att frågorna också åtföljdes av böcker som man kunde förbereda sig på (jag klarade den matematiska analysen på institutet för fyra år sedan och jag glömde förstås böckernas namn).

Jag bestämde mig för att ägna två veckor åt att förbereda mig för intervjun och varje dag efter jobbet kom jag ihåg vad jag hade glömt och lärde mig det jag inte visste innan. I synnerhet var jag tvungen att lära mig linjär algebra från grunden, eftersom det inte lärdes ut på min elektronikavdelning. Jag vill säga att om du redan har tagit examen från universitetet och ditt arbete inte är relaterat till matematik, måste du avsätta mer än två veckor för förberedelser. Det är mycket önskvärt att du har en semester vid denna tidpunkt, eftersom du behöver spendera mycket ansträngning och tid. Tyngdpunkten ska inte läggas på teori, utan på att lösa praktiska problem, vilket är svårt efter en arbetsdag. Men teorin är också nödvändig att känna till "från pärm till pärm", eftersom uppgifterna vid intervjun ofta var icke-standardiserade.

Tid "H"

Så dagen för intervjun kom. På morgonen kom jag till Yandex-kontoret, träffade examinatorerna (de var underbara unga killar med en tjej från Moscow State University), och intervjun började. Det bestod av praktiska uppgifter. Efter att ha löst den första får du en andra, sedan en trea, och så vidare tills examinatorn förstår att du har godkänts, eller du inte förstår att du har blivit underkänd. Den första uppgiften handlade om programmering.

Min första uppgift var denna: att skriva ett program för att hitta GCD på vilket programmeringsspråk som helst. Eftersom jag i skolan gick på olympiader i datavetenskap och matematik löste jag det snabbt (ur minnet) och gick vidare till nästa. Den andra uppgiften är att hitta derivatan av x till potensen av x. Ganska lätt uppgift om man känner till logaritmens egenskaper, men jag har glömt just denna egenskap. Lyckligtvis ledde examinatorn mig i denna riktning, och problemet löstes snabbt. Jag vill understryka att vid intervjun, till skillnad från enkäten, var det inte längre svaren som kontrollerades, utan tankegångarna som ledde fram till svaret. Ett sådant system för antagning användes i samma KPI innan införandet av en enhetlig testning och gav ganska bra resultat. Det kan ses att skolan inte organiserades för Yandex PR, utan för att lovande ungdomar skulle kunna göra ett kvalitativt steg i utvecklingen.

Jag kommer inte säkert ihåg de ytterligare uppgifterna, jag kan bara komma ihåg ämnena: beräkna determinanten för en matris av storlek n, där n är ett valfritt tal; kontrollera om vektorutrymmet är en bas; beräkna variansen av fördelningsfunktionen för en given sannolikhetstäthetsfunktion. I genomsnitt tog intervjun två timmar – någon gav upp tidigare, någon satt till det sista.

"Prova shche"

Betygsnämnden skickade resultatet per post, oavsett om personen godkänts eller inte. De skickade ett meddelande till mig om att jag misslyckades.

Överraskande nog, efter att jag inte blev antagen, försvann inte lusten att studera vid ShAD någonstans, utan bara intensifierades. I år vill jag också försöka gå i skolan, men jag försöker förbereda mig i förväg. Till att börja med måste du återigen komma ihåg hela teorin, och sedan - att demontera och demontera problemen, eftersom de främst är viktiga för antagning.

Med den här artikeln vill jag officiellt starta min kampanj för att förbereda mig för att gå med i Yandex-skolan. Jag planerar att dela mina tankar och utvecklingar i denna riktning med DOU-läsare: Jag tror att jag inte är den enda som förbereder mig för antagning i år.