Diskret matematik: beräkningar, grafer, slumpmässiga promenader - gratis kurs från Open Education, utbildning 6 veckor, från 5 till 7 timmar per vecka, Datum: 3 december 2023.

Utbildning 2021: Doktor i fysikaliska och matematiska vetenskaper: Matematisk institut uppkallad efter. I. A. Steklov Ryska vetenskapsakademin 2009: Kandidat för fysikaliska och matematiska vetenskaper: Moscow State University. M.V. Lomonosov, specialitet 01.01.06 "Matematisk logik, algebra och talteori", avhandlingsämne: Betyg vikter av perceptroner (polynomtröskel booleska funktioner) 2009: Forskarutbildning: Moskva-staten Universitet uppkallat efter M.V. Lomonosov, Institutionen för matematisk logik och teori om algoritmer, specialitet "Algebra, logik och talteori" 2006: Specialitet: Moscow State University. M.V. Lomonosov, Institutionen för matematisk logik och teori om algoritmer, specialitet "Matematik", examen "Matematiker"

1. Grundläggande beräkningar

Låt oss säga att vi måste räkna några föremål. Finns det något bättre att göra än att bara lista föremålen och räkna dem ett efter ett? Behöver vi skriva ut vår data i sin helhet för att se om den räcker för att träna vår modell? Kan vi uppskatta hur länge algoritmen kommer att köras utan att implementera och köra den? Alla dessa frågor studeras av en gren av matematiken som kallas kombinatorik. Vi kommer att börja studera detta område av matematik, vilket gör att vi kan svara på frågorna ovan i enkla fall.

2. Avancerade beräkningar

Vi har övervägt flera standardformuleringar av kombinatorik, som redan gör det möjligt för oss att lösa många beräkningsproblem. Vi har två mål. Först kommer vi att diskutera mer komplexa formuleringar i kombinatorik i detalj. Vi kommer att diskutera kombinationsnummer i detalj. Vi kommer att titta på en annan ny standardformulering av kombinatorik - kombinationer med upprepningar. För det andra kommer vi att träna på att lösa beräkningsproblem. För att göra detta kommer vi särskilt att titta på exempel på lösningar på flera problem.

3. Diskret sannolikhet

 Låt oss lära oss att tillämpa den förvärvade kunskapen på problem med att beräkna sannolikheter. Låt oss diskutera en diskret probabilistisk modell. Förutom bara sannolikheter kommer vi också att diskutera de numeriska egenskaperna hos slumpmässiga experiment, slumpvariabler, samt deras huvudsakliga numeriska parameter, den matematiska förväntan.

4. Grunderna i grafteori

Grafer är en av de vanligaste kombinatoriska modellerna. De uppstår varhelst vi har någon form av relation mellan par av föremål. Å andra sidan har grafer icke-triviala allmänna egenskaper, som därmed visar sig användbara i en mängd olika praktiska situationer. Den här veckan börjar vi diskutera grafer. Vi kommer att diskutera grundläggande parametrar och modellövergångar, samt en speciell klass som kallas tvådelade grafer.

5. Träd och riktade grafer

Låt oss diskutera alla grundläggande begrepp relaterade till grafer. Vi kommer också att diskutera grafer utan cykler, riktade grafer, som modellerar praktiska situationer där relationerna mellan objekt är asymmetriska.

6. Projekt: slumpmässiga vandringar i grafer

Låt oss lära oss hur man tillämpar den förvärvade kunskapen för att bygga ett rekommendationssystem. Låt oss först diskutera den allmänna inställningen och överväga vårt huvudverktyg - slumpmässiga vandringar på grafer. Sedan använder vi slumpmässiga vandringar för att förutsäga samband i grafer hämtade från praktiken.