#separator:Tab #html:true #notetype:Basic #deck:Egzamin_extract+main Porównać 'siłę wyrazu' automatu skończonego, automatu ze stosem oraz maszyny Turinga. Jakie klasy języków rozpoznaje każdy z nich? Automat Skończony (Finite Automaton - FA): Języki regularne (Typ 3)

Automat ze Stosem (Pushdown Automaton - PDA): Języki bezkontekstowe (Typ 2)

Maszyna Turinga (Turing Machine - TM): Języki rekurencyjnie przeliczalne (Typ 0) egzamin pyt01 AISDI main Omówić i porównać algorytmy najkrótszej ścieżki wskazując ich kluczowe właściwości i logikę budowy: Dijkstry, Belmana-Forda, A*. Wprowadzenie - problem najkrótszej ścieżki: Warianty problemu: egzamin pyt02 AISDI main Omówić zagadnienia redundancji i normalizacji w relacyjnej bazie danych oraz wynikające z tego wymagania. Wprowadzenie: Redundancja: = niepożądane powtarzanie danych egzamin pyt03 BD2 main Omówić główne kategorie elementów biblioteki STL. Jaka jest ich rola i wzajemne powiązania? Odpowiedź uzasadnić na przykładach. Filozofia STL: Generyczność: szablony (templates) umożliwiają pracę z dowolnymi typami egzamin pyt05 PROI main Przedstawić sieciowe modele optymalizacji stosowane w systemach zarządzania. Omówić ich właściwości. Wprowadzenie: Węzły: = punkty decyzyjne, lokalizacje, zdarzenia egzamin pyt12 WSYZ main Omówić szczegółowo teorie, definicje, standardy i narzędzia wykorzystywane przy projektowaniu i implementacji systemów opartych na koncepcji agenta i aktora. Architektury agentów: Zachowania niskopoziomowe mogą być "nadpisane" przez wyższe.

Standardy komunikacji agentów: FIPA-ACL (Agent Communication Language): egzamin pyt13 AASD main Wymienić i szczegółowo opisać wybrane algorytmy i metody wykorzystywane w systemach wieloagentowych i aktorowych. Algorytmy negocjacji i aukcji: Manager Contractors

Algorytmy konsensusu: Client ──request──→ Primary

Algorytmy koordynacji: Algorytm Ricarta-Agrawali:

Algorytmy uczenia wieloagentowego: Q(s,a) ← Q(s,a) + α[r + γ max Q(s',a') - Q(s,a)]

Algorytmy dla aktorów: // All-for-One: restart wszystkich dzieci egzamin pyt14 AASD main Omówić metody modelowania architektury systemów informatycznych. Przedstawić cele i metody modelowania architektury. Notacje i języki modelowania: Zasada: Zoom in/out między poziomami egzamin pyt15 AIS main Czemu służą wzorce architektoniczne? Jak powstają? Jak są katalogowane? Omówić przykładowe wzorce architektoniczne. Jak powstają wzorce: Nazwa: identyfikator egzamin pyt16 AIS main Przedstawić warunki konieczne i dostateczne optymalności różniczkowalnych zadań optymalizacji bez ograniczeń i z ograniczeniami oraz warunki regularności i omówić metody poszukiwania rozwiązań zadań optymalizacji nieliniowej. Optymalizacja bez ograniczeń: (Gradient zerowy - punkt stacjonarny)

Warunki KKT (Karush-Kuhn-Tucker): Jeśli $x^*$ jest minimum i spełnione są warunki regularności:

Warunki regularności (Constraint Qualification): LICQ: $\{\nabla g_i(x^) : g_i(x^) = 0\} \cup \{\nabla h_j(x^*)\}$ są liniowo niezależne

Warunki dostateczne II rzędu: dla wszystkich $d \neq 0$ spełniających: egzamin pyt17 AMO main Omówić metody rozwiązywania zadań liniowych i kwadratowych optymalizacji. Programowanie liniowe (LP): Złożoność: O(2^n) worst-case, ale praktycznie bardzo szybki

Programowanie kwadratowe (QP): Gdzie Q jest macierzą symetryczną.

Metody rozwiązywania QP: 1. Zgadnij zbiór aktywnych ograniczeń W

Przypadki szczególne: Rozwiązanie: $(A^T A)x = A^T b$ (równanie normalne) egzamin pyt18 AMO main Przedstawić metody wyznaczania cech (parametryzacji) sygnału mowy: MFCC (cechy mel-cepstralne) i LPC (cechy według liniowej predykcji). Cel parametryzacji mowy: Redukcja wymiarowości:: 16kHz × 16bit → ~13-40 cech/ramkę

MFCC (Mel-Frequency Cepstral Coefficients): mel(f) = 2595 · log₁₀(1 + f/700)

