BitEdu - liceum i technikum
Informatyka
Zakres podstawowy jest otwarty: wyjaśnienia, kod i ćwiczenia. Po zalogowaniu zapiszesz prace w biurku, zobaczysz również dodatkowe lekcje i treści rozszerzone.
Algorytmy i złożoność
Algorytm Euklidesa i Sito Eratostenesa — klasyka, która działa do dziś
Ponad 2000 lat temu, bez komputerów, Euklides i Eratostenes wymyślili metody, które dziś są fundamentem programowania — to dowód, że proste pomysły mogą być skuteczniejsze niż złożone wzory. Oba algorytmy pojawiają się na maturze rozszerzonej i pokazują pierws...
Binarne wyszukiwanie — jak znaleźć coś szybciej niż inni
Każde wyszukiwanie w Google, YouTube czy Spotify opiera się na binarnej logice podziału — zrozumienie, DLACZEGO dzielenie zakresu na pół jest tak potężne, to jeden z najważniejszych "aha momentów" w nauce algorytmiki, wymagany na maturze rozszerzonej.
Liczby pierwsze i ułamki — po co nam NWD i NWW?
Sprawdzisz pierwszość liczby, skrócisz ułamek i dodasz dwa ułamki przez NWD oraz NWW.
Algorytmy sortowania — bąbelkowe i przez scalanie (dziel i zwyciężaj)
Sortowanie to jedna z najczęściej wykonywanych operacji w informatyce — a strategia "dziel i zwyciężaj" (poznana tu na przykładzie sortowania przez scalanie) to jeden z najważniejszych, uniwersalnych sposobów myślenia o dużych problemach, wymagany na maturze r...
Teksty — porównywanie i szukanie wzorca
Porównasz napisy i znajdziesz wszystkie wystąpienia wzorca, także nakładające się.
Metoda połowienia (bisekcji) — szukanie miejsc zerowych funkcji
To ta sama strategia "dziel na pół", którą poznałeś przy wyszukiwaniu binarnym — tylko zastosowana do zupełnie innego problemu: znajdowania rozwiązań równań, których nie da się łatwo policzyć wzorem. To pokazuje, jak JEDNA uniwersalna idea algorytmiczna działa...
Porządkuj i powtarzaj — wstawianie oraz ciąg Fibonacciego
Wykonasz sortowanie przez wstawianie i obliczysz element ciągu metodą iteracyjną.
Szybkie potęgowanie — jak myśleć o potędze sprytniej, a nie ciężej
Obliczenie 2¹⁰⁰⁰ "na piechotę" to tysiąc mnożeń — szybkie potęgowanie robi to samo w zaledwie 10 krokach. To trzeci, po wyszukiwaniu binarnym i bisekcji, przykład tej samej potężnej idei: dzielenia problemu na pół, tym razem zastosowanej do przyspieszania obli...
Rekurencja w różnych kontekstach — Fibonacci, fraktale i stos wywołań
Rekurencja pojawiała się już wcześniej w tym dziale (wyszukiwanie binarne, MergeSort, szybkie potęgowanie) — czas zrozumieć ją dogłębnie: jak DOKŁADNIE działa "pod maską" (stos wywołań), gdzie w życiu codziennym się pojawia, i dlaczego niektóre jej zastosowani...
Podejście zachłanne — jak wybierać najlepszy krok tu i teraz
Nie każdy problem trzeba rozwiązywać, analizując WSZYSTKIE możliwości — czasem szybsza i prostsza strategia "wybierz to, co teraz wygląda najlepiej" daje bardzo dobre (a czasem najlepsze) wyniki. Zrozumienie, KIEDY takie podejście działa, a kiedy zawodzi, jest...
Programowanie dynamiczne — rozwiązywanie problemów sprytniej
W poprzedniej lekcji widziałeś, że naiwna rekurencja dla ciągu Fibonacciego liczy te same wartości WIELOKROTNIE — dla fib(40) program mógłby liczyć całymi minutami. Programowanie dynamiczne rozwiązuje ten problem, zapamiętując wyniki — i przyspiesza obliczenia...
Stos i kolejka w Pythonie — struktury proste i użyteczne
Historia stron w przeglądarce, kolejka do drukarki, cofanie ostatniego ruchu w grze — wszystko to działa dzięki DWÓM prostym strukturom danych: stosowi i kolejce. To fundament, na którym zbudowane są bardziej złożone struktury (drzewa, grafy) oraz algorytmy pr...
Specjalny element w tablicy — największy, najmniejszy, lider
Znajdowanie największego, najmniejszego elementu czy "lidera" (wartości dominującej) w zbiorze danych to jedne z najczęściej sprawdzanych umiejętności algorytmicznych na maturze — a jednocześnie świetny wstęp do myślenia o złożoności obliczeniowej: to samo zad...
Algorytmy na grafach — sieci społeczne i metro w Paryżu
Google Maps, Facebook, Netflix — wszystkie te usługi "myślą" grafami: siecią połączeń między elementami. Zrozumienie, jak reprezentować i przeszukiwać graf, to jedna z najważniejszych umiejętności na maturze rozszerzonej, łącząca stos i kolejkę (poprzednia lek...
Analiza algorytmów — kompletny przewodnik maturalny (notacja Big-O)
To podsumowanie całego działu Algorytmy i złożoność — narzędzie do FORMALNEJ oceny każdego algorytmu poznanego w poprzednich 11 lekcjach. Na maturze nie wystarczy napisać, że program "działa" — trzeba umieć powiedzieć, JAK DŁUGO będzie działał przy dużych dany...
Schemat Hornera — wielomian bez liczenia każdej potęgi
Zapiszesz schemat Hornera, wykonasz jego ślad i użyjesz go do obliczenia wartości wielomianu.
Rozkład na czynniki pierwsze — dziel i zapisuj
Rozłożysz dodatnią liczbę na czynniki pierwsze i uzasadnisz końcowy krok algorytmu.
Spójne fragmenty — najdłuższy wzrost i największa suma
Odróżnisz podciąg od spójnego fragmentu i znajdziesz najdłuższy niemalejący oraz fragment o największej sumie.
ONP — najpierw kolejność, potem stos
Zamienisz poprawne wyrażenie na ONP i obliczysz je za pomocą stosu.
LCS — wspólny podciąg budowany w tabeli
Zbudujesz tabelę długości LCS i odtworzysz jeden najdłuższy wspólny podciąg.
Dziel i zwyciężaj — min/max oraz quicksort
Prześledzisz rekurencyjne min/max i quicksort oraz odróżnisz ich podział od scalania.
Najkrótsza droga z wagami — algorytm Dijkstry
Zastosujesz Dijkstrę do grafu z nieujemnymi wagami i wskażesz różnicę względem BFS.