Znajdowanie najkrótszej drogi:
https://youtu.be/eCSjwO9wu0I?t=8117
oraz CodinGame – nauka programowania/algorytmiki przez tworzenie gier
https://youtu.be/eCSjwO9wu0I?t=8350
to główne tematy zajęć Olimpijskiego Koła Informatycznego.

Dijkstra wymyślił algorytm znajdowania najkrótszej drogi gdy… dowoził dziecko do przedszkola:
https://youtu.be/eCSjwO9wu0I?t=7842

Quizy OKI – jesteśmy współczesnymi odkrywcami nowych lądów!
https://youtu.be/eCSjwO9wu0I?t=10111
Rozwiązywaliśmy prawdziwe naukowe problemy – sami musimy zdefiniować problem, nie wiemy czy jest odpowiedź
https://youtu.be/eCSjwO9wu0I?t=9244
za co dziękuję
https://youtu.be/eCSjwO9wu0I?t=10008

Głównym bohaterem naszych zajęć było zadanie Maraton:
https://youtu.be/eCSjwO9wu0I?t=1199
które pozwoliło nam odkryć ALGORYTM DIJKSTRY – wyszukiwania najkrótszych dróg:
https://youtu.be/eCSjwO9wu0I?t=7937
szczegółowo omówiony w trakcie analizy zadania Maraton
https://youtu.be/eCSjwO9wu0I?t=2074

KOD zadana Maraton/ LINK do treści / OMÓWIENIE:
https://oki.org.pl/maraton/

To było wymagające zadanie.
Ale dobrze jak zadania są trudniejsze niż to co umiemy!
https://youtu.be/eCSjwO9wu0I?t=7792

Krok po kroku symulowaliśmy działanie algorytmu Dijkstry korzystając z tablicy:
https://youtu.be/eCSjwO9wu0I?t=2445
oraz symulowaliśmy działanie algorytmu Dijkstry korzystając z kolejki priorytetowej:
https://youtu.be/eCSjwO9wu0I?t=3792

Algorytm Dijkstry pokazał że nie ma jednego najlepszego podejścia.
Mieliśmy prawdziwą naukową dyskusję kiedy jaki algorytm jest lepszy
https://youtu.be/eCSjwO9wu0I?t=4934

Złożoność algorytmu Dijkstry może być V^2 (wykorzystanie tablicy):
https://youtu.be/eCSjwO9wu0I?t=3401
ale może być również V*logV lub V^2*logV (wykorzystanie kolejki priorytetowej)
https://youtu.be/eCSjwO9wu0I?t=4707

I to jest piękno algorytmiki – wiele możliwości – i my jako eksperci którzy doradzamy!
https://youtu.be/eCSjwO9wu0I?t=5344

Ale mieliśmy też konkluzje.
Pesymistycznie nasze algorytmy różnią się niedużo
Optymistycznie kolejka priorytetowa jest duuuuużo szybsza od tablicy
https://youtu.be/eCSjwO9wu0I?t=5119

A jak jest na Olimpiadzie – kolejka czy tablica?
https://youtu.be/eCSjwO9wu0I?t=5308

Napisaliśmy również kod naszego programu Maraton
https://youtu.be/eCSjwO9wu0I?t=5370
którego najważniejszym elementem było utworzeniu grafu z wagami (odległościami):
https://youtu.be/eCSjwO9wu0I?t=5652
wczytanie grafu:
https://youtu.be/eCSjwO9wu0I?t=5852
oraz sam algorytm Dijkstry:
https://youtu.be/eCSjwO9wu0I?t=6300

Ponieważ kolejka priorytetowa bierze max wartości – my potrzebujemy wziąć najmniejszą – więc na kolejce priorytetowej trzymaliśmy wartości z minusami
https://youtu.be/eCSjwO9wu0I?t=7190
oraz
https://youtu.be/eCSjwO9wu0I?t=7327

Podsumowanie zadania Maraton:
https://youtu.be/eCSjwO9wu0I?t=7809

Ciekawe zagadnienia były w naszych quizach:
Ile krawędzi ma graf pełny / klika:
https://youtu.be/eCSjwO9wu0I?t=285

Pokazaliśmy również moc logarytmu – szczegółowo wyjaśniliśmy sobie czym jest logarytm:
https://youtu.be/eCSjwO9wu0I?t=549

Wytłumaczyliśmy sobie szczegółowo czym jest kolejka priorytetowa:
https://youtu.be/eCSjwO9wu0I?t=792

Nasza Praca Domowa:
https://oki.org.pl/pd29/

Pasja, odkrywanie, radość!
Daniel Olkowski

———–
Zapisz się na newsletter a będziesz na bieżąco:
https://forms.gle/Az61QABG81RNk5oT7

———