Algorytmy: zakres rozszerzony
Algorytmy z zakresu rozszerzonego informatyki w liceum i technikum w Pythonie: rekurencja, szybkie potęgowanie, rozkład na czynniki pierwsze, jednoczesne minimum i maksimum, sortowanie przez scalanie i szybkie, metoda połowienia, pierwiastek metodą Herona i błędy obliczeń, schemat Hornera, fraktale, podciągi, stos i kolejka z odwrotną notacją polską, metoda zachłanna, programowanie dynamiczne, grafy, szyfrowanie RSA z podpisem elektronicznym i kompresja RLE. Każdy przykład można przejść krok po kroku i oglądać zmienne oraz stos wywołań, a zadania sprawdzają się automatycznie.
Dla kogo: Liceum i technikum, zakres rozszerzony: rekurencja, metody numeryczne, struktury danych, grafy i szyfrowanie w Pythonie, pod maturę. Więcej o kursie
Rekurencja: silnia, potęga i algorytm Euklidesa
Funkcja, która wywołuje samą siebie: warunek końca, stos wywołań, silnia, potęga i algorytm Euklidesa w wersji rekurencyjnej.
Szybkie potęgowanie
Potęga w liczbie mnożeń zależnej od liczby cyfr dwójkowych wykładnika: wersja rekurencyjna i iteracyjna oraz potęgowanie modulo.
Rozkład liczby na czynniki pierwsze
Rozkład przez kolejne dzielenie, dzielniki tylko do pierwiastka, zapis potęgowy i zastosowania: NWD i liczba dzielników.
Jednoczesne wyszukiwanie minimum i maksimum
Minimum i maksimum w jednym przejściu: porównywanie parami (około 3n/2 porównań) i metoda dziel i zwyciężaj.
Sortowanie przez scalanie i sortowanie szybkie
Dwa algorytmy dziel i zwyciężaj: scalanie posortowanych list, sortowanie przez scalanie (merge sort) i sortowanie szybkie (quicksort).
Miejsce zerowe funkcji metodą połowienia
Szukanie miejsca zerowego funkcji ciągłej przez połowienie przedziału: warunek zmiany znaku, dokładność i liczba kroków.
Pierwiastek kwadratowy i błędy obliczeń
Przybliżony pierwiastek metodą Herona, pierwiastek całkowity przez połowienie oraz źródła błędów: zaokrąglenie, przepełnienie i utrata cyfr.
Schemat Hornera i działania w innych systemach liczbowych
Wartość wielomianu schematem Hornera, zamiana z dowolnego systemu na dziesiętny i dodawanie pisemne w systemie dwójkowym i ósemkowym.
Fraktale rekurencyjnie
Figury, których części są pomniejszonymi kopiami całości: zbiór Cantora, trójkąt i dywan Sierpińskiego oraz linijka, rysowane rekurencyjnie znakami w konsoli.
Podciągi o zadanych własnościach
Najdłuższy spójny podciąg niemalejący, maksymalna suma spójnego podciągu (algorytm Kadane) i najdłuższy podciąg rosnący.
Stos, kolejka i odwrotna notacja polska
Struktury danych stos i kolejka, sprawdzanie nawiasów, obliczanie wyrażeń w odwrotnej notacji polskiej (ONP) i zamiana zapisu zwykłego na ONP.
Metoda zachłanna
Wybór najlepszej w danej chwili możliwości: wydawanie reszty, plan zajęć i przykład, w którym metoda zachłanna nie daje najlepszego wyniku.
Programowanie dynamiczne
Zapamiętywanie wyników podproblemów: Fibonacci z pamięcią i metodą wstępującą, najdłuższy wspólny podciąg i wydawanie reszty najmniejszą liczbą monet.
Grafy: przeszukiwanie i najkrótsze drogi
Graf jako lista sąsiedztwa, stopnie wierzchołków, przeszukiwanie wszerz, najkrótsza droga w grafie z wagami (algorytm Dijkstry) i składowe spójności.
Szyfrowanie z kluczem publicznym i podpis elektroniczny
Algorytm RSA na małych liczbach: klucz publiczny i prywatny, odwrotność modulo, szyfrowanie, odszyfrowanie oraz podpis elektroniczny i jego weryfikacja.
Kompresja bezstratna: kodowanie RLE
Kodowanie długości serii (RLE): kompresja i dekompresja napisów, stopień kompresji i dane, dla których metoda się nie opłaca.