MITP

Algorytm

skończony, jednoznaczny ciąg kroków prowadzących do rozwiązania danego problemu.

Cechy dobrego algorytmu

Poprawność, Skończoność, Jednoznaczność, Efektywność, Deterministyczność

Bubble Sort

Porównuj sąsiednie elementy i zamieniaj je miejscami, jeśli są w złej kolejności. Powtarzaj aż zbiór będzie posortowany Czasowa: O(n²), Pamięciowa: O(1) (in-place)

Selection Sort

Znajduj najmniejszy element i wstawiaj go na początek – powtarzaj dla pozostałychCzasowa: O(n²), Pamięciowa: O(1)

Merge Sort

Dziel tablicę na dwie połowy, sortuj rekurencyjnie, a następnie scal wyniki w jeden posortowany zbiór. Czasowa O(nlogn), pamięciowa O(n)

Quick Sort

Wybierz pivot, podziel dane na mniejsze/większe od pivota, sortuj obie części rekurencyjnie. Czasowa O(n^2), pamięciowa O(logn) rekurencja

Wyszukiwanie w drzewie binarnym

Wykorzystuje strukturę drzewa – każdy węzeł ma element mniejszy po lewej i większy po prawej. Najgorzej O(n) gdy drzewo niezbalansowane, pamięciowe O(logn)

Drzewo

Drzewo to hierarchiczna struktura danych. Składa się z węzłów połączonych krawędziami. Pierwszy węzeł to korzeń, a te bez potomstwa (dzieci) to liście. Węzły nadrzędne to rodzice, a podrzędne to synowie. Węzły z tym samym rodzicem to rodzeństwo.

Wskaźnik

iterowanie elementów w tablicach, przydzielanie nowych obiektów na stercie, przekazywanie zmiennych do funkcji, przekazywanie funkcji jako argumentów

semantyka wskaźników

może być pusty, można przesunąć na inny adres, Można wykonywać na nim arytmetykę

semantyka referencji

Musi być zainicjalizowana, Nie może być „pusta”, Jest nieodłączalna - raz przypisujemy

Wskaźnik na funkcję

to zmienna, która przechowuje adres punktu wejścia do danej funkcji.

do czego służą wskaźniki na funkcję

Pozwala to na wybór funkcji, która ma się wykonać, w trakcie działania programu (runtime). Możesz np. mieć tablicę wskaźników do różnych algorytmów i przełączać się między nimi.

callback

Callback to wywoływanie funkcji przez inną funkcję. Zapewnia odseparowanie logiki oraz większą elastyczność kodu, ponieważ ta sama funkcja wywołująca może używać różnych callbacków.

zwracanie funkcji

Zwracać pojedynczą wartość (np. return wynik) ● Zwracać wiele wartości (np w pythonie return z wieloma zmiennymi po przecinku) ● Zwracać struktury lub obiekty bądź też słowniki ● Zwracać funkcje (funkcja wyższego rzędu)

Rekurencja

Rekurencja to technika, w której funkcja wywołuje samą siebie, aby rozwiązać problem metoda dzielenia na mniejsze podproblemy. Każde wywołanie rekurencyjne redukuje problem, aż do osiągnięcia warunku bazowego (punktu zakończenia)

Programowanie funkcyjne (FP – Functional Programming)

Funkcje wyższego rzędu -funk 2) Czyste funkcje ○ x_efeUbocz ○ sameArg=sameWynik ○ Ułatwiają testowanie i równoległość obliczeń 3) Unikanie efektów ubocznych ○ Efekt uboczny to zmiana stanu zewnętrznego (np. zapis do pliku, modyfikacja globalnej zmiennej).

Wyjątek

zdarzenie podczas wykonywania programu, które zakłóca normalny przebieg programu Mechanizmy obsługi wyjątków w C++ i Python

Rodzaje błędów

błąd kompilacji(semantyczny i składni), linkowania, runtime, logiczne

Wyjątek

zdarzenie podczas wykonywania programu, które zakłóca normalny przebieg programu

C++: Wyjątki

Służą do obsługi błędów runtime. Składnia: try (blok testowy), throw (zgłoszenie obiektu), catch (przechwycenie). Zasada: Łap przez referencję (const std: exception& e). Brak finally – używaj RAII i destruktorów do sprzątania zasobów.

