Algorytmy i struktury danych: jak się przygotować i nadrobić luki

Jednego programu ASD nie ma. Zależnie od uczelni przedmiot nazywa się „Algorytmy i struktury danych”, „Algorytmy i złożoność” albo jest częścią „Programowania II”, a bywa na pierwszym albo na drugim roku. Gdy porównasz sylabusy różnych uczelni, powtarzają się jednak te same tematy:

• Złożoność obliczeniowa i notacja O.
• Wyszukiwanie liniowe i binarne, sortowanie: od bąbelkowego po quicksort i sortowanie przez scalanie.
• Rekurencja, często też backtracking i programowanie dynamiczne.
• Struktury danych: stos, kolejka, lista jednokierunkowa, drzewa BST, kopce, tablice mieszające, grafy z BFS i DFS.

Na części uczelni ASD prowadzi się w C++ albo w Pythonie, a nie w Javie. Same algorytmy są wtedy takie same, zmienia się tylko składnia. Co dokładnie będzie u ciebie, znajdziesz w sylabusie albo karcie przedmiotu, na wielu uczelniach w systemie USOS. Zajrzyj tam przed początkiem semestru i skreśl tematy, których u ciebie nie ma. Reszta artykułu jest celowo ogólna.

ASD buduje na podstawach programowania, ale ich nie powtarza. Tych pięciu rzeczy prowadzący oczekują od pierwszego tygodnia:

1. Metody z parametrami i wartością zwracaną. Kto myli return z System.out.println, polegnie na każdym zadaniu ze strukturami danych.
2. Tablice i pętle po indeksach. Algorytmy sortowania składają się prawie wyłącznie z nich.
3. Klasy, obiekty, konstruktory i this. Bez nich nie zbudujesz węzła listy ani drzewa.
4. Referencje zamiast wartości. Dwie zmienne mogą wskazywać na ten sam obiekt. Przy obiektach == porównuje referencje, a equals zawartość.
5. Rekurencja. Drzewa i wiele algorytmów sortowania są rekurencyjne. Kto nie potrafi prześledzić stosu wywołań w głowie, szybko traci wątek.

Zanim przeczytasz dalej, zapisz na kartce, co wypisze ten program:

1public class Main {2    static void grow(int[] values) {3        values[0] = 99;4    }5
6    static void reset(int number) {7        number = 0;8    }9
10    static int sum(int n) {11        if (n == 0) {12            return 0;13        }14        return n + sum(n - 1);15    }16
17    public static void main(String[] args) {18        int[] values = {1, 2, 3};19        int number = 7;20        grow(values);21        reset(number);22        String a = new String("Java");23        String b = new String("Java");24        System.out.println(values[0]);25        System.out.println(number);26        System.out.println(a == b);27        System.out.println(a.equals(b));28        System.out.println(sum(4));29    }30}

99
7
false
true
10

Tak to ocenisz:

• 99 dobrze? Wiesz, że tablica jest przekazywana przez referencję. Metoda zmienia oryginał.
• 7 dobrze? Wiesz, że int jest kopiowany. Zmiana w reset zostaje lokalna.
• false i true dobrze? Znasz różnicę między == a equals. Więcej o tym w rozdziale Stringi.
• 10 dobrze? Potrafisz śledzić rekurencję: 4 + 3 + 2 + 1 + 0.

Każda błędna linia wskazuje temat, który warto powtórzyć przed ASD. Takie zadania pojawiają się też często na kolokwiach. Jak ćwiczyć je systematycznie, opisujemy w tekście „Co wypisze program?”: jak ćwiczyć to zadanie przed sprawdzianem.

Licz 30 do 60 minut dziennie, pięć dni w tygodniu. To zmieści się w wakacjach albo w przerwie międzysemestralnej, nawet obok pracy dorywczej.

Tydzień 1: metody, tablice, stringi