LPC (Linear Predictive Coding): Dźwięczne:: pobudzenie okresowe (struny głosowe) egzamin pyt19 EASAR main Przedstawić klasyczną metodę rozpoznawania mowy opartą o HMM (Ukryte Modele Markowa). Porównać ją z metodami korzystającymi z głębokich sieci neuronowych. HMM (Hidden Markov Model) - klasyczne podejście: Każdy stan emituje obserwacje (MFCC) według rozkładu GMM:

Deep Learning w rozpoznawaniu mowy: Attention-based (Seq2Seq):

Ewolucja wydajności: Rok Model WER egzamin pyt20 EASAR main Jak wykorzystuje się agenta upostaciowionego do specyfikacji sterowników robotów? Agent upostaciowiony (Embodied Agent): Percepcji: poprzez sensory

Formalny model agenta: Specyfikacja żywotności: egzamin pyt21 ERPM main Omówić specjalizowane języki programowania robotów. Uwypuklić ich klasyfikację. Języki producentów robotów przemysłowych: ! MoveJ = ruch w przestrzeni złączy (Joint)

Języki uniwersalne i frameworki: rospy.init_node('robot_controller') egzamin pyt22 ERPM main Przedstawić koncepcję i przeznaczenie zegarów logicznych i wektorów stempli czasowych. Problem czasu w systemach rozproszonych: Problem: Nie możemy polegać na zegarach fizycznych - drift, opóźnienia sieciowe, brak atomowej synchronizacji.

Zegar Lamporta (Scalar Clock): 1. Przed każdym zdarzeniem lokalnym:

Zegary wektorowe (Vector Clocks): 1. Przed każdym zdarzeniem lokalnym: egzamin pyt23 ERSMS main Omówić silne i słabe modele spójności danych w środowisku rozproszonym. Silne modele spójności: Implementacja: Consensus (Paxos, Raft), single leader

Słabe modele spójności: Implementacja: DNS, Dynamo, Cassandra egzamin pyt24 ERSMS main Gdzie znajdują zastosowania zadania programowania matematycznego całkowitoliczbowego i jak można je rozwiązywać? Omówić wybraną metodę dokładną, wyjaśnić dla jakich praktycznych problemów ma ona zastosowanie i co może wpływać na jej efektywność. Definicja MIP (Mixed Integer Programming): Przypadki szczególne:

Branch and Bound (B&B) - metoda dokładna: LP relaxation egzamin pyt25 MOD main Scharakteryzować informatyczne narzędzia optymalizacji dyskretnej. Jakie są warunki i wymagania, jakie możliwości oraz trudności wiążą się ze stosowaniem gotowych narzędzi. Porównanie wydajności (benchmark): CPLEX ████████████████████████████ 100% egzamin pyt26 MOD main Omówić typowe fazy ewolucji modelu danych i pożądane cechy modelu w każdej z faz. Model konceptualny (Conceptual Data Model): ┌──────────┐ ┌──────────┐

Model logiczny (Logical Data Model): ┌────────────────────────┐ ┌────────────────────────┐

Model fizyczny (Physical Data Model): CREATE INDEX idx_klient_email ON klient(email); egzamin pyt28 MODA main Oszacować ilościowo przyśpieszenie wykonania programu sekwencyjnego z fragmentami równoległymi na maszynie wielordzeniowej. Co osłabia to ograniczenie? Prawo Amdahla: $$S(n) = \frac{1}{(1-p) + \frac{p}{n}}$$

Wizualizacja ograniczenia: Obserwacja: Krzywe szybko się spłaszczają - dodawanie procesorów daje coraz mniejszy zysk.

Co osłabia ograniczenie Amdahla?: S_scaled(n) = n - (1-p)(n-1) = 1 - p + p·n

Czynniki zmniejszające rzeczywiste przyśpieszenie: ┌─────────────────────────────────────────────────────────────────┐

Efektywność równoległa: Wniosek: Efektywność spada z liczbą procesorów. Trzeba zwiększać problem (Gustafson) lub zmniejszać (1-p). egzamin pyt29 PORR main Omówić metody oraz typowe problemy w modelowaniu matematycznym dla problemów decyzyjnych i optymalizacyjnych. Typowe problemy w modelowaniu: Przykład - planowanie produkcji:

Techniki modelowania: Problem: |x| (wartość bezwzględna) egzamin pyt30 MOM main Wyjaśnić główne zagadnienia modelowania matematycznego w systemach decyzyjnych z wykorzystaniem pojęć (nie)wypukłości i (nie)liniowości. Definicje kluczowe: $$S \text{ wypukły} \Leftrightarrow \forall x,y \in S, \forall \lambda \in [0,1]: \lambda x + (1-\lambda)y \in S$$

Liniowość vs nieliniowość: $$\min c^T x \quad \text{s.t.} \quad Ax \leq b, \quad x \geq 0$$

