Algorytm Edmondsa-Karpa — eksploracja kosmosu

Rodzaj: wykład
Udział publiczności: z aktywnym udziałem
Limit uczestników: 57 / 60 ( liczba wolnych miejsc / liczba wszystkich miejsc )
Miejsce: Wydział Informatyki
ul. Wiejska 45A
15-351 Białystok
Zobacz na mapie kampusu
Nr sali : Aula 12B (żółta etykieta: B5)
Data: 2024-03-13
Godzina: 12:15
Czas trwania: 50 min
Dostępność: wymagana rejestracja przez stronę
Osoba prowadząca: dr inż. Anna Borowska
Rejestracja zakończyła się: 12 Marzec 2024 15:00

ZAREJESTRUJ SIĘ NA WYDARZENIE

OPIS WYDARZENIA

W trakcie wykładu przedstawię, w prosty sposób, algorytm Edmondsa-Karpa wyznaczający maksymalny przepływ w sieci. Następnie uczniowie zastosują ten algorytm do rozwiązania postawionego problemu.
Celem spotkania, poza dobra zabawą, jest uświadomienie uczniom szkół średnich, że Informatyka to nie tylko gry, Internet i komputery. Informatyka to dziedzina nauki, której celem jest wspomaganie działań we wszystkich aspektach życia.
Sieć przepływowa to skierowany graf prosty, ważony (z wartościami przepustowości na krawędziach), posiadający dwa wyróżnione wierzchołki: źródło (tj. wierzchołek, do którego nie prowadzi żadna krawędź) i ujście (tj. wierzchołek, z którego żadna krawędź nie wychodzi). Wyznaczanie przepływu w sieci polega na przyporządkowaniu każdej krawędzi pewnej wartości, która oznacza liczbę danych aktualnie przesyłanych przez tą krawędź. Ograniczenia przepustowości sieci stanowią istotne zagadnienie w transporcie publicznym, w telekomunikacji, w procesach produkcyjnych, w sieciach ciepłowniczych, itd. …