C++: Hierarchia (najważniejsze) wyjątków

std: exception -> bad_alloc, bad_cast, logic_error (invalid_argument, out_of_range), runtime_error (overflow_error, range_error).

Python: Wyjątki

Mechanizm obsługi błędów i przepływu. Składnia: try, except (łapanie), else (brak błędu), finally (zawsze wykonaj). Zasada: EAFP (lepiej prosić o wybaczenie niż o pozwolenie). raise zgłasza błąd.

Python: Hierarchia (najważniejsze)

BaseException -> Exception -> ArithmeticError (ZeroDivisionError), LookupError (IndexError, KeyError), TypeError, ValueError, FileNotFoundError.

Programowanie obiektowe

sposób tworzenia programów jako zbioru współpracujących ze sobą obiektów, które łączą dane (pola) i zachowania (metody).

Refaktoryzacja

Refaktoryzacja: ulepszanie struktury bez zmiany działania. Techniki: Wyodrębnienie metody (podział długich funkcji). Zmiana nazw na opisowe. Usuwanie duplikacji (DRY). Inline: zastąpienie zmiennej/metody jej treścią, gdy jest zbędna.

Profiler

Profiler: narzędzie do analizy wydajności programu. Zastosowanie: Mierzenie czasu wykonania funkcji (CPU). Wykrywanie wycieków i zużycia pamięci (RAM). Znajdowanie "wąskich gardeł" (bottlenecks). Pomaga optymalizować najwolniejsze fragmenty kodu.

Szablony

kod generyczny, typy określane przy kompilacji. Funkcje: jedna definicja dla wielu typów (np. sort). Klasy: uniwersalne kontenery (np. vector<T>).

Projektowanie: Model inkluzyjny

Zasada: Szablony muszą być w całości zdefiniowane w plikach nagłówkowych (.h). Dlaczego: Kompilator musi widzieć "przepis" w każdym pliku, w którym używasz szablonu, aby wygenerować kod dla konkretnego typu (np. dla int).

Projektowanie: Duck Typing

Zasada: Szablon nie wymaga dziedziczenia, a jedynie konkretnych operacji. Logika: "Jeśli coś kwacze jak kaczka, jest kaczką". Jeśli w szablonie używasz a + b, to zadziała on z każdym typem, który ma zdefiniowany operator dodawania.

Projektowanie: Specjalizacja

Zasada: Tworzenie osobnej wersji szablonu dla specyficznego typu danych. Cel: Optymalizacja lub zmiana błędnego zachowania (np. inny sposób porównywania dla liczb, a inny dla wskaźników tekstowych char*).

Preprocessing

Wstępny etap budowy. Preprocesor przetwarza dyrektywy zaczynające się od #. Działania: Wklejanie zawartości plików (#include), podmienianie makr (#define) oraz usuwanie komentarzy. Wynikiem jest czysty kod źródłowy C++.

Kompilacja

Proces zamiany kodu źródłowego na kod maszynowy (asembler). Działania: Analiza składniowa, semantyczna i generowanie kodu dla konkretnej architektury procesora. Wynikiem jest plik obiektowy (. o lub. obj) z kodem binarnym.

Konsolidacja (Linkowanie)

Łączenie wielu plików obiektowych i bibliotek w jeden plik wykonywalny (. exe,. elf). Działania: Rozwiązywanie symboli (łączenie wywołań funkcji z ich definicjami) i ustalanie adresów w pamięci. Tu powstają błędy typu „unresolved external”.

Optymalizacja

lepszanie kodu przez kompilator (flagi -O1, -O2, -O3). Techniki: Inline (wstawianie treści funkcji), usuwanie martwego kodu, rozwijanie pętli. Cel: Zmniejszenie rozmiaru pliku lub zwiększenie szybkości działania programu.

Struktura pliku obiektowego (format ELF)

Nagłówek: typ, architektura. Sekcje:. text (kod),. data (zmienne),. bss (niezainicj.),. rodata (stałe),. symtab (symbole),. rel (relokacja). Tab. nagłówków sekcji: opis rozmiarów/offsetów. Segmenty: opis ładownia do RAM.