Logo Obozu Naukowego

Algorytmy grafowe

Prowadzący

Czas Trwania Warsztatów

20 godzin - 25 jednostek lekcyjnych w ciągu 5 dni zajęć

Algorytmy grafowe

Podstawy teorii grafów i operacje na grafach w Pythonie

Podczas tego tygodnia nauczycie się myślenia o otaczającej was rzeczywistości w nowy sposób. Na zajęciach poznacie tajniki grafów i dostrzeżecie jak potężnym narzędziem do opisu rzeczywistości mogą one być. Warsztaty będą miały charakter teoretyczny oraz praktyczny, więc nie obejdzie się bez samodzielnego programowania. 

*Workshop can be held bilingually if needed.

Do kogo kierowany jest ten warsztat?

Najlepiej na warsztacie poczują się osoby zainteresowane matematyką i informatyką. Podczas tego tygodnia będziemy programować, więc wymagana jest podstawowa znajomość konceptów takich jak: funkcje, instrukcje warunkowe (if/else), pętle (for,while), listy/tablice (array/list). Jeśli programowaliście już kiedyś w innym języku niż Python, też dacie sobie radę ;)

Niezbędny sprzęt i oprogramowanie

Do udziału w warsztacie wymagany jest własny laptop. Będziemy używać darmowego środowiska anaconda, które należy samodzielnie zainstalować na laptopie przed zajęciami.

Jedynym wymaganiem odnośnie laptopa jest to, żeby działała na nim anaconda.

https://www.anaconda.com/products/individual#Downloads 

Dlaczego warto wziąć udział w tym warsztacie?

Jeśli jesteście zainteresowani w przyszłości zawodem programisty, czy studiami na kierunkach takich jak: informatyka, analiza danych, lub matematyka, to prędzej czy później temat grafów będzie wam baaardzo bliski. Czemu by więc nie zaprzyjaźnić się z nimi już teraz? ;)

Korzyści dla uczestników z udziału w warsztacie:

  • nauka podstawowych algorytmów grafowych,
  • zdobycie umiejętności aplikowania matematycznych modeli w rzeczywistości,
  • trening programowania,
  • rozwój matematycznej i algorytmicznej “intuicji”.

Program warsztatu

Dzień pierwszy

Graphs - intro

Pierwszy dzień warsztatów będzie poświęcony na zapoznanie się w grupie, wyrównanie wiedzy programistycznej, oraz przyswojenie podstawowych notacji i mechanizmów rządzących teorią grafów (directed/undirected, weighted/unweighted). Poznamy również sposoby przedstawiania grafów na komputerze.

Dzień drugi

Pathfinding

DFS, BFS, Algorytm dijkstry, problem komiwojażera, A*, omówimy wszystkie te pojęcia, napiszemy własne implementacje, zaaplikujemy te algorytmy w zadaniach, oraz przedyskutujemy złożoność i przewagi konkretnych rozwiązań nad innymi.

Dzień trzeci

Random walk

Dzień trzeci spędzimy na zabawie z algorytmami losowymi na grafach oraz szlifowaniu wcześniej zdobytych umiejętności. Będzie to głównie praca w grupach, której zwieńczeniem będzie przedstawianie wyników reszcie zespołów.

Dzień czwarty

Centrality, and community detection algorithms

Algorytmy mogą również służyć do wychwytywania zależności między grupami. Ten dzień warsztatów zostanie poświęcony na klastrowanie “społeczności” między grafami. Zobaczymy też, w jaki sposób google pozycjonuje swoje wyniki.

Dzień piąty

Freedom!!!

Ostatniego dnia podzielimy się na grupy i każdy zespół zajmie się tym na co ma ochotę np. zadaniami z olimpiad informatycznych, matematycznymi podłożami teorii grafów, rozwiązywaniem jakiegoś istniejącego problemu lub zabawą poznanymi już algorytmami.

Why do we perceive the world as stable and ourselves as local and unique? Here’s my guess: because it’s useful.

Max Tegmark