Powtórz Metody i rekurencję i pisz codziennie dwie, trzy małe metody: maksimum w tablicy, słowo od tyłu, sprawdzenie, czy liczba jest pierwsza. Ważne, żebyś każdą metodę napisał sam i sprawdził ją dla kilku różnych danych wejściowych.

Tydzień 2: klasy, referencje i dziedziczenie

Przeczytaj Klasy i obiekty, a potem Dziedziczenie i interfejsy. Napisz klasę Node z polem value i referencją next, połącz trzy węzły i wypisz je w pętli. To już jest lista jednokierunkowa w najprostszej postaci. Dla wprawy zbuduj też małą hierarchię, np. Shape z Circle i Rectangle, i licz pola przez interfejs.

Tydzień 3: kolekcje, wyjątki, typy generyczne

Przerób Listy i mapy, a potem Wyjątki i enumy. Policz na przykład słowa w tekście za pomocą Map<String, Integer>. Na ASD często najpierw implementujesz strukturę samodzielnie, a potem porównujesz ją z gotową klasą z biblioteki. Dobrze wtedy wiedzieć, jak działa ArrayList czy HashMap.

Tydzień 4: pierwsze algorytmy i struktury danych

Zacznij od prostych algorytmów sortowania i rekurencji z backtrackingiem. Zaimplementuj sam sortowanie bąbelkowe i przez wstawianie, a potem przejdź je na kartce na tablicy z pięcioma liczbami. Policz przy tym, ile porównań wykonuje każda wersja. To najprostsze wprowadzenie do złożoności. Jeśli zostanie czas, zajrzyj do artykułu Stos, kolejka i lista jednokierunkowa.

Jeśli zauważysz, że luki są większe, cofnij się o krok. Nasz tekst o kolejności nauki Javy pokazuje, co na czym się opiera.

Samo czytanie nie wystarczy. Te zasady robią różnicę:

• Pisz sam. Śledzenie cudzego kodu daje poczucie zrozumienia. Dopiero gdy napiszesz go bez wzoru, wiesz, czy umiesz.
• Najpierw przewiduj, potem uruchamiaj. Przed każdym uruchomieniem zastanów się, co powinno wyjść. Jeśli wynik jest inny, właśnie czegoś się nauczyłeś.
• Znaj typowe błędy. Każdy nasz artykuł kończy się sekcją „Typowe błędy”. Przeczytaj ją, zanim zaczniesz zadania.
• Ćwicz też bez podpowiedzi. Kolokwia i egzaminy z ASD często pisze się na kartce. Wskazówki znajdziesz w tekście Kolokwium z Javy na kartce: jak ćwiczyć pisanie kodu bez IDE.

Jario powstało właśnie z myślą o tej luce. Kurs Podstawy Javy prowadzi w 12 rozdziałach od pierwszego wypisania tekstu do strumieni i typów generycznych. Możesz zacząć od rozdziału, który sprawił ci kłopot w teście. Potem jest kurs Algorytmy w Javie: 8 rozdziałów o wyszukiwaniu, sortowaniu, rekurencji, drzewach, kopcach, haszowaniu i grafach, czyli o tematach z ASD.

Każde zadanie sprawdzasz przyciskiem „Sprawdź”, który uruchamia testy. Gdy utkniesz, tutor AI daje wskazówki małymi krokami i nie zdradza rozwiązania. Zna zadanie, twój kod i wynik testów. Autouzupełnianie w edytorze możesz wyłączyć, jeśli ćwiczysz do kolokwium na kartce. A ponieważ wszystko działa w przeglądarce, nie potrzebujesz zainstalowanego JDK.

Zrób test, zapisz swoje luki i zamknij je według czterotygodniowego planu. Gdy metody, klasy, referencje i rekurencja siedzą, ASD nie jest nowym startem, tylko ciągiem dalszym czegoś, co już umiesz. W Jario możesz od razu w przeglądarce zacząć od rozdziału, którego najbardziej ci brakuje.