--- # SKRYPT MÓWIONY — Obrona Magisterska --- \newpage ## PYTANIE 1 · Automaty i klasy języków (AISDI) **Pytanie:** *Porównać „siłę wyrazu" automatu skończonego, automatu ze stosem oraz maszyny Turinga. Jakie klasy języków rozpoznaje każdy z nich?* --- ### Co mówię Dobrze, tutaj chodzi o hierarchię Chomsky'ego, czyli o to, jak kolejne automaty mają coraz większą moc obliczeniową dzięki temu, że mają coraz lepszą pamięć. [TABLICA: rysuj „schodki" albo kółka zagnieżdżone — od najmniejszego do największego] Zaczynam od najsłabszego. **Automat skończony** — on nie ma żadnej pamięci poza swoim stanem. Może rozpoznawać języki regularne, czyli takie, które da się opisać wyrażeniem regularnym. Przykład — sprawdzanie czy identyfikator w kodzie jest poprawny. Ale nie poradzi sobie z czymś, co wymaga zliczania — na przykład z językiem a^n b^n, bo nie ma jak zapamiętać ile było tych „a". [TABLICA: napisz FA → Regularne, pamięć: brak] Następny krok — **automat ze stosem**. Tutaj dodajemy stos, i to wystarczy, żeby obsłużyć nawiasy, rekurencję w gramatykach. Rozpoznaje języki bezkontekstowe — to jest ten poziom, na którym działają parsery języków programowania. Poradzi sobie z a^n b^n, bo na stos odkłada „a" i zdejmuje przy „b". Ale nie da rady z a^n b^n c^n, bo stos zostaje zużyty po dwóch pierwszych grupach. [TABLICA: dopisz PDA → Bezkontekstowe, pamięć: stos LIFO] Na końcu — **maszyna Turinga**. Ma nieskończoną taśmę z odczytem i zapisem. Może się cofać, może pisać w dowolnym miejscu. Rozpoznaje języki rekurencyjnie przeliczalne, czyli — zgodnie z tezą Churcha-Turinga — wszystko to, co w ogóle da się obliczyć. [TABLICA: dopisz TM → Rek. przeliczalne, pamięć: taśma ∞ R/W] Więc mamy taką hierarchię inkluzji: regularne ⊂ bezkontekstowe ⊂ kontekstowe ⊂ rekurencyjnie przeliczalne. Każdy następny automat rozpoznaje ściśle więcej. Warto wspomnieć, że jest jeszcze **LBA** — automat z ograniczoną taśmą — między PDA a TM. On rozpoznaje języki kontekstowe, takie jak a^n b^n c^n. Ale nie jest wprost wymieniony w pytaniu. ### Jeśli mam jeszcze czas / pytają dalej Ciekawa różnica: dla automatów skończonych — determinizm i niedeterminizm dają tę samą moc. Każdy NFA da się przekształcić na DFA. Dla PDA — nie: niedeterministyczny PDA rozpoznaje więcej niż deterministyczny. A dla maszyn Turinga — znowu równoważne, pod względem mocy, choć nie szybkości. ### Spodziewane pytania dodatkowe **„Podaj kontrprzykład — co łamie FA?"** → a^n b^n — trzeba liczyć, FA nie ma pamięci, nie da rady. **„Czym się różni DFA od NFA?"** → NFA może być w wielu stanach naraz, ale każdy NFA da się zamienić na DFA — kosztem wykładniczej liczby stanów. **„Co to jest teza Churcha-Turinga?"** → Że maszyna Turinga opisuje wszystko, co intuicyjnie rozumiemy jako „obliczanie". Nie jest to twierdzenie matematyczne — to teza filozoficzna. --- \newpage ## PYTANIE 2 · Algorytmy najkrótszej ścieżki (AISDI) **Pytanie:** *Omówić i porównać algorytmy: Dijkstry, Bellmana-Forda, A\*.* --- ### Co mówię Trzy algorytmy, każdy rozwiązuje problem najkrótszej ścieżki, ale w innych warunkach i innym podejściem. [TABLICA: narysuj prosty graf ważony — 5 wierzchołków, parę krawędzi z wagami] **Dijkstra** — algorytm zachłanny. Startujemy z jednego źródła, trzymamy kolejkę priorytetową wierzchołków po aktualnej odległości i zawsze przetwarzamy ten o najmniejszej. Relaksujemy jego krawędzie. Kluczowy warunek — **wagi muszą być nieujemne**, bo raz przetworzony wierzchołek już nie jest odwiedzany ponownie. Złożoność z kopcem — O((V+E) log V). **Bellman-Ford** — podejście z programowania dynamicznego. Robimy V−1 iteracji, w każdej relaksujemy wszystkie krawędzie. Dlaczego V−1? Bo najdłuższa ścieżka prosta ma V−1 krawędzi. Główna zaleta — **obsługuje ujemne wagi** i potrafi **wykryć cykl ujemny**: jeśli po V−1 iteracjach dalej da się poprawić jakąś odległość, to jest cykl. Złożoność — O(V·E), wolniejszy od Dijkstry. **A\*** — to w zasadzie Dijkstra z heurystyką. Zamiast przetwarzać wierzchołek o najmniejszej odległości g(n), bierze ten o najmniejszym f(n) = g(n) + h(n), gdzie h to oszacowanie ile jeszcze zostało do celu. Jeśli heurystyka jest dopuszczalna — czyli nie przeszacowuje — to A\* jest optymalny. Typowe zastosowanie — nawigacja, gry. [TABLICA: napisz krótką tabelkę] | Algo | Podejście | Ujemne wagi | Złożoność | |------|-----------|-----------|-----------| | Dijkstra | Zachłanny | NIE | O((V+E)log V) | | Bellman-Ford | DP | TAK | O(VE) | | A* | Heuryst. | NIE | Zależy od h | ### Spodziewane pytania dodatkowe **„Dlaczego Dijkstra nie działa z ujemnymi wagami?"** → Bo po przetworzeniu wierzchołka zakładamy, że mamy już najkrótszą ścieżkę do niego. Ujemna waga może później dać lepszą trasę — ale algorytm już tego nie sprawdzi. **„Co to znaczy, że heurystyka jest dopuszczalna?"** → Że h(n) ≤ faktyczny koszt z n do celu. Nigdy nie przeszacowuje. Przykład — odległość po linii prostej na mapie. **„Który jest najszybszy w praktyce?"** → A\* z dobrą heurystyką, bo eksploruje mniej wierzchołków. Dijkstra exploruje we wszystkich kierunkach, A\* kieruje się ku celowi. --- \newpage ## PYTANIE 3 · Redundancja i normalizacja (BD2) **Pytanie:** *Omówić zagadnienia redundancji i normalizacji w relacyjnej bazie danych.* --- ### Co mówię Redundancja to powtarzanie tych samych danych w wielu miejscach. Problem nie jest sam fakt powtórzenia, tylko **anomalie**, jakie powoduje. Są trzy rodzaje anomalii. **Wstawiania** — nie mogę dodać danych bez podania niepotrzebnych powiązań. **Usuwania** — kasuję rekord i tracę informację, która nie powinna zniknąć. **Modyfikacji** — zmieniam jedno pole, ale muszę to zrobić w dziesięciu miejscach, bo dane są powielone. [TABLICA: przykład — tabela Student-Kurs-Wydział, gdzie NazwaWydziału się powtarza] Rozwiązaniem jest **normalizacja** — rozbijamy tabelę na mniejsze, eliminując zależności, które powodują redundancję. Postacie normalne idą tak: 1NF → 2NF → 3NF → BCNF → dalej. Jest taka mnemotechnika: **„Klucz, cały klucz i tylko klucz — tak mi dopomóż Codd."** - **1NF** — wartości atomowe, istnieje klucz. Czyli żadnych list w komórkach. - **2NF** — każdy atrybut wtórny zależy od **całego** klucza, nie od jego części. To dotyczy kluczy złożonych. - **3NF** — brak zależności przechodnich. Jeśli A → B → C, to C nie powinno być w tej samej tabeli co A. - **BCNF** — dla każdej zależności funkcyjnej lewa strona musi być nadkluczem. Silniejsza niż 3NF. W praktyce — 3NF albo BCNF to taki „standard" w systemach transakcyjnych. Dalsze postacie — 4NF, 5NF — dotyczą zależności wielowartościowych i łączeniowych, ale stosuje się je rzadko. Jest też **denormalizacja** — świadome dodawanie redundancji dla wydajności, żeby uniknąć kosztownych JOIN-ów. Typowe w hurtowniach danych, OLAP. ### Spodziewane pytania dodatkowe **„Podaj przykład naruszenia 2NF."** → Tabela (StudentID, KursID, NazwaKursu): NazwaKursu zależy tylko od KursID, nie od całego klucza złożonego. **„Jaka jest różnica między 3NF a BCNF?"** → 3NF pozwala na zależności, gdzie lewa strona nie jest nadkluczem, jeśli prawa strona jest atrybutem pierwszym. BCNF tego nie akceptuje. **„Kiedy denormalizować?"** → Gdy zapytania analityczne wymagają wielu JOIN-ów i opóźnienie jest nieakceptowalne. Obniżamy normalizację na rzecz wydajności odczytu. --- \newpage ## PYTANIE 4 · Baza danych jako fundament systemów (BD2) **Pytanie:** *Dlaczego baza danych stanowi dobry fundament do budowy wielu systemów informatycznych?* --- ### Co mówię To pytanie jest trochę bardziej koncepcyjne. Chodzi o to, dlaczego baza danych jest tak dobrym fundamentem — w porównaniu z alternatywami typu pliki, pamięć operacyjna, własne rozwiązania. Powodów jest kilka i pójdę po kolei. Po pierwsze — **transakcyjność ACID**. Atomowość gwarantuje, że operacja się wykona w całości albo wcale. Spójność — że baza przechodzi ze spójnego stanu w spójny. Izolacja — równoległe operacje sobie nie przeszkadzają. Trwałość — raz zapisane dane przetrwają awarię. To jest fundament — bez tego każdy system musiałby sam implementować te gwarancje. Po drugie — **niezależność danych**. Architektura ANSI/SPARC wyróżnia trzy poziomy: fizyczny, logiczny, zewnętrzny. Zmiana indeksów czy partycjonowania nie wpływa na logikę aplikacji. To pozwala na niezależną ewolucję systemu. Po trzecie — **współbieżność**. Baza ma wbudowane mechanizmy — blokady, MVCC — żeby wielu użytkowników mogło pracować jednocześnie. Bez bazy — musielibyśmy to implementować sami. Po czwarte — **integralność**. Klucze obce, CHECK-i, triggery — baza sama pilnuje reguł biznesowych na poziomie danych. Po piąte — **optymalizator zapytań**. Piszę CO chcę, a baza sama decyduje JAK to zrealizować — wybiera indeksy, plany wykonania. To ogromna oszczędność pracy. Jeszcze bezpieczeństwo — GRANT/REVOKE, role, szyfrowanie. Skalowalność — replikacja, sharding. I SQL jako standardowy interfejs — nie wymyślam protokołu od zera. Podsumowując — baza danych daje zestaw rozwiązanych problemów, które każdy system potrzebuje. Zamiast budować od zera, korzystamy z dojrzałego narzędzia. ### Spodziewane pytania dodatkowe **„Co to MVCC?"** → Multi-Version Concurrency Control. Zamiast blokować, baza trzyma wiele wersji wiersza. Czytający widzi starszą wersję, piszący tworzy nową. Nie blokują się nawzajem. **„A kiedy baza NIE jest dobrym fundamentem?"** → Kiedy mamy dane niestrukturalne, wymagania ultra-niskiej latencji, albo dane w grafie — wtedy rozwiązania specjalizowane (timeseries DB, document stores, graph DB) mogą być lepsze. --- \newpage ## PYTANIE 5 · Kategorie STL (PROI) **Pytanie:** *Omówić główne kategorie elementów biblioteki STL.* --- ### Co mówię STL ma cztery główne filary — i kluczowe jest to, jak one ze sobą współpracują. [TABLICA: narysuj schemat] KONTENERY ←→ ITERATORY ←→ ALGORYTMY ↑ FUNKTORY **Kontenery** — przechowują dane. Mamy sekwencyjne — vector, list, deque. Asocjacyjne oparte na drzewach R-B — set, map — z O(log n). Nieuporządkowane oparte na hashach — unordered_set, unordered_map — z O(1) średnio. I adaptery — stack, queue, priority_queue — ograniczony interfejs. **Iteratory** — to uogólnione wskaźniki. Są w hierarchii: od Input/Output, przez Forward, Bidirectional, po Random Access. Vector daje Random Access, list — Bidirectional, forward_list — Forward. Iterator mówi algorytmowi JAK przechodzić po kontenerze. **Algorytmy** — sort, find, transform, copy, accumulate. Kluczowa cecha — **operują na iteratorach, nie na kontenerach**. Nie obchodzi ich, czy to vector, list czy deque. **Funktory** — obiekty funkcyjne, które parametryzują algorytmy. Klasyczne: less, greater. W C++11 — lambdy. I to jest ta genialna architektura STL — jest **ortogonalna**. Mam M kontenerów i N algorytmów — potrzebuję M+N komponentów, nie M×N. Bo kontenery i algorytmy komunikują się przez iteratory. Ten sam sort działa na vectorze i na deque — wystarczy że mają Random Access iterator. [TABLICA: sort(v.begin(), v.end()) — ten sam algorytm, różne kontenery] ### Spodziewane pytania dodatkowe **„Kiedy wybrać vector, a kiedy list?"** → Vector domyślnie — contiguous memory, cache-friendly, Random Access. List — gdy dużo wstawiania/usuwania w środku, bo to O(1) z iteratorem, ale cache-unfriendly. W praktyce — vector wygrywa prawie zawsze. **„Co to jest ortogonalność w kontekście STL?"** → To, że kontener i algorytm nie muszą o sobie wiedzieć. Łączy je iterator — wspólny interfejs. Dodanie nowego kontenera nie wymaga zmian w algorytmach. **„Czym się różni funktor od lambdy?"** → Funktor to klasa z operatorem(), lambda to skrócona składnia, która pod spodem generuje analogiczną klasę. W C++11+ — praktycznie to samo. --- \newpage ## PYTANIE 6 · Reużywalność kodu w OOP (PROI) **Pytanie:** *Omówić metody reużywalności kodu i struktur danych w obiektowych językach programowania.* --- ### Co mówię Mamy kilka głównych mechanizmów, ale zacznę od dwóch najważniejszych — i od tego, jak się je porównuje. **Dziedziczenie** — relacja „jest" (is-a). Klasa pochodna przejmuje interfejs i implementację bazowej. Pozwala na polimorfizm — virtual, override. Wada — silne wiązanie, krucha klasa bazowa, i diamond problem przy wielodziedziczeniu. **Kompozycja** — relacja „zawiera" (has-a). Zamiast dziedziczyć, obiekt ma pole innego typu. Stack nie JEST wektorem — Stack ZAWIERA wektor. Luźniejsze wiązanie, lepsza enkapsulacja, łatwiejsze testowanie. I tutaj zasada z GoF-a, którą trzeba znać: **„Favor composition over inheritance"**. Kompozycja jest preferowana. Dziedziczenie — tylko gdy mam rzeczywiście relację is-a i potrzebuję polimorfizmu. **Programowanie generyczne** — szablony w C++, generics w Javie. Piszę kod raz, działa dla wielu typów. Przykład — cała STL jest oparta na templates. To jest reużywalność na poziomie algorytmów i struktur. **Interfejsy i klasy abstrakcyjne** — kontrakt bez implementacji. W Javie `interface`, w C++ czysta klasa wirtualna. Pozwala na strategy pattern, dependency injection, testowanie przez mocki. **Wzorce projektowe** — reużywalne rozwiązania problemów. GoF opisał 23 wzorce. Strategy, Observer, Factory, Decorator — to nie jest kod do kopiowania, ale sprawdzone schematy. No i oczywiście **biblioteki i frameworki** — najoczywistsza forma reużywalności na większą skalę. ### Spodziewane pytania dodatkowe **„Co to problem diamentu?"** → Gdy klasa dziedziczy po dwóch klasach, które mają wspólną bazę. W C++ — rozwiązanie przez `virtual inheritance`. W Javie — nie ma wielodziedziczenia klas, są interfejsy. **„Podaj przykład, kiedy dziedziczenie jest lepsze od kompozycji?"** → Gdy potrzebuję polimorfizmu — np. mam kolekcję Shape* i wywołuję draw() — list, circle, rectangle. Każdy rysuje się inaczej, ale interfejs jest wspólny. **„Czym jest dependency injection?"** → Przekazuję zależności z zewnątrz zamiast tworzyć je wewnątrz klasy. To ułatwia testowanie i wymianę implementacji. --- \newpage ## PYTANIE 7 · DNS i caching (SKM) **Pytanie:** *Które serwery DNS zyskują najwięcej na cachingu? Jakie znasz rodzaje serwerów DNS?* --- ### Co mówię Zacznę od tego, jakie są rodzaje serwerów DNS, bo to kontekst do odpowiedzi na główne pytanie. [TABLICA: rysuj piramidę DNS] Na samej górze — **Root Servers**. Jest ich 13 logicznych — od A do M — ale fizycznie setki, rozproszonych przez anycast. Poniżej — **serwery TLD** — odpowiedzialne za .com, .pl, .org. Dalej — **Authoritative** — mają faktyczne rekordy konkretnych domen. Mam primary, który jest edytowalny, i secondary, który jest kopią. Po stronie klienta mamy **recursive resolver** — to jest ten, który wykonuje pełne rozwiązywanie nazw. ISP-owski resolver, Google 8.8.8.8, Cloudflare 1.1.1.1. I na samym końcu — **stub resolver** w systemie operacyjnym, który po prostu pyta recursive resolver. [TABLICA: narysuj strzałki: Klient → Recursive → Root → TLD → Authoritative] Teraz — **które serwery zyskują najwięcej na cachingu?** Odpowiedź: **root i TLD** — i to zdecydowanie. Dlaczego? Rozmiar piramidy. Jest tylko 13 logicznych root serwerów, a zapytań o DNS są miliardy dziennie. **Bez cache** — każde zapytanie o cokolwiek musiałoby przejść przez root, potem TLD. Z cache — resolver pyta root RAZ o .com, cachuje ten referral na 48 godzin albo dłużej, i przez ten czas wszystkie zapytania o .com idą bezpośrednio do TLD bez angażowania roota. TTL-e rootów to 48 godzin do 7 dni! TLD — 24 do 48 godzin. Dzięki temu redukcja ruchu do root serwerów to z prawie 100% do ułamka procenta. Gdyby nie caching, infrastruktura roota nie wytrzymałaby obciążenia. ### Spodziewane pytania dodatkowe **„Co to anycast?"** → Jeden adres IP rozgłaszany z wielu lokalizacji. Klient łączy się z najbliższą instancją — na podstawie routingu BGP. Wszystkie root servery używają anycast. **„Co to TTL?"** → Time To Live — ile sekund rekord DNS może być trzymany w cache. Po upłynięciu trzeba odpytać ponownie. **„Co się stanie jak wyłączysz cache w resolverze?"** → Ogromny wzrost ruchu do root i TLD serwerów. Każde zapytanie zaczyna od góry piramidy. W skali — to zatopiłoby infrastrukturę. --- \newpage ## PYTANIE 8 · TCP Three-Way Handshake (SKM) **Pytanie:** *Cel, interpretacja numerów sekwencyjnych, wartość początkowa ISN.* --- ### Co mówię TCP Three-Way Handshake to mechanizm nawiązywania połączenia. Trzy kroki. [TABLICA: rysuj diagram] Klient Serwer |--- SYN, seq=x ---→| |←- SYN+ACK, seq=y, ack=x+1 -| |--- ACK, seq=x+1, ack=y+1 →| Krok pierwszy — klient wysyła **SYN** z losowym numerem sekwencyjnym x. Krok drugi — serwer odpowiada **SYN+ACK**: swoim numerem y i potwierdzeniem x+1. Krok trzeci — klient potwierdza: ACK z ack=y+1. **Cel?** Trzy rzeczy. Nawiązanie obustronne — obie strony się zgadzają na komunikację. Synchronizacja numerów ISN — obie strony znają początkowy numer drugiej. I uzgodnienie parametrów — w opcjach TCP lecą MSS, Window Scale, SACK. Teraz — **numery sekwencyjne**. SEQ to numer pierwszego bajtu danych w segmencie. Nie numerujemy segmentów, numerujemy bajty! Jeśli sending seq=100 i 50 bajtów danych, to następny segment zacznie od 150. **Numery potwierdzenia** — ACK to numer **następnego oczekiwanego bajtu**. Jest kumulatywny — potwierdza wszystko do tego numeru. Jest też SACK — selective ACK — pozwala potwierdzać niesąsiednie bloki. **ISN** — wartość początkowa. Nie zaczyna od zera! Dwa powody. Po pierwsze — **bezpieczeństwo**: gdyby ISN był zero albo przewidywalny, atakujący mógłby zgadnąć numer sekwencyjny i przejąć sesję. Po drugie — unikanie kolizji z pakietami z poprzednich połączeń. Oryginalny RFC 793 mówił o timerze co 4 mikrosekundy. Nowszy RFC 6528 — ISN jest generowany kryptograficznie z adresów, portów i tajnego klucza. ### Spodziewane pytania dodatkowe **„Dlaczego trzy kroki, a nie dwa?"** → Bo obie strony muszą potwierdzić swój ISN. W dwóch krokach serwer nie wie, czy klient odebrał jego ISN. **„Co to SYN flood?"** → Atak DoS — wysyłam tysiące SYN-ów bez dokończenia handshake'u. Serwer trzyma pół-otwarte połączenia, aż wyczerpie zasoby. Obrona — SYN cookies. --- \newpage ## PYTANIE 9 · Procesy i wątki (SOI) **Pytanie:** *Budowa, szybkość, zastosowanie. Problemy komunikacji i synchronizacji.* --- ### Co mówię **Proces** to program w trakcie wykonania. Ma własną przestrzeń adresową — oddzielny kod, dane, stos, heap. Procesy są od siebie **izolowane**. Jeden spadnie — drugi dalej działa. **Wątek** to lekka jednostka wykonania **wewnątrz** procesu. Współdzieli z procesem kod, dane globalne, heap, otwarte pliki. Ma **prywatny** stos i rejestry. [TABLICA: narysuj — dwa prostokąty-procesy, w jednym dwa mniejsze prostokąty-wątki z własnymi stosami, ale wspólnym heapem] Główna różnica praktyczna — **szybkość**. Tworzenie procesu to milisekundy — trzeba kopiować tablicę stron, deskryptory. Tworzenie wątku — mikrosekundy. Przełączanie kontekstu procesu — kosztowne, bo wymaga TLB flush. Przełączanie wątku — znacznie szybsze, bo nie zmienia się przestrzeni adresowej. **Komunikacja** — i tu jest różnica. Między procesami — IPC: pipe, shared memory, message queue, sockety. Między wątkami — po prostu współdzielona pamięć. Ale ta prostota ma cenę. **Problemy synchronizacji:** **Race condition** — dwa wątki modyfikują tę samą zmienną, wynik zależy od kolejności — niedeterminizm. **Deadlock** — zakleszczenie. Wątek A trzyma zasób 1 i czeka na 2, wątek B trzyma 2 i czeka na 1. Cztery warunki Coffmana: mutual exclusion, hold and wait, no preemption, circular wait. Złam jeden — deadlocka nie ma. **Starvation** — zagłodzenie, wątek nigdy nie dostaje zasobu. Mechanizmy rozwiązań: mutex, semafor, monitor, condition variable, spinlock, barrier. Lubię tę analogię: proces to mieszkanie — ma adres, własne ściany. Wątek to pokój — współdzieli kuchnię i łazienkę z innymi pokojami. ### Spodziewane pytania dodatkowe **„Czym jest mutex a czym semafor?"** → Mutex — binarny zamek, tylko jeden wątek wchodzi do sekcji krytycznej. Semafor — licznik: pozwala na N jednoczesnych dostępów. Mutex to w zasadzie semafor z N=1, ale semantycznie — mutex ma właściciela. **„Co to jest TLB?"** → Translation Lookaside Buffer — cache translacji adresów wirtualnych na fizyczne. Przy zmianie procesu — trzeba go wyczyścić, bo nowy proces ma inną tablicę stron. --- \newpage ## PYTANIE 10 · Zarządzanie pamięcią (SOI) **Pytanie:** *Problemy i mechanizmy. Stronicowanie vs segmentacja.* --- ### Co mówię Zarządzanie pamięcią musi rozwiązać kilka problemów. **Fragmentacja** — zewnętrzna, gdy wolna pamięć jest porozrzucana, i wewnętrzna, gdy przydzielony blok jest większy niż potrzeba. **Ochrona** — proces nie może czytać pamięci innego procesu. **Relokacja** — program musi działać pod różnymi adresami. **Współdzielenie** — biblioteki współdzielone, copy-on-write. Dwa podejścia — stronicowanie i segmentacja. [TABLICA: stronicowanie — rysuj kratki jednakowej wielkości po obu stronach (strony i ramki)] **Stronicowanie** — dzielę pamięć wirtualną na **strony** stałego rozmiaru, najczęściej 4KB. Pamięć fizyczna to **ramki** tego samego rozmiaru. Tablica stron mapuje strony na ramki. Adres = numer strony + offset, translacja zamienia numer strony na numer ramki. Zalety — **brak fragmentacji zewnętrznej**, bo wszystko jest tego samego rozmiaru. Wada — fragmentacja wewnętrzna, ale mała — średnio pół strony. TLB — cache translacji — bo sięganie do tablicy stron na każdy dostęp byłoby za wolne. Page fault — gdy strona nie jest w RAM-ie, ładujemy z dysku-swap. Algorytmy wymiany: FIFO, LRU, Clock. [TABLICA: segmentacja — rysuj bloki różnej wielkości etykietowane: KOD, DANE, STOS] **Segmentacja** — dzielę pamięć na logiczne **segmenty** o różnych rozmiarach — segment kodu, danych, stosu. Naturalnie odpowiada strukturze programu. Ochrona jest naturalna — per segment mogę ustawić prawa R/W/X. Wada — **fragmentacja zewnętrzna**, bo segmenty są różnej wielkości. W praktyce — **stronicowanie wygrało**. x86-64 ma flat segmentation — segmenty obejmują całą przestrzeń, a faktyczna translacja idzie przez stronicowanie wielopoziomowe. Intel praktycznie porzucił segmentację. ### Spodziewane pytania dodatkowe **„Co to copy-on-write?"** → Przy fork() dziecko dostaje tę samą pamięć co rodzic — ale strony są oznaczone jako read-only. Dopiero przy pierwszym zapisie robimy kopię. Oszczędność — bo często dziecko robi exec() i zmienia cały obraz. **„Dlaczego wielopoziomowe tablice stron?"** → Bo dla 64-bit jednopoziomowa tablica byłaby gigantyczna. Wielopoziomowa — alokujemy tylko te fragmenty tablicy, które naprawdę pokrywają używaną pamięć. --- \newpage ## PYTANIE 11 · Modelowanie procesów biznesowych (WSYZ) **Pytanie:** *Scharakteryzować standardy i narzędzia do modelowania procesów biznesowych.* --- ### Co mówię Standard numer jeden to **BPMN 2.0**. To jest to, co się pojawia wszędzie, gdzie biznes spotyka IT. BPMN ma trzy typy elementów. **Zdarzenia** — koła: start, pośrednie, końcowe. **Czynności** — prostokąty z zaokrąglonymi rogami: taski i podprocesy. **Bramki** — romby: XOR — jeden z wielu, AND — wszystkie ścieżki, OR — jeden lub więcej. [TABLICA: narysuj prosty proces BPMN — koło start → task → bramka XOR → dwa taski → koło end] Do tego — **swimlanes**: pool to organizacja, lane to dział wewnątrz. Pozwalają pokazać kto za co odpowiada. BPMN 2.0 ma format XML — to znaczy, że diagram nie jest tylko rysunkiem, może być wykonywany w silniku procesowym jak Camunda. Drugi standard — **diagramy aktywności UML**. Podobne do BPMN, ale bardziej zorientowane na IT. Mają fork/join dla współbieżności, pin-y dla przepływu obiektów. Lepsze do modelowania procesów technicznych, gorsze dla osób biznesowych. Trzeci — **EPC** (Event-driven Process Chain). Naprzemienne zdarzenia i funkcje, łączniki AND/OR/XOR. Popularny w ekosystemie SAP, framework ARIS. Porównanie: BPMN jest uniwersalny — łączy biznes z IT. UML Activity — głównie dla programistów. EPC — głównie SAP. Narzędzia: Bizagi Modeler, Camunda, Signavio, Lucidchart, draw.io, Enterprise Architect. ### Spodziewane pytania dodatkowe **„Jaka jest różnica między bramką XOR a OR?"** → XOR — dokładnie jedna ścieżka. OR — jedna LUB więcej. AND — wszystkie. W praktyce XOR jest najczęstsza. **„Czy BPMN może być wykonywany automatycznie?"** → Tak, BPMN 2.0 ma format XML, który silniki procesowe — Camunda, jBPM — mogą interpretować i wykonywać. --- \newpage ## PYTANIE 12 · Sieciowe modele optymalizacji (WSYZ) **Pytanie:** *Przedstawić sieciowe modele optymalizacji stosowane w systemach zarządzania.* --- ### Co mówię Tutaj chodzi o problemy optymalizacyjne, które modelujemy na grafach. Wymienię kilka najważniejszych. [TABLICA: narysuj prosty graf z wagami] **Najkrótsza ścieżka** — klasyka. Dijkstra, Bellman-Ford, A\*. Zastosowanie — GPS, routing w sieciach. Omawialiśmy już wcześniej. **Maksymalny przepływ** — mam sieć z pojemnościami na krawędziach, chcę przepchnąć jak najwięcej ze źródła do ujścia. Algorytm Ford-Fulkersona, Edmonds-Karp. Zastosowanie — przepustowość sieci, planowanie produkcji. **Minimalny koszt przepływu** — jak max flow, ale oprócz pojemności każda krawędź ma koszt. Chcę przepchnąć wymaganą ilość po minimalnym koszcie. Transport, logistyka. **Problem przydziału** — n zadań do n pracowników, macierz kosztów, minimalizuj sumę. Algorytm węgierski, O(n³). HR, grafiki zmianowe. **TSP — problem komiwojażera** — odwiedź wszystkie miasta dokładnie raz, wróć do startu, minimalizuj trasę. NP-trudny — dokładne rozwiązanie nie skaluje się. W praktyce — heurystyki, metaheurystyki. Trasy kurierów. **CPM/PERT** — harmonogramowanie projektów. Wierzchołki to zadania, krawędzie to zależności. Ścieżka krytyczna — najdłuższa ścieżka w grafie — wyznacza minimalny czas projektu. **MST — minimalne drzewo rozpinające** — połącz wszystkie wierzchołki minimalnym kosztem. Kruskal, Prim. Sieci infrastrukturalne — kablowanie, wodociągi. Wspólny mianownik — to wszystko to grafy z wagami i pytanie „jak optymalnie wykorzystać tę sieć?" ### Spodziewane pytania dodatkowe **„Jaka jest różnica między CPM a PERT?"** → CPM — deterministyczne czasy zadań. PERT — probabilistyczne, z trzema oszacowaniami (optymistyczny, pesymistyczny, prawdopodobny). **„Dlaczego TSP jest NP-trudny?"** → Nie znamy algorytmu wielomianowego. Brute force to O(n!) — nie skaluje się. Heurystyki dają przybliżone rozwiązania w rozsądnym czasie. --- \newpage ## PYTANIE 13/27 · Modelowanie architektury systemów informatycznych (AIS) **Pytanie:** *Cele i metody modelowania architektury.* --- ### Co mówię Modelowanie architektury to sposób na zarządzanie złożonością systemu. Cele — komunikacja między zespołami, dokumentacja decyzji, analiza atrybutów jakości, planowanie ewolucji. Kilka frameworków. **C4 Model** — bo jest najprostszy i najpopularniejszy. Simon Brown. Cztery poziomy zoomu: Level 1 — Context: system w otoczeniu, kto z niego korzysta. Level 2 — Container: główne komponenty — web app, baza danych, API. Level 3 — Component: wewnątrz kontenera. Level 4 — Code: klasy, kluczowe fragmenty. Zazwyczaj ten poziom to za dużo. [TABLICA: narysuj cztery kwadraciki, coraz bardziej szczegółowe — „zoom"] **4+1 View Model** Kruchtena. Pięć perspektyw: Logical — funkcjonalność, Process — współbieżność, Development — organizacja kodu, Physical — wdrożenie i sprzęt. I Scenarios — use-case'y, które to wszystko łączą. **TOGAF** — metodyka korporacyjna. ADM — Architecture Development Method. Cztery domeny: Business, Data, Application, Technology. Duży, formalny, enterprise. **Zachman Framework** — taksonomia. Tabela 6×6: What/How/Where/Who/When/Why na jednej osi, a poziomy abstrakcji na drugiej. Nie mówi JAK modelować, mówi CO trzeba opisać. **ArchiMate** — notacja graficzna dla architektury enterprise. Trzy warstwy: Business, Application, Technology. Do analizy — **ATAM**: ocena kompromisów architektonicznych, np. performance vs security. Atrybuty jakości z ISO 25010. ### Spodziewane pytania dodatkowe **„Co to ADR?"** → Architecture Decision Record. Dokument opisujący jedną decyzję architektoniczną: kontekst, decyzja, konsekwencje. Lekka forma dokumentacji. **„Kiedy użyć C4 vs TOGAF?"** → C4 — projekty software'owe, dokumentacja techniczna. TOGAF — architektura korporacyjna, strategic planning, duże organizacje. --- \newpage ## PYTANIE 14/28 · Wzorce architektoniczne (AIS) **Pytanie:** *Czemu służą? Jak powstają? Jak są katalogowane? Przykłady.* --- ### Co mówię Wzorzec architektoniczny to sprawdzone rozwiązanie powtarzalnego problemu. Służą jako **wspólne słownictwo** — mówię „microservices" i każdy wie o co chodzi — oraz jako **przenoszenie wiedzy** między projektami. **Jak powstają?** Ktoś rozwiązuje problem. Inni rozwiązują podobne problemy podobnie. Ktoś to zauważa, uogólnia i **dokumentuje**. Struktura: Nazwa + Problem + Rozwiązanie + Konsekwencje. **Katalogi:** - **GoF** — 23 wzorce projektowe, poziom klas i obiektów. - **POSA** — wzorce architektoniczne, większa skala — Layers, Pipes and Filters, Broker. - **PoEAA** Fowlera — wzorce dla aplikacji enterprise: Repository, Unit of Work, Active Record. - **EIP** — Enterprise Integration Patterns — messaging. - **Cloud Patterns** — Circuit Breaker, Saga, Sidecar. Przykłady wzorców architektonicznych: **Layered** — warstwy: prezentacja → logika → dostęp do danych → baza. Prosta separacja odpowiedzialności, ale sztywna i boilerplate. **Microservices** — niezależne serwisy, osobne wdrożenia, skalowanie per-serwis. Ogromna złożoność operacyjna. **Event-Driven** — zdarzenia przez broker (np. Kafka). Luźne powiązanie, eventual consistency. **Hexagonal / Ports & Adapters** — rdzeń logiki biznesowej niezależny od frameworków i baz danych. Porty to interfejsy, adaptery to implementacje. Świetna testowalność. Złota zasada — **„Monolith first."** Zacznij od monolitu, rozdzielaj gdy poznasz granice domen. ### Spodziewane pytania dodatkowe **„Jaka jest różnica między wzorcem architektonicznym a projektowym?"** → Skala. Architektoniczny — struktura całego systemu (Layers, Microservices). Projektowy — struktura kodu (Strategy, Observer). Architektoniczny wpływa na deployment, zespoły, skalowanie. **„Co to CQRS?"** → Command Query Responsibility Segregation — osobne modele do odczytu i zapisu. Optymalizuję każdą stronę niezależnie. Przydatne gdy read i write mają bardzo różne wymagania. --- \newpage ## PYTANIE 15 · Agent upostaciowiony w robotyce **Pytanie:** *Jak wykorzystuje się agenta upostaciowionego do specyfikacji sterowników robotów?* --- ### Co mówię Agent upostaciowiony to agent, który ma ciało fizyczne — sensory, efektory — i działa w rzeczywistym środowisku. W odróżnieniu od agenta software'owego, musi radzić sobie z szumem sensorycznym, opóźnieniami i niepewnością. Cykl działania to: **Percepcja → Deliberacja → Akcja**. See-Think-Act. Do specyfikacji sterowników używa się architektury warstwowej — klasycznie trzy warstwy. [TABLICA: narysuj trzy prostokąty jeden nad drugim] Na dole — **Controller** — warstwa reaktywna. PID, unikanie kolizji, sterowanie silnikami. Działa w milisekundach. Nie „myśli", reaguje. W środku — **Sequencer** — zarządza sekwencją zachowań. FSM albo Behavior Tree. Decyduje: teraz jedziemy do punktu A, potem chwytamy, potem wracamy. Skala: setki milisekund. Na górze — **Planner** — planowanie symboliczne. Zna mapę, zna cel, tworzy plan. Skala: sekundy do minut. Do formalnej specyfikacji celów i bezpieczeństwa używa się **logiki temporalnej LTL**. Mogę zapisać: „zawsze, gdy jest przeszkoda, nie jedź do przodu" — □(obstacle → ¬move_forward). Albo „ostatecznie dotrzesz do celu" — ◇(at_goal). Te formuły mogą być formalnie weryfikowane. Nowocześnie — **Behavior Trees** stały się popularnym narzędziem specyfikacji. Selector — wykonaj pierwszy sukces. Sequence — wykonaj wszystkie po kolei. Czytelne, modularne, łatwe do wizualizacji. Wywodzą się z game AI — Halo 2 — ale zaadaptowano je w robotyce. Model formalny agenta — BDI: Beliefs — co wiem o świecie, Desires — czego chcę, Intentions — co aktualnie realizuję. ### Spodziewane pytania dodatkowe **„Co to PID?"** → Regulator proporcjonalno-całkująco-różniczkujący. Trzy składniki: P — proporcjonalny do błędu, I — kumulowany błąd, D — szybkość zmiany błędu. Klasyka sterowania. **„Czym jest ROS?"** → Robot Operating System — middleware pub/sub do komunikacji między modułami robota. Nie jest OS-em w sensie jądra, ale daje abstrakcję komunikacji. --- \newpage ## PYTANIE 16 · Języki programowania robotów **Pytanie:** *Omówić specjalizowane języki. Uwypuklić klasyfikację.* --- ### Co mówię Klasyfikuję języki robotów po **poziomie abstrakcji** — od najwyższego do najniższego. [TABLICA: napisz piramidkę — T-R-M-S] **Task-level** — najwyższy. Mówię „podnieś A, połóż na B" — system sam planuje ruchy. PDDL, Behavior Trees. Planowanie zadań. **Robot-level** — komendy ruchu robota: move_to, grasp, release. Każdy producent ma swój język. ABB — RAPID (MoveJ, MoveL, MoveC). KUKA — KRL (PTP, LIN, CIRC). FANUC — Karel. To jest podejście imperatywne — mówię robotowi co ma robić ruch po ruchu. **Motion-level** — planowanie trajektorii, kinematyka odwrotna. Biblioteka MoveIt w ROS. Tutaj programista operuje na poziomie „dojedź z pozycji A do B bez kolizji", ale system musi obliczyć konkretną trajektorię. **Servo-level** — najniższy, sterowanie silnikami. PID, regulacja prądu, pozycji. C/C++, FPGA. Czas rzeczywisty. Jest też podział na **online vs offline**. Online — uczę robota przy konsoli (teach pendant), prowadzę go ręcznie. Offline — programuję w symulatorze na komputerze, potem wgrywam. Problem branży — **vendor lock-in**. Każdy producent ma swój język — RAPID, KRL, Karel, PDL2. Nie są kompatybilne. ROS próbuje to ujednolicić jako warstwa abstrakcji, ale ma problem z hard real-time. Programowanie graficzne — RobotStudio dla ABB, ROBOGUIDE dla FANUC. I Blockly w edukacji. Ciekawostka etymologiczna: język Karel nazwano od Karla Čapka, czeskiego pisarza, który wymyślił słowo „robot" — od czeskiego „robota" — pańszczyzna. ### Spodziewane pytania dodatkowe **„Czym się różni PTP od LIN w KUKA?"** → PTP — Point-to-Point — robot jedzie najszybszą drogą, nie kontroluję trajektorii. LIN — ruch liniowy — efektor jedzie po linii prostej. CIRC — ruch kołowy. **„Czy ROS rozwiązuje problem vendor lock-in?"** → Częściowo. ROS daje wspólną warstwę komunikacji i planowania, ale sterownik nisko poziomowy nadal jest producenta. Oraz ROS nie jest hard real-time w standardowym wydaniu (ROS 2 poprawia to z DDS). --- \newpage ## PYTANIE 17 · Szeregowanie zadań **Pytanie:** *Cechy klasyfikacji. Przykładowa metoda.* --- ### Co mówię Problemy szeregowania klasyfikuje się przez **notację Grahama**: alfa | beta | gamma. [TABLICA: napisz α | β | γ] **α** — środowisko maszynowe. 1 — jedna maszyna. Pm — m maszyn równoległych. F — flow shop, wszyscy przechodzą przez maszyny w tej samej kolejności. J — job shop, każde zadanie ma własną trasę. **β** — cechy zadań. rⱼ — release dates, dⱼ — due dates, pmtn — preemption dozwolona, prec — precedencje. **γ** — kryterium optymalizacji. Cmax — makespan, czas zakończenia ostatniego. ΣCⱼ — suma czasów zakończenia. Lmax — maksymalne opóźnienie. Pokażę na przykładzie. [TABLICA: problem 1 || ΣCⱼ] Mam jedną maszynę, pięć zadań z czasami: J1(5), J2(3), J3(8), J4(2), J5(6). Chcę zminimalizować sumę czasów zakończenia. Reguła **SPT** — Shortest Processing Time — uszereguj od najkrótszego. Sortujemy: J4(2), J2(3), J1(5), J5(6), J3(8). Czasy zakończenia: 2, 5, 10, 16, 24. ΣCⱼ = 2+5+10+16+24 = 57. To jest optymalne! [TABLICA: narysuj oś czasu z zadaniami] Dlaczego to działa? Intuicja — krótkie zadania kończą się wcześnie i „nie czekają" na długie. Formalnie — zamiana sąsiednich zadań, gdzie krótsze jest za długim, zawsze zwiększa sumę. Inne reguły: **EDD** — Earliest Due Date — dla Lmax. **Johnson** — optymalny dla dwumaszynowego flow shop. Większość problemów szeregowania jest **NP-trudna** — job shop, Pm||Cmax dla m≥2. ### Spodziewane pytania dodatkowe **„Co to makespan?"** → Czas od startu pierwszego zadania do zakończenia ostatniego. Mierzy „jak długo trwa cała produkcja". **„Czym się różni flow shop od job shop?"** → Flow shop — wszystkie zadania przechodzą przez maszyny w tej samej kolejności, jak taśma produkcyjna. Job shop — każde zadanie ma indywidualną trasę, jak warsztat naprawczy. --- \newpage ## PYTANIE 18 · Zarządzanie zapasami w łańcuchu dostaw **Pytanie:** *Problemy i przykładowy model.* --- ### Co mówię Główny problem — znalezienie równowagi. Za dużo zapasów — koszty magazynowania, pieniądze zamrożone, ryzyko przeterminowania. Za mało — brak towaru, utracona sprzedaż. Klasyczny problem — **efekt byczego bicza** (bullwhip effect). Małe wahania popytu u detalistów narastają w górę łańcucha — dystrybutor zamawia więcej, producent jeszcze więcej, dostawca surowców widzi gigantyczne wahania. Przyczyny — prognozowanie, zamówienia partiami, promocje. [TABLICA: narysuj sinusoidę, która się amplifikuje — detalista → dystrybutor → producent] Podstawowy model — **EOQ** — Economic Order Quantity. Harrisowsko-Wilsonowski. [TABLICA: napisz wzór] TC(Q) = K·D/Q + h·Q/2 K — koszt zamówienia, D — popyt roczny, h — koszt utrzymania jednostki na rok, Q — wielkość zamówienia. Optymalna wielkość: **Q\* = √(2KD/h)** Przykład: D=10000, K=100, h=2. Q\* = √(2·100·10000/2) = √(1000000) = 1000 sztuk. Koszt optymalny — 2000 PLN/rok. Jest jeszcze **punkt ponownego zamawiania** — ROP = d × L + SS. Popyt dzienny razy lead time plus safety stock. Safety stock zależy od poziomu obsługi — na 95% bierzemy z=1.65, mnożymy przez odchylenie popytu w czasie dostawy. Modele zaawansowane: (s,Q) — zamawiaj Q gdy stan spadnie do s. (s,S) — zamawiaj do poziomu S. VMI — dostawca sam zarządza zapasem u klienta. ### Spodziewane pytania dodatkowe **„Jakie są założenia EOQ?"** → Popyt stały i znany, lead time zero lub stały, brak rabatów ilościowych, dostawy jednorazowe. Bardzo uproszczony model, ale daje dobre intuicje. **„Jak ograniczyć bullwhip effect?"** → Dzielenie danych o popycie w czasie rzeczywistym (POS data), VMI, mniejsze partie zamówień, stabilne ceny bez promocji. --- \newpage ## PYTANIE 19/29 · Model Publish-Subscribe **Pytanie:** *Scharakteryzować model i przykładowe rozwiązania techniczne.* --- ### Co mówię Pub/Sub to wzorzec komunikacji, w którym nadawcy nie wysyłają wiadomości bezpośrednio do odbiorców. Między nimi jest **broker**. [TABLICA: narysuj] Publishers → [Broker] → Subscribers Publisher mówi „oto zdarzenie", a broker dostarcza je wszystkim zainteresowanym subskrybentom. Kluczowa cecha — **luźne powiązanie**: publisher nie wie kto słucha, subscriber nie wie kto wysyła. Jak stacja radiowa — nadaje, kto chce słucha. Typy subskrypcji: **topic-based** — subskrybuję temat, np. „orders.created". **Content-based** — filtracja po zawartości wiadomości. Hierarchiczne tematy z wildcardami — np. „orders.#" łapie wszystko z prefiksem. Gwarancje dostarczenia — QoS. At-most-once — mogę stracić wiadomość. At-least-once — mogą być duplikaty. Exactly-once — najdroższa gwarancja, ale najtrudniejsza do osiągnięcia. Teraz konkretne technologie. **Kafka** — model oparty na logu. Producer pisze do partycji, consumer czyta z offsetu. Pull model — consumer sam decyduje kiedy czyta. Persistence domyślnie — mogę odtworzyć strumień. Very high throughput. Consumer groups — load balancing. LinkedIn, potem Apache. **RabbitMQ** — AMQP, push model. Exchange types: Direct, Topic, Fanout, Headers. Bardziej elastyczny routing, ale wiadomości znikają po konsumpcji. Tradycyjny message broker. **MQTT** — lekki, 2-bajtowy header. Idealny dla IoT, urządzenia z ograniczonymi zasobami. Trzy poziomy QoS. **Redis Pub/Sub** — prosty, szybki, ale fire-and-forget — brak persistence. Dobre do real-time notyfikacji. ### Spodziewane pytania dodatkowe **„Kafka vs RabbitMQ — kiedy co?"** → Kafka — event streaming, duże wolumeny, replay, analityka. RabbitMQ — task queues, złożony routing, tradycyjny messaging. Kafka to log, RabbitMQ to kolejka. **„Co jeśli broker padnie?"** → Broker to Single Point of Failure. Rozwiązanie — replication, clustering. Kafka ma replication factor, RabbitMQ ma mirrored queues. --- \newpage ## PYTANIE 20/30 · Analityka danych strumieniowych **Pytanie:** *Rozwiązania analityczne na danych strumieniowych.* --- ### Co mówię Strumień danych to dane, które płyną ciągle, potencjalnie w nieskończoność. Nie mogę zebrać wszystkiego i przetworzyć — muszę analizować na bieżąco. Kluczowy koncept — **okna czasowe** (windowing). [TABLICA: narysuj oś czasu z oknami] **Tumbling** — rozłączne okna stałego rozmiaru. Każde zdarzenie należy do dokładnie jednego okna. Np. liczba zdarzeń co minutę. **Sliding** — nakładające się okna. Rozmiar 10 minut, przesunięcie co 1 minutę. Zdarzenie może być w wielu oknach. **Session** — definiowane aktywnością. Okno trwa dopóki są zdarzenia, zamyka się po przerwie (gap). **Global** — jedno wielkie okno, trigger decyduje kiedy emitować wynik. Platformy: **Apache Flink** — true streaming, przetwarza zdarzenie po zdarzeniu. Bardzo niska latencja, exactly-once guarantees. SOTA do stream processingu. Nazwa — z niemieckiego „flink" = szybki. **Spark Streaming** — micro-batch. Zbiera zdarzenia w małe paczki i przetwarza. Latencja ~100ms. Prostszy model programowania, łatwo przejść z batcha. **Kafka Streams** — biblioteka, nie klaster. Wbudowana w Kafkę. Lekka, nie wymaga osobnej infrastruktury. Problem czasu — **Event Time vs Processing Time**. Zdarzenie powstaje o 12:00, dociera o 12:05 — który czas liczymy? Watermarki mówią systemowi „do tego momentu powinny dotrzeć wszystkie zdarzenia". Spóźnione dane — drop, przeliczymy, boczny output. Algorytmy strumieniowe — gdy nie ma pamięci na wszystko. **HyperLogLog** — zlicz unikalne elementy z kilobajtem pamięci, ~2% błąd. **Count-Min Sketch** — estymacja częstości. **Reservoir Sampling** — losowa próbka z nieznanego strumienia. ### Spodziewane pytania dodatkowe **„Czym jest watermark?"** → Znacznik postępu event time. Mówi: „wszystkie zdarzenia z czasem mniejszym niż W już dotarły." Spóźnione — traktujemy wg strategii: ignoruj, przelicz, side output. **„Micro-batch vs true streaming?"** → Micro-batch zbiera dane w małe paczki i przetwarza periodycznie — prostsza semantyka, ale wyższe latencje. True streaming — przetwarza per wydarzenie — niższa latencja, ale bardziej skomplikowana obsługa stanu i exactly-once. --- \newpage ## PYTANIE 21 · Zegary logiczne i wektory stempli czasowych **Pytanie:** *Koncepcja i przeznaczenie.* --- ### Co mówię W systemach rozproszonych nie ma globalnego zegara. Każdy węzeł ma swój zegar i one się rozjeżdżają — drift, opóźnienia sieciowe. Nie możemy powiedzieć „to zdarzenie było pierwsze" patrząc na czas ścienny. Lamport w 1978 roku zaproponował rozwiązanie — **relacja happened-before**. Zapisuję ją jako →. Reguły: jeśli a jest przed b w tym samym procesie — a → b. Jeśli a to wysłanie wiadomości, a b to jej odbiór — a → b. I przechodniość. Jeśli nie mogę ustalić porządku — zdarzenia są **współbieżne**, a || b. **Zegar Lamporta** — skalarny. Każdy proces ma licznik C. Przed zdarzeniem — inkrementuję. Wysyłając — dołączam C do wiadomości. Odbierając — biorę max ze swojego C i odebranego, i inkrementuję. [TABLICA: narysuj trzy procesy, strzałki wiadomości, dopisz wartości zegara] Problem — zegar Lamporta gwarantuje: jeśli a → b, to C(a) < C(b). Ale **nie odwrotnie**! Jeśli C(a) < C(b), nie wiem czy a → b, czy są współbieżne. Nie wykrywa współbieżności. **Zegary wektorowe** rozwiązują ten problem. Każdy z N procesów trzyma wektor V[1..N]. Przed zdarzeniem — V[i]++. Wysyłając — dołączam cały wektor. Odbierając — V[j] = max(V[j], T[j]) dla wszystkich j, potem V[i]++. Kluczowa właściwość: **a → b ⟺ V(a) < V(b)**. Równoważność! Jeśli wektory są nieporównywalne — zdarzenia są współbieżne. Porównanie wektorów: V ≤ W wtedy gdy V[i] ≤ W[i] dla każdego i. Współbieżne — gdy ani V ≤ W, ani W ≤ V. Cena — wektor ma rozmiar O(N). Lamport — O(1). Dla małych systemów nieistotne, dla tysięcy procesów — problematyczne. Zastosowania — wykrywanie konfliktów w replikacji (Amazon Dynamo), causal broadcast, debugowanie rozproszone. ### Spodziewane pytania dodatkowe **„Co to version vectors w Dynamo?"** → Wariant zegarów wektorowych do śledzenia wersji obiektów w replikowanej bazie. Pozwalają wykryć konflikty — jeśli wektory nieporównywalne, to dwa węzły pisały niezależnie. **„Czy da się coś między Lamportem a vector clock?"** → Tak — np. dotted version vectors, albo Bloom clocks — hybrydowe podejścia, które oszczędzają pamięć przy zachowaniu wykrywania współbieżności. --- \newpage ## PYTANIE 22 · Modele spójności danych w systemach rozproszonych **Pytanie:** *Silne i słabe modele spójności.* --- ### Co mówię To pytanie o kompromis — im silniejsza spójność, tym wolniejszy system. Im słabsza — tym szybszy, ale trudniejszy do programowania. [TABLICA: narysuj spektrum od lewej do prawej] Linearizability → Sequential → Causal → Session → Eventual **Linearizability** — najsilniejsza. Każda operacja wygląda tak, jakby wykonała się atomowo w jednym momencie między wywołaniem a odpowiedzią. Globalny czas rzeczywisty. Kosztowna — wymaga konsensusu. Przykład — Google Spanner, który synchronizuje atomowe zegary. **Sequential consistency** — jest globalny porządek operacji, zgodny z porządkiem programu każdego procesu, ale NIE musi zgadzać się z czasem rzeczywistym. Przykład — ZooKeeper. **Causal consistency** — operacje przyczynowo zależne widziane w tej samej kolejności przez wszystkich. Niezależne — mogą być w różnej kolejności. Wymaga vector clocks. **Session guarantees** — słabsze: Read Your Writes — widzę to co napisałem. Monotonic Reads — nie cofam się w czasie. **Eventual consistency** — najsłabsza. Jeśli przestanę pisać, to kiedyś wszystkie repliki się zsynchronizują. Ale nie wiadomo kiedy. DNS, Cassandra, DynamoDB. **CAP Theorem** — w obliczu partycji sieciowej muszę wybrać: Consistency albo Availability. Nie mogę mieć obu. CP — np. Spanner, silna spójność, ale niedostępny przy partycji. AP — np. Cassandra, zawsze dostępna, ale eventual. Konflikty w modelu eventual rozwiązuję przez: Last-Writer-Wins, porównanie wersji, albo **CRDTs** — struktury, które matematycznie gwarantują, że po zsynchronizowaniu dają ten sam wynik niezależnie od kolejności. ### Spodziewane pytania dodatkowe **„Czy CAP to wybór 2 z 3?"** → W praktyce — partycja się zdarzy, więc to nie „wybierz 2 z 3", tylko „przy partycji: C czy A?" Normaltynie system ma C i A, problem pojawia się przy awarii sieci. **„Co to quorum?"** → W replikacji — W+R > N gwarantuje, że odczyt trafi na co najmniej jedną replikę z najnowszą wersją. Np. N=3, W=2, R=2. --- \newpage ## PYTANIE 23 · Segmentacja obrazu **Pytanie:** *Problem, strategie klasyczne i sieci neuronowe.* --- ### Co mówię Segmentacja to przypisanie **każdemu pikselowi** etykiety klasy lub regionu. W odróżnieniu od klasyfikacji — która mówi „co jest na zdjęciu" — segmentacja mówi **gdzie** dokładnie. Typy: **Semantic** — klasa per piksel, wszystkie samochody to „samochód". **Instance** — rozróżnia poszczególne instancje, ten samochód od tamtego. **Panoptic** — łączy oba. Metody klasyczne: **Thresholding** — próg intensywności. Piksele powyżej progu — obiekt, poniżej — tło. Otsu automatycznie dobiera próg. Proste, ale ograniczone do dwóch klas. **Region growing** — zaczynam od punktu seed, dodaję sąsiednie piksele spełniające kryterium podobieństwa. Tendencja do over-segmentation. **Watershed** — traktujemy obraz jako teren topograficzny i „zalewamy wodą". Granice — tam, gdzie woda z różnych źródeł się spotyka. Deep learning — tu nastąpił przełom: **U-Net** — encoder-decoder w kształcie U. Encoder kompresuje obraz, decoder odtwarza rozdzielczość. Kluczowe — **skip connections** — łączą warstwy o tej samej rozdzielczości z encodera do decodera. Popularne w medycynie — mało danych, ale skip connections pomagają zachować detale. **DeepLab** — atrous (dilated) convolutions — powiększają receptive field bez dodatkowych parametrów. ASPP — multi-scale processing. **Metryka** — mIoU: intersection over union, uśrednione po klasach. Standard w benchmarkach. [TABLICA: narysuj kształt litery U z prostokątów — encoder po lewej, decoder po prawej, strzałki skip] ### Spodziewane pytania dodatkowe **„Co to dilated convolution?"** → Normalna konwolucja ma filtr 3×3 pokrywający 3×3 pikseli. Dilated — filtr 3×3, ale z przerwami — widzi np. 5×5 lub 7×7 pikseli. Większe receptive field przy tych samych parametrach. **„Dlaczego U-Net jest popularne w medycynie?"** → Bo wymaga mało danych treningowych — skip connections zachowują informacje przestrzenne. Obrazy medyczne są drogie do annotacji, więc data efficiency jest kluczowa. --- \newpage ## PYTANIE 24 · Detekcja obiektów **Pytanie:** *Problem, metody klasyczne, deep learning. Jak zbudować detektor z klasyfikatora?* --- ### Co mówię Detekcja obiektów to jednoczesna **lokalizacja** (bounding box) i **klasyfikacja**. Wynik: klasa, współrzędne ramki, pewność. Podejścia dzielę na dwa etapy — two-stage i one-stage. **Two-stage — rodzina R-CNN:** R-CNN — generuję ~2000 regionów przez Selective Search, każdy region przepuszczam przez CNN, klasyfikuję SVM-em. Bardzo wolne — 50 sekund na obraz. Fast R-CNN — CNN raz na cały obraz, potem ROI Pooling — wycinam cechy regionu z mapy cech. ~2 sekundy. **Faster R-CNN** — kluczowy krok — Region Proposal Network. Zamiast Selective Search — sieć sama proponuje regiony. End-to-end. ~5 fps. [TABLICA: obraz → CNN → RPN → ROI Pool → klasyfikacja + bbox regression] **One-stage — YOLO, SSD:** **YOLO** — You Only Look Once. Dzielę obraz na siatkę S×S, każda komórka predykuje bounding boxy i klasy naraz, w jednym przebiegu sieci. 45-155 fps! Rewolucja w szybkości. Gorszy dla małych obiektów, ale kolejne wersje to poprawiaj. Po detekcji — **NMS** — Non-Maximum Suppression. Mam wiele nakładających się detekcji tego samego obiektu. Sortuję po confidence, biorę najlepszą, usuwam te, które się z nią mocno nakładają (IoU > próg), powtarzam. Teraz — **jak zbudować detektor z klasyfikatora?** Trzy sposoby, coraz lepsze: 1. **Sliding window** — przesuwam okno, każdy patch klasyfikuję. Ekstremalnie wolne. 2. **Region proposals + klasyfikator** — Selective Search wysiewa kandydatów, klasyfikuję każdego. Szybsze, ale wciąż oddzielne kroki. 3. **Fine-tune** — biorę pretrained klasyfikator jako backbone, doczepiam głowicę detekcyjną — bbox regression + klasyfikacja. End-to-end. Najlepsza jakość. ### Spodziewane pytania dodatkowe **„YOLO vs Faster R-CNN — kiedy co?"** → YOLO — gdy zależy na szybkości — real-time, wideo, edge computing. Faster R-CNN — gdy zależy na dokładności, zwłaszcza dla małych obiektów. **„Co to anchor boxes?"** → Predefiniowane kształty ramek o różnych proporcjach. Sieć nie predykuje ramki od zera — predykuje offset od najbliższego anchora. Anchor-free (np. YOLOv8) — bez tego, predykuje punkt centralny i wymiary. --- \newpage ## PYTANIE 25 · Prawo Amdahla — przyspieszenie równoległe **Pytanie:** *Oszacować przyspieszenie. Co osłabia ograniczenie?* --- ### Co mówię Prawo Amdahla mówi, ile zyskam dodając procesory. [TABLICA: napisz wzór] S(n) = 1 / ((1−p) + p/n) p — część kodu, która może być zrównolegloona. n — liczba procesorów. 1−p — część sekwencyjna. Kluczowe — przy n dążącym do nieskończoności: S_max = 1 / (1−p) Jeśli 10% kodu jest sekwencyjne — maksymalne przyspieszenie to 10x. Nawet z milionem procesorów. Sekwencyjna część jest limitem. [TABLICA: szybka tabelka] | p | n=4 | n=16 | n→∞ | |------|------|------|------| | 90% | 3.08 | 5.93 | 10 | | 95% | 3.48 | 9.52 | 20 | | 99% | 3.88 |13.91 | 100 | To jest dość pesymistyczna perspektywa. **Co osłabia to ograniczenie?** **Prawo Gustafsona** — zmień perspektywę. Amdahl mówi: stały problem, więcej procesorów. Gustafson mówi: stały czas, **większy problem**. S = 1 − p + p·n. Dla p=90%, n=100 → S=90.1. Bo w praktyce — gdy mam więcej procesów, daję im więcej danych do przetwarzania, a nie ten sam mały problem. Techniki zmniejszania sekwencyjnej części: algorytmy równoległe (zamiast sekwencyjnych), lock-free structures (zamiast mutexów), pipelining, ukrywanie latencji — async I/O, prefetching. Ale w praktyce przyspieszenie jest jeszcze gorsze niż Amdahl przewiduje — overhead synchronizacji, komunikacja, load imbalance, efekty cache (false sharing). ### Spodziewane pytania dodatkowe **„Jaka jest różnica między strong scaling a weak scaling?"** → Strong — stały problem, dodaję procesory. Amdahl. Weak — zwiększam problem proporcjonalnie do procesorów. Gustafson. W HPC — weak scaling jest bardziej realistyczny. **„Co to false sharing?"** → Dwa wątki piszą do różnych zmiennych, ale tych samych cache lines. CPU unieważnia cache lines nawzajem — ogromne spowolnienie, mimo braku logicznego konfliktu. --- \newpage ## PYTANIE 26 · Komunikacja synchroniczna/asynchroniczna, blokująca/nieblokująca **Pytanie:** *Definicje. Jak uniknąć zakleszczenia w symetrycznych procesach (Jacobi)?* --- ### Co mówię Dwa wymiary — i ludzie je często mylą. **Synchroniczna vs asynchroniczna** — dotyczy tego, czy nadawca czeka na odbiorcę. Synchroniczna — nadawca czeka aż odbiorca przyjmie wiadomość. Asynchroniczna — nadawca wrzuca do bufora i jedzie dalej. **Blokująca vs nieblokująca** — dotyczy tego, czy funkcja wraca od razu. Blokująca — nie wraca dopóki operacja nie skończona. Nieblokująca — wraca natychmiast, operacja w tle, sprawdzam wynik później. W MPI: MPI_Send — blokująca, synchroniczność zależy od implementacji. MPI_Ssend — blokująca synchroniczna. MPI_Isend — nieblokująca. „I" od Immediate. Teraz — **problem zakleszczenia w symetrycznym kodzie**. [TABLICA: narysuj dwa procesy i strzałki] Proc 0: Send(to=1); Recv(from=1); Proc 1: Send(to=0); Recv(from=0); Oba robią Send jako pierwsze. Oba czekają aż partner odbierze. Nikt nie robi Recv. **Deadlock.** **Rozwiązania:** Pierwsze — **asymetria**. Proc 0: Send → Recv. Proc 1: Recv → Send. Jeden wysyła pierwszy, drugi odbiera pierwszy. Prosty, działa. Drugie — **nieblokujące**. Oba robią Irecv + Isend + Wait. Isend i Irecv wracają natychmiast, inicjują operacje w tle, Wait czeka na zakończenie obu. Symetryczny kod, zero deadlocków. Trzecie — **MPI_Sendrecv** — jedna funkcja, która jednocześnie wysyła i odbiera. Implementacja dba żeby nie było zakleszczenia. Najprostsze rozwiązanie. Czwarte — **Bsend** — buforowane. Kopiuje dane do bufora i wraca. Nie czeka na odbiorcę. ### Spodziewane pytania dodatkowe **„Co to metoda Jacobiego i dlaczego ma ten problem?"** → Metoda iteracyjna rozwiązywania układów równań. W wersji równoległej — każdy proces liczy swoją część i wymienia wyniki z sąsiadami. Symetryczny wzorzec — wszyscy robią to samo — stąd ryzyko Send-Send deadlocka. **„Kiedy użyć Isend vs Ssend?"** → Isend — gdy chcę nakładać komunikację z obliczeniami. Ssend — gdy potrzebuję pewności, że odbiorca odebrał (np. protokół synchroniczny). --- \newpage ## PYTANIE 31 · Interaktywne wspomaganie decyzji w warunkach ryzyka **Pytanie:** *Przedstawić metody interaktywne.* --- ### Co mówię „Warunki ryzyka" — znamy prawdopodobieństwa wyników, ale nie wiemy na pewno co się stanie. W odróżnieniu od pewności — gdzie wiem dokładnie — i niepewności — gdzie nie znam nawet prawdopodobieństw. „Interaktywne" — kluczowe słowo. Nie narzucamy decydentowi wyniku. Prowadzamy **dialog** — odkrywamy jego preferencje, funkcję użyteczności — i na tej podstawie rekomendujemy. **Metoda loterii** — najprostsza. Ustalam U(worst)=0, U(best)=1. Pytam: „wolisz x na pewno, czy loterię — z prawdopodobieństwem p najlepszy wynik, z 1−p najgorszy?" Punkt obojętności p\* = U(x). Powtarzam dla kilku wartości x — otrzymuję kształt funkcji użyteczności. **Certainty Equivalent** — CE loterii to pewna kwota, której wartość dla decydenta jest taka sama jak loterii. Jeśli CE < wartość oczekiwana — decydent jest **risk-averse**, ma wklęsłą funkcję użyteczności. CE > E[X] — risk-seeking. **AHP** — Analytic Hierarchy Process Saaty'ego. Strukturyzuję problem jako hierarchię: cel na górze, kryteria w środku, alternatywy na dole. Porównuję parami w skali 1–9. Z macierzy porównań wyciągam wagi — eigenvalue. Sprawdzam spójność — CR < 0.1. [TABLICA: narysuj hierarchię — Cel → Kryteria → Alternatywy] **PROMETHEE** — definiuję funkcje preferencji per kryterium. Obliczam przepływy: Φ⁺ — ile razy alternatywa dominuje inne, Φ⁻ — ile razy jest dominowana. Φ net = Φ⁺ − Φ⁻. Ranking. **ELECTRE** — concordance (na ile kryteriów A jest lepsza od B) plus discordance (jak bardzo B jest lepsza w najgorszym kryterium). Outranking: A S B. ### Spodziewane pytania dodatkowe **„Czym jest risk premium?"** → E[X] − CE. Ile decydent „zapłaci" za pozbycie się ryzyka. Risk-averse → premium > 0. **„Kiedy AHP a kiedy PROMETHEE?"** → AHP — gdy mogę porównać parami, niewielu kryteriów i alternatyw. PROMETHEE — gdy mam więcej danych ilościowych i chcę ranking z przepływami. --- \newpage ## PYTANIE 32 · Dominacja stochastyczna **Pytanie:** *FSD i SSD. Jak mogą być użyte w modelach wyboru?* --- ### Co mówię Dominacja stochastyczna pozwala porównać dwie inwestycje — dwa rozkłady wyników — **bez znajomości dokładnej funkcji użyteczności**. Jeśli A dominuje B, to każdy racjonalny decydent z danej klasy wybierze A. **FSD — First-order Stochastic Dominance.** [TABLICA: narysuj dwie dystrybuanty, F_A zawsze poniżej F_B] A dominuje B w sensie FSD wtedy gdy dystrybuanta A nie jest wyższa od B w żadnym punkcie: F_A(x) ≤ F_B(x) dla każdego x. Interpretacja — A daje **zawsze nie mniejsze prawdopodobieństwo** przekroczenia dowolnego progu. Potrzebuję tylko jednego założenia o U: U' ≥ 0, czyli „więcej = lepiej". Klasa: wszyscy racjonalni, nienasyceni. FSD jest **rzadka** w praktyce — dystrybuanty nie mogą się przecinać. **SSD — Second-order Stochastic Dominance.** A dominuje B wtedy gdy **całka** z dystrybuanty A nie przekracza całki z B — dla każdego x. Dystrybuanty **mogą się przecinać**, ale skumulowane pole pod F_A musi być nie większe. Wymaganie na U: U' ≥ 0 i U'' ≤ 0 — monotoniczne i wklęsłe. Klasa: decydenci z **awersją do ryzyka.** SSD jest znacznie **częstsza** niż FSD. Relacja: FSD implikuje SSD, ale nie odwrotnie. **Zastosowania w modelach wyboru:** Selekcja portfeli — mogę wyeliminować zdominowane portfele bez pytania o U. Jeśli A SSD-dominuje B, to żaden risk-averse decydent nie wybierze B. Redukuję zbiór rozwiązań. Ubezpieczenia — fair ubezpieczenie SSD-dominuje brak ubezpieczenia dla risk-averse. Mean-preserving spread — B = A + szum o zerowej wartości oczekiwanej → A SSD B. Evaluacja inwestycji — A ma wyższy zwrot i mniejsze ryzyko niż B → A SSD B. ### Spodziewane pytania dodatkowe **„Co to mean-preserving spread?"** → Dodaję losowy szum o średniej zero do rozkładu — zachowuję średnią, ale zwiększam rozproszenie. Dla risk-averse — to gorsze. Stąd rozkład bez szumu SSD-dominuje ten z szumem. **„Czy FSD/SSD daje pełne uporządkowanie?"** → Nie — to porządek częściowy. Wiele par alternatyw jest nieporównywalnych. To nie jest ranking — to filtr eliminacyjny. ---