Dawno, dawno temu w zamierzchłych czasach szkoły średniej, zdarzało mi się umierać ze śmiechu czytając podręcznik do biologii. Gdy przygotowywałem się do sprawdzianu i mój umysł był już tak skatowany nieznanymi mi pojęciami, że przestawałem rozumieć mowę potoczną, czytałem na głos opis przebiegu mejozy i żonglując metafazą, anafazą, zygotenem i wrzecionem kariokinetycznym doprowadzałem się do niekontrolowanych spazmów. Zresztą wiem, że niektórzy rodzice mieli zwyczaj odczytywać fragmenty naszych podręczników na swoich imprezach w celu rozbawienia gości. Więc nie tylko ja tak miałem.
Ostatnio wróciło to do mnie, kiedy rozmawiałem z przedstawicielką Politechniki Warszawskiej (swoją drogą wiecie, że dziewczyny dzielą się na ładne, brzydkie i te z Politechniki?), która powiedziała mi, że nie może czegoś tam zrobić, bo uczy się o całkach powierzchniowych i algorytmie Edmondsa-Karpa. Sprawdziłem co to takiego przeczuwając powrót do lat młodości.
Za Wikipedią:
„Algorytm Edmondsa-Karpa jest jedną z realizacji metody Forda-Fulkersona rozwiązywania problemu maksymalnego przepływu w sieci przepływowej. Jego złożoność czasowa wynosi O(VE2), jest zatem wolniejszy od innych znanych algorytmów przepływowych działających w czasie O(V3), takich jak algorytm relabel-to-front, czy algorytm trzech Hindusów. W praktyce jednak złożoność pesymistyczna rzadko jest osiągana, co w połączeniu z prostotą czyni algorytm Edmondsa-Karpa bardzo użytecznym, szczególnie dla grafów rzadkich.”
Subskrybuj:
Komentarze do posta (Atom)
Brak komentarzy:
Prześlij komentarz