Programowanie i algorytmika


Definicja algorytmu:

Algorytm to skończony zbiór kroków, które prowadzą do rozwiązania określonego problemu.

Cechy algorytmu:
  • Skończoność (musi mieć określoną liczbę kroków)
  • Jednoznaczność (każdy krok musi być precyzyjnie określony)
  • Wejście/Wyjście (przyjmuje dane wejściowe i generuje wynik)
  • Efektywność (kroki powinny być wykonalne w rozsądnym czasie)

Podstawowe techniki algorytmiczne:

  • Podział na podproblemy (Divide and Conquer): Dzielimy problem na mniejsze, rozwiązujemy je i łączymy wyniki (np. sortowanie szybkie, algorytm Karatsuby).
  • Dynamiczne programowanie (Dynamic Programming): Rozwiązujemy złożony problem przez zapamiętywanie wyników podproblemów, aby unikać ich powtarzania (np. problem plecakowy, ciąg Fibonacciego).
  • Algorytmy zachłanne (Greedy Algorithms): Wybieramy lokalnie najlepsze rozwiązanie, oczekując, że doprowadzi do globalnego optimum (np. algorytm Kruskala, Huffmana).
  • Przeszukiwanie w głąb i wszerz (DFS, BFS): Techniki eksploracji grafów i drzew.
  • Metoda siłowa (Brute Force): Przetestowanie wszystkich możliwych rozwiązań.

Struktury danych wspierające algorytmy:

  • Tablice i listy: Przechowywanie danych liniowych.
  • Stosy i kolejki: Obsługa danych w kolejności LIFO i FIFO.
  • Drzewa: Struktura hierarchiczna, np. drzewa binarne, drzewa wyszukiwania (BST).
  • Grafy: Węzły połączone krawędziami (np. do reprezentacji sieci).
  • Haszowanie: Mapowanie danych w celu szybkiego dostępu.

Złożoność algorytmów:

  • Czasowa (Time Complexity): Liczba operacji w zależności od rozmiaru danych wejściowych, np. O(1),O(n),O(n2)O(1),O(n),O(n2).
  • Pamięciowa (Space Complexity): Ilość pamięci używanej przez algorytm.
  • Warto znać notację asymptotyczną:
    • O (najgorszy przypadek),
    • Ω (najlepszy przypadek),
    • Θ (przeciętny przypadek).

Kluczowe algorytmy do nauki na start:

  • Sortowanie: Bąbelkowe (Bubble Sort), przez wstawianie (Insertion Sort), szybkie (Quick Sort), sortowanie przez kopcowanie (Heap Sort).
  • Wyszukiwanie: Liniowe, binarne.
  • Przetwarzanie grafów: BFS, DFS, Dijkstra, algorytmy na MST (Kruskal, Prim).
  • Podstawowe operacje na liczbach: Algorytm Euklidesa, szybkie potęgowanie.

Praktyczne zastosowanie algorytmów:

  • Problemy optymalizacyjne: np. znajdowanie najkrótszej ścieżki w grafie.
  • Przetwarzanie dużych zbiorów danych: np. indeksowanie wyszukiwania w wyszukiwarkach.

Narzędzia do nauki:

  • Platformy do rozwiązywania zadań: LeetCode, HackerRank, Codeforces.
  • Podstawowe książki:
    • "Wprowadzenie do algorytmów" (Cormen, Leiserson, Rivest, Stein)
    • "Algorytmy: Ilustrowany przewodnik" (Aditya Bhargava)