Jaką teorię warto znać pod OI - algorytmy?

k221 · Post autor: **k221** » 12 cze 2016, o 21:18

Takie pytanko trochę zawczasu - wiem, że pod OI trzeba swobodnie posługiwać się językiem programowania na poziomie strukturalnym, ogarniać matmę, warto też przyjrzeć się bibliotekom które można używać ale co jeszcze? Czy warto znać jakieś algorytmy na pamięć żeby w pół minuty je wyklepać (proszę o przykłady)? Czy przyda się wczytywanie z pliku (z tego co się orientowałem to nie, ale wolę spytać).

dec1 · Post autor: **dec1** » 12 cze 2016, o 22:37

Wczytywanie z pliku raczej się nie przyda.

Algorytmy są ważne. Przykłady:
- Euklidesa: normalny i rozszerzony
- sortowanie: liniowe, quicksort, bąbelkowe
- wyszukiwanie: liniowe, binarne
- typowe problemy np. plecakowy, komiwojażer, najdłuższy wspólny podciąg

Też różne techniki np.:
- programowanie dynamiczne
- dziel i zwyciężaj
- programowanie liniowe
- algorytmy zachłanne

Teoria grafów często się pojawia, wiele problemów można wyrazić jako grafy. Przykłady algorytmów:
- wyszukiwanie wgłąb, wszerz
- Dijkstry
- Kruskala
- Prima
- Bellmana-Forda
- szukanie cykli w grafie

Linki:

wiedzmac · Post autor: **wiedzmac** » 12 cze 2016, o 23:54

W powyższej liście oczywiście brakuje sporo rzeczy.

Zobacz sobie książkę Piotra Stańczyka pt. Algorytmika Praktyczna. Tam jest wszystko co potrzebujesz.
Do tego możesz spojrzeć na

Kod: Zaznacz cały

http://mokip.wdfiles.com/local--files/l

... n_arka.pdf

Mariusz M · Post autor: **Mariusz M** » 20 mar 2017, o 02:40

dec1, Wałaszek (ten z pierwszego linku) ma sporo błędów w swoich algorytmach
i jeszcze się przyznał że specjalnie te błędy w algorytmach zostawił

Ponury123 · Post autor: **Ponury123** » 21 mar 2017, o 09:26

mariuszm,

mariuszm pisze:dec1, Wałaszek (ten z pierwszego linku) ma sporo błędów w swoich algorytmach
i jeszcze się przyznał że specjalnie te błędy w algorytmach zostawił

Witam,
a wiesz może czy tyczy się to jakiś konkretnych działów czy po prostu błędy rozsiane losowo?

Mariusz M · Post autor: **Mariusz M** » 26 mar 2017, o 16:48

Ja sprawdzałem algorytmy związane z listami i tam było sporo błędów
Jeżeli chodzi o listy to u Cormena też nie jest dobrze

Ogólnie Wałaszek nie sprawdza warunków brzegowych
sytuacji gdy użytkownik wpisał niewłaściwe dane wejściowe

Przykładowo usuwanie z listy
Robi to na wskaźnikach i nie sprawdza czy wskaźnik pokazuje na element listy lub NIL
przez co dostaje np nieskończoną pętlę