Testowanie wypukłości: 1. HESJAN: H = ∇²f(x) ≽ 0 (dodatnio półokreślony) dla wszystkich x egzamin pyt31 MOM main Podać definicję komunikacji synchronicznej i asynchronicznej oraz blokującej i nieblokującej. Jak uniknąć zakleszczenia, gdy dwa symetryczne procesy (np. realizujące algorytm iteracyjny Jacobiego) mają w kodzie następujące po sobie wywołania funkcji wysyłającej komunikat do partnera i odbierającej komunikat wysłany przez niego? Definicje podstawowe: KOMUNIKACJA ASYNCHRONICZNA:

Problem zakleszczenia (Deadlock): // Proces 0: // Proces 1:

Rozwiązania problemu zakleszczenia: MPI_Irecv(from=partner, data_in, &req_recv); // Nieblokujące recv egzamin pyt32 PORR main Scharakteryzować model przesyłania komunikatów publikuj-subskrybuj oraz przykładowe rozwiązania techniczne wykorzystujące ten model. Rozwiązania techniczne: channel.queue_bind(exchange='logs', queue=queue_name) egzamin pyt33 PSD main Scharakteryzować rozwiązania analityczne działające na danych o charakterze strumieniowym. Modele przetwarzania: Processing: ───●───────●──●──●───────→

Platformy Stream Processing: KStream source = builder.stream("input-topic");

Algorytmy strumieniowe: Przykład: Redis PFADD, PFCOUNT egzamin pyt34 PSD main Na czym polega specyfika modelowania matematycznego układów cyber-fizycznych? Podać przykłady współpracy agentów w sieci i problemów w osiąganiu pożądanego zachowania układu. Współpraca agentów w sieci: L = Laplacian grafu komunikacji

Warunki zbieżności consensus: Szybkość zbieżności ~ λ₂(L) (algebraic connectivity) egzamin pyt35 SIU main Omówić ogólny algorytm, elementy składowe oraz własności uczenia się ze wzmocnieniem. Funkcje wartości: $$V^\pi(s) = \mathbb{E}_\pi \left[ \sum_{t=0}^{\infty} \gamma^t r_t \mid s_0 = s \right]$$

Algorytmy: ┌─────────────────────────────────────────────────────────────────┐ egzamin pyt36 SIU main Porównać metody projekcji grafów dwudzielnych. Przedstawić ich użyteczność w grupowaniu dokumentów tekstowych. Metody projekcji: P = B · Bᵀ (dla projekcji na U)

Zastosowanie w grupowaniu dokumentów: Graf dwudzielny projekcja (cosine similarity): egzamin pyt38 TASS main Scharakteryzować problem segmentacji obrazu. Przedstawić podstawowe strategie i algorytmy segmentacji przy użyciu metod klasycznych oraz sieci neuronowych. Metody klasyczne: Otsu (automatyczny próg): egzamin pyt39 TWM main Opisać problem detekcji obiektów w obrazach. Przedstawić podstawowe strategie i algorytmy detekcji przy użyciu metod klasycznych oraz sieci neuronowych. Jak skonstruować detektor obiektów dysponując istniejącym klasyfikatorem tych obiektów? Metody Deep Learning: ┌─────────────────────────────────────────────────────────────────┐

Non-Maximum Suppression (NMS): Soft-NMS: Nie usuwa, tylko obniża confidence egzamin pyt40 TWM main Przedstawić metody interaktywne wspomagania decyzji w warunkach ryzyka. Metoda pewnego ekwiwalentu (Certainty Equivalent): Dla loterii L = (p₁: x₁, p₂: x₂, ...): egzamin pyt41 WDWR main Scharakteryzować relacje dominacji stochastycznej pierwszego i drugiego rzędu. Jak mogą być użyte w modelach wyboru w warunkach ryzyka? Dominacja stochastyczna pierwszego rzędu (FSD): $$A \succeq_{FSD} B \Leftrightarrow F_A(x) \leq F_B(x) \quad \forall x$$

Dominacja stochastyczna drugiego rzędu (SSD): $$A \succeq_{SSD} B \Leftrightarrow \int_{-\infty}^{x} F_A(t) dt \leq \int_{-\infty}^{x} F_B(t) dt \quad \forall x$$

Zastosowanie w modelach wyboru: Dla rozkładów normalnych z E[A] > E[B] i σ[A] < σ[B]: egzamin pyt42 WDWR main Jakie cechy zadań szeregowania wykorzystuje się do ich klasyfikacji? Omówić przykładową metodę dla wybranego problemu szeregowania. Pole α - Środowisko maszynowe: MASZYNY RÓWNOLEGŁE (Pm): egzamin pyt43 ZBOP main Jakie problemy wiążą się z zarządzaniem zapasami w łańcuchu dostaw? Omówić przykładowy model zarządzania zapasami w łańcuchu dostaw. Model EOQ (Economic Order Quantity): Ordering cost = K × (D/Q) (D/Q zamówień rocznie) egzamin pyt44 ZBOP main