Jak się uczyć algorytmów i myślenia algorytmicznego?

Algorytm to sposób rozwiązania problemu w skończonej liczbie kroków

Czy wiesz co to wartość bezwzględna, jak zsumować kilka liczb, pamiętasz jak wykonywać mnożenie i dzielenie pisemne, obliczyć pole koła? – zapewne ta wiedza z czasów podstawówki nadal pozostaje w Twojej głowie i bez trudu przekażesz ją kilkuletniemu dziecku. Teraz musisz nauczyć się myśleć, w jaki sposób swoją wiedzę o sposobie rozwiązania problemu przekazać maszynie – twojemu komputerowi za pomocą algorytmu.

Algorytmy i programowanie – jak zacząć?

Jak się uczyć algorytmów? Czy można nauczyć się logicznego myślenia, myślenia algorytmicznego?

Pytanie zadane w tytule posta pojawia się co jakiś czas w wiadomościach od opublikowania posta Po co programiście algorytmika?. Uświadomiłam sobie, że póki co nie będę wstanie napisać wszystkich postów, które gdzieś tam mam w głowie, a jednocześnie chciałabym, by osoby, które tu wchodzą miały materiały do nauki.

Uważam, że programowanie i algorytmy to naczynia połączone. Rozwiązywanie zadań algorytmicznych jest ważnym etapem nauki programowania (niezależnie czy wybierzecie front-end, back-end, aplikacje mobilne czy inne dziedziny związane z programowaniem), chociaż zgadzam się, że nie jest niezbędne by dostać pierwszą pracę w IT, czy zostać programistą / programistką.

Tak czy inaczej zdania nie zmienię – pozostanę przy tym, że ruszanie komórek mózgowych i rozwiązywanie problemów algorytmicznych jest umiejętnością w pracy programisty ważną.

Jak się uczyć algorytmiki?

Nauka algorytmów może wydawać się czarną magią, mimo że materiałów do nauki algorytmów jest w sieci całkiem sporo. Problem polega na tym, że jeśli nie miało się algorytmów jako przedmiotu na studiach, to nie do końca wiadomo za co się wziąć tyle tej wiedzy jest.

Tutaj, więc posłużę się własnym, prostym sylabusem:

1) Czym są dane i jak je przechowujemy?
2) Struktury: kopiec (stóg), kolejka (FIFO), stos (LIFO), grafy i ich reprezentacje, drzewa
3) Cykl i ścieżka Eulera, cykl Hamiltona
4) Podstawy złożoności obliczeniowej (w tym notacja-O)
5) Algorytmy sortowania:

  • insert sort – przez wstawianie,
  • selection sort – przez wymianę
  • quick sort – szybkie,
  • bubble sort – bąbelkowe,
  • heap sort – stogowe
  • counting sort – przez zlicznanie,
  • merge sort – przez scalanie

6) Programowanie dynamiczne (problem plecakowy)
7) Rekurencja
8) Tablica haszująca

To jest przykład i to bardzo okrojony, ale w moim odczuciu wystarczający by załapać podstawy oraz je przećwiczyć. Oczywiście można wybrać też opcję Learn hard way – i skorzystać z sylabusa Algorytmy i struktury danych „ważniaka” (jest to materiał akademicki, bardzo rozbudowany, ale świetnie opracowany i wśród studentów informatyki wręcz kultowy).

Materiały do nauki algorytmiki?

Oczywiście wszystkie te pojęcia można sobie wygooglować i je po prostu przejść pokolei, przerobić. Dziękuję, temat do zamknięcia.

Niestety, nie są to pojęcia łatwe i czytając definicję z wikipedii może być ciężko je opanować. Znalazłam kilka fajnych źródeł, z których można skorzystać.

Materiały do nauki algorytmów po polsku

Zwróćcie uwagę, że nie jest wymagana umiejętność programowania, aby nauczyć się algorytmiki. Możecie te problemy rozwiązywać nawet układając klocki lego, jak długo pozwala wam to zrozumieć zasadę rozwiązywania problemów.

Tam, gdzie język programowania się przydaje to już implementacja (czyli napisanie kodu, zaprogramowanie) rozwiązania danego problemu.

Algorytmy KhanAcademy – to darmowy, interaktywny kurs podstaw algorytmiki dostępny na platformie Khan Academy. Bardzo przyjemnie przedstawione zagadnienia z przykładami, dużą liczbą ilustracji, zadań do samodzielnego rozwiązania, dodatkowo kurs zawiera wyzwania w formie uzupełnianki kodu JavaScript (nie są konieczne do zrozumienia kolejnych lekcji). Rozwiązanie całości to zapewne od kilku do kilkunastu godzin nauki w zależności od indywidualnego tempa. Dzieląc sobie na 1-2 godzinę dziennie, ze spokojem zrobimy kurs w 2 tygodnie.
zadania z algorytmiki khan academy

Algorytmy.org – strona w całości poświęcona algorytmice. Znajdziemy na niej sporo tematów z tych co podałam powyżej. Były moją stroną startową przez semestr, gdy na uczelni trwały algorytmy i struktury danych.

Od wprowadzenia teorytycznego jako kurs algorymiki, przez struktury danych i algorytmy z przykładami. Jest z czego wybierać. Co najważniejsze na stronie dostępne są do pobrania przykładowe implementacje (głównie w C++).
zadania algorytmy

Algorytmy LO Tarnów – „kurs” na stronie tego liceum sprawia, że szczęka opada. Chapeau bas! Pan mgr Jerzy Wałaszek udostępniając taką bazę zrobił coś wspaniałego dla polskiego Internetu i wszystkich studentów informatyki (znowu materiał, który pomagał zaliczyć algorytmy i struktury danych). Pozazdrościć jego licealistom 😉

► Na blogu pojawił się wpis z teorii grafów, jakby ktoś chciał to tutaj ma reprezentację maszynową grafu.

Książki

Zaletą książek do algorytmów jest forma podania. Właściwie dostajemy jedno źródło i kartka po kartce, algorytm po algorytmie mamy już zaplanowaną kolejność nauki. Dodatkowo w przeciwieństwie do kursów online książka „działa” bez dostępu do Internetu (co jest plusem dla osób, które się często rozpraszają przez inne zakładki np. facebook). Warto pamiętać, że nauka algorytmów z książek powinna mieć też efekt w kodzie.

Algorytmy – ilustrowany przewodnik – książkę tę poleciłam jakiś czas temu mojej znajomej – Paulinie. Wcześniej nie miała styczności z algorytmiką. Sama uczyła się programowania (w tym roku też dostała pracę ❤), poprosiłam ją o krótką recenzję:


Algorytmy ilustrowany przewodnik
Czytana od początku do końca stanowi świetne wprowadzenie do tematu dla osoby, która nie miała wcześniej styczności z algorytmami.
Przykłady są naprawdę proste i łatwo przyswajalne, a do tego bywają całkiem zabawne. To wszystko sprawia, że nauka jest naprawdę przyjemna! Nie mając wcześniej styczności z Pythonem bez problemu zrozumiałam przykłady implementacji z książki, stworzyłam też swój pierwszy algorytm w Ruby i JavaScript. A co najważniejsze – książka pozwoliła mi przygotować się do zadań rekrutacyjnych na stanowisko junior backend developera. Szczerze polecam każdemu, kto chciałby polubić się z algorytmami:)

Wprowadzenie do Algorytmów

Wprowadzenie do algorytmów
Cormen to właściwie klasyk, przynajmniej tak mi się wydaje. Nie zliczę, ile razy słyszałam to nazwisko na pierwszym roku studiów. To książka z kategorii „cięższych lotów”, podręcznikowa. Oczywiście nadal dobra dla początkujących (ale takich, co już jakieś podstawy za sobą mają. Bez nich raczej ciężko będzie przez nią przebrnąć), jak i dla osób, które programują już od dawna, a chcieliby sobie przypomnieć podstawy. Zapewne najbardziej popularna wśród studentów informatyki.

Algorytmy bez tajemnic

Algorytmy bez tajemnic Cormen
Inaczej Cormen w wersji odchudzonej, uproszczonej. Pozycja znacznie lżejsza od „Wprowadzenia do informatyki”. Nie jest zbyt obszerna, zawiera prodstawy algorytmów oraz przykłady na pseudokodzie, wprowadza ciekawe zagadnienia algorytmiczne jak np. kryptografia i kompresja danych.

Materiały do nauki algorytmów po angielsku

Tutaj listę potraktuję trochę po macoszemu, bo wiem, że wolicie listy po polsku.

Po pierwsze aplikacja webowa oraz na telefon, którą już wam polecałam – Brilliant.org. W każdej wolnej chwili – w tramwaju, autobusie, pociągu, możecie czytać artykuły i rozwiązywać quizy dotyczące algorytmiki.
Web: https://brilliant.org/courses/computer-science-algorithms/

Przy tej okazji przypominam też wpis: 5 darmowych aplikacji mobilnych, które uczą programować

Drugi link, który polecam to kurs wideo od Udemy – Coding Interview Bootcamp: Algorithms + Data Structures. Fajny kurs w formie zadań z opisywanymi podejściami do problemu. Jak nazwa wskazuje pomaga przygotować się z algorytmów, które najczęściej pojawiają się w trakcie rekrutacji. Zadania rozwiązywane są w języku Javascript, więc podstawowa znajomość Js jest wymagana. Kurs jako jedyny w zestawieniu jest płatny, jednak ceny Udemy są bardzo przystępne + macie 30 dni na zwrot, nawet jeśli w ciągu tych 30 dni zdążycie skończycie cały kurs (i np. jego poziom was rozczaruje… albo jesteście cebulą) możecie bez problemu anulować zakup.

Kolejna na liście jest platforma edX. Znajdziecie tu darmowe kursy, które mogą wam się przydać:

Powyższe kursy wymagają zapisu, dostęp do materiałów jest darmowy. Gdyby ktoś był zainteresowany EdX proponuje płatne certyfikaty do każdego kursu.

Udacity kurs algorytmy
Obszerny, bo szacowany na ok 4 miesiące, kurs algorytmiki na przykładzie sieci społecznościowych znajdziecie za darmo na stronie Udacity. Wprowadza pojęcia projektowania i analizy algorytmów, które pozwalają odkryć, w jaki sposób ludzie są ze sobą powiązani.

Algorytmy – zadania

Kiedy mamy za sobą podstawy, teorię i w sumie wiemy o co mniej więcej chodzi czas zabrać się za zadania. Rozwiązywać je możecie w dowolonym języku programowania i udostępniać na swoim githubie.

W poście 1000+ zadań do rozwiązania w Pythonie i nie tylko pojawiają się zadania algorytmiczne wraz z rozwiązaniami.

Kolejnym miejscem, gdzie znajdziecie przykładowe zadania to strona AiSD (dr Marta Szachniuk wykładała ten przedmiot dla Bioinformatyki, gdy byłam na pierwszym roku, polecam)

Jeszcze garść zadań z algorytmiki ode mnie:

Zadanie 1
Zaimplementuj dowolne 4 sortowania (np. bubble, merge, heap, quick).

▶ Napisz generator, który zwróci Ci tablice liczb całkowitych, gdzie ciąg danych ułożony jest w sposób losowy, rosnący, malejący.
Przetestuj program dla różnie wygenerowanych ciągów liczb, o różnej liczbie elementów i sposobie ułożenia w kolejności.
Porównaj czasy działania algorytmów sortowania. Który jest wg. Ciebie najlepszy? Są to algorytmy o znanej złożoności obliczeniowej, czy twoje testy pokrywają się z oczekiwanym wynikiem?

Zadanie 2
Zaimplementuj reprezentacje grafu: lista następników, macierz sąsiedztwa.
Zaimplementuj algorytmy przechodzenia grafu wszerz (BFS) oraz w głąb (DFS).

Zadanie 3
Zaimplementuj algorytm znajdujący pierwszy cykl Hamiltona w grafie nieskierowanym.

Zadanie 4
Zaimplementuj algorytm znajdujący pierwszy cykl Eulera w grafie nieskierowanym.

Zadanie 5
Zaimplementuj program rozwiązujący 0-1 problem plecakowy:
– algorytmem pełnego przeszukania (brute force)
– algorytmem programowania dynamicznego
– wybrany algorytm zachłanny

▶ Wygeneruj n zbiór przedmiotów (waga, cena) dla 10 różnych wartości n i przetestuj swój program.

W razie problemów z rozwiązaniami w Pythonie wpadajcie na grupę Python: nauka.

Udało się rozwiązać zadania? – Pochwalcie się w komentarzu pod postem! 🙂