Wymień cechy algorytmu i sposoby jego reprezentacji.
Cechy: poprawność, jednoznaczność, skończoność, sprawność, prostota działania.
Reprezentacje: zapis słowny, schemat blokowy, drzewo algorytmu,
Omówić zagadnienie asymptotycznej złożoności obliczeniowej algorytmów. Podać standardowe notacje rzędu złożoności.
Algorytmy sortowania oraz charakterystyka ich złożoności obliczeniowej.
Bubble sort O(n^2)
Insertion sort O(n^2)
Quick sort O(n log(n))
Heapsort O(n log(n))
Przedstawić iteracyjne oraz rekurencyjne struktury algorytmiczne. Dokonać porównania.
Struktury drzewiaste, charakterystyka podstawowych typów drzew oraz przykłady ich zastosowań.
Omówić sposoby implementacji list jednokierunkowej oraz dwukierunkowej. Podać zestaw operacji wchodzących w skład interfejsu listy.
Lista jednokierunkowa to struktura danych w której z każdego elementu, można odwołać się do elementu kolejnego. W liscie dwukierunkowej można odwołać się także do poprzedniego elementu listy.
Omówić algorytmy efektywnego poszukiwania najkrótszej ścieżki w grafie.
Procesy kompilacji i interpretacji w różnych językach programowania. Omów ich przebieg, porównaj wady i zalety, wskaż przykłady implementacji w popularnych językach.
Mechanizm przeładowanie operatorów w językach obiektowych. Podaj przykład praktycznego zastosowania.
Przeciążenie operatorów polega na tym, że operator może mieć różne implementacje zależnie od użytych typów operandów (argumentów).
Mechanizm dziedziczenia. Dziedziczenie jedno i wielokrotne. Podaj przykład wykorzystania.
Dziedziczenie to mechanizm współdzielenia funkcjonalności między klasami. Klasa pochodna, poza własnymi atrybutami i metodami otrzymuje także atrybuty i metody klasy z której dziedziczy. Przy dziedziczeniu wielokrotnym klasa otrzymuje atrybuty i metody wszystkich klas po których dziedziczy, ale może wystąpić „deadly diamond of death” czyli przypadek gdzie klasa A dziedziczy po 2 klasach dziedziczących po tej samej klasie i nadpisującymi pewną funkcję f. Przy wywołaniu funkcji f dla klasy A, nie wiadomo którą implementację funkcji f należy wywołać.
Klasy abstrakcyjne i funkcje wirtualne w językach obiektowych. Podaj przykład zastosowania.
Klasa abstrakcyjna to klasa, której obiektów nie można tworzyć, służy jedynie do dziedziczenia i polimorfizmu. Funkcje wirtualne to takie, których wywołania są polimorficzne.
Obsługa sytuacji wyjątkowych w językach obiektowych (np. C++, Java).
Obsługa sytuacji wyjątkowych odbywa się przy użyciu 3 bloków: try, catch, finally. W try mieści się kod w którym może wystąpić wyjątek, blok catch przechwytuje określony wyjątek, lub wszystkie wyjątki i zajmuje się obsługą błędu, natomiast blok finally jest to element który zawsze zostanie wykonany.
Organizacja pamięci pomocniczej - metody przydziału miejsca na dysku;
Pamięć pomocnicza jest pewnym obszarem znajdującym się na dysku, zwiększającym przestrzeń adresową procesora. Wykorzystywana wtedy gdy dane potrzebne procesorowi nie mieszczą się w pamięci głównej. Do przemieszczania procesów między pamięcią główną a pomocniczą służy partycja swap.
Omów i porównaj najczęściej stosowane systemy plików.
FAT32 – prosty, częste fragmentacje, brak zarządzania wolnymi sektorami, brak praw dostępu – obsługiwany przez wszystkie OS
NTFS – prawa dostępu, obsługa rzadkich plików, kompresja woluminów, quota
EXT2 – hierarchia przy pomocy i-węzłów. Katalog to specjalny plik. Każdy plik ma swój i-węzeł. Automatyczne sprawdzanie systemu po niepoprawnym odmontowaniu
EXT3 – journaling(transakcje) i indeksowane katalogi
Metody zarządzania wolną przestrzenią pamięci dyskowej.
Algorytmy planowania przydziału procesora.
Algorytmy zastępowania stron.
Schematy RAID (Redundant Array of Independent Disks). Porównanie pod kątem niezawodności i wydajności.
Raid 0 – stripping – dane są dzielone i przenoszone naprzemiennie na kolejne dyski.
Raid 1 – mirroring – te same dane są zapisywane na wszystkich dyskach.
Raid 4 – dane są dzielone na paski i zapisywane na kolejnych dyskach. + obliczane są kody parzystości zapisywane na dodatkowym dysku.
Raid 5 – to samo tylko kody parzystości zapisywane są na wszystkich dyskach po koleii przez co nie ma stałego obciążenia 1 dysku.
Raid 6 – Tak jak R5, ale z 2 nadmiarowymi dyskami.
Omów metody zarządzania pamięcią.
Mechanizmy komunikacji międzyprocesowej IPC (Inter Process Communication).
Pliki i blokady
Sygnały
Semafory
Kolejki komunikatów – asynchroniczny protokół komunikacyjny
Pamięć dzielona – rodzaj pamięci z której może korzystać wiele programów.
Układy elektroniczne jako filtry. Klasyfikacja i przykłady zastosowań.
Filtr – fragment obwodu elektronicznego odpowiedzialny za przepuszczanie lub blokowanie sygnałów o określonym zakresie częstotliwości.
Dolnoprzepustowe (poniżej pewnej wartości),
Górnoprzepustowe,
środkowoprzepustowe (pomiędzy dwoma wartościami),
środkowozaporowe (nie przepuszcza miedzy 2 wartosciami)
Wzmacniacz operacyjny. Parametry charakterystyczne, zastosowania.
Bramki i funktory logiczne. Tabele prawdy. Minimalizacja funkcji.
OR (y=a+b)
AND (y=a*b)
NOT y=·a
XOR
Minimalizacja za pomocą siatek Karnaugha
http://edu.i-lo.tarnow.pl/inf/alg/002_struct/0005.php
Układy sekwencyjne. Przykłady realizacji i obszary zastosowań.
Układ sekwencyjny charakteryzuje się tym, że stan wyjść zależy od stanu wejści oraz od poprzedniego stanu zwanego stanem zewnętrznym.
Sumator równoległy. Sumator a jednostka arytmetyczno- logiczna.
Sumator – układ kombinacyjny który wykonuje operację dodawania dwóch lub więcej liczb dwójkowych. Sumatory równoległe dodają do siebie jednocześnie bity ze wszystkich pozycji.
Jednostka arytmetyczno-logiczna prowadzi proste operacje na liczbach całkowitych. Operacje logiczne, dodawanie, odejmowanie, przesuniecia bitowe, czasem mnożenie/dzielenie i modulo.
Budowa i zasada działania procesorów: potokowy, wektorowy, CISC, RISC.
Klasyfikacja architektur komputerowych.
Systemy przerwań. Aspekty sprzętowe i programowe.
Przerwanie - sygnał powodujący zmianę przepływu sterowania, niezależnie od aktualnie wykonywanego programu. Pojawienie się przerwania powoduje wstrzymanie aktualnie wykonywanego programu i wykonanie przez procesor kodu procedury obsługi przerwania.
Przerwania sprzętowe: zewnętrzne (sygnał pochodzi z zewnętrznego układu) i wewnętrzne (wyjątki) zgłaszane przez procesor.
Programowe – z kodu wywoływana jest procedura obsługi przerwania, stosowane do komunikacji z OS.
Omówić podstawowe tryby adresowania:
Natychmiastowy (argument częścią rozkazu, nie ma odniesienia do pamięci w celu pobrania argumentu np. „ADD 5”)
Bezpośredni (adres argumentu np. „ADD A” gdzie pod adresem A znajduje się argument)
Pośredni (Pole adresowe odnosi się do słowa w pamięci, które zawiera adres argumentu. np. „ADD (A)” – dodaj zawartość komórki wyznaczonej przez zawartość pod adresem A)
Rejestrowy (argument znajduje się w rejestrze w określony polu adresowym)
Rejestrowy pośredni (adres w rejestrze odnosi się do słowa w pamięci, które zawiera adres argumentu)
Z przesunięciem (pole adresowe zawiera 2 wartości np. EA = A+(R)
Stosowy (argument znajduje się na wierzchołku stosu wskazanym przez rejestr)
Formaty i typy rozkazów procesora, wpływ długości rozkazów procesora na wielkość zajmowanej pamięci przez program oraz na jego czas wykonania.
Typy i hierarchia pamięci w systemie komputerowym.
Pamięć rejestrowa – ulotna, przechowuje argumenty operacji wykonywanych przez procesor [ułamki ns]
Pamięć podręczna pierwszego poziomu (L1) – służy do przechowywania pewnej ilości danych z pamięci operacyjnej najczęściej używanych przez procesor [kilka ns]
Pamięć podręczna drugiego poziomu (L2) – dłuży do wspomagania pracy pamięci pierwszego poziomu przechowując najczęściej używane fragmenty pamięci operacyjnej. Jak nie ma danych w L1 to procesor szuka w L2.
Pamięć ROM – przechowuje dane i kody mikroprogramów jednostki sterującej
Pamięć RAM – przechowuje dane i kody programów.
Pamięć dyskowa/masowa – nieulotna.
Pamięć wymienna/zewnętrzna.
Omów metody projektowania baz danych.
Projektowanie konceptowe – model bazy niezależny od DBMS i dostawcy.
Projektowanie logiczne – tworzenie bazy w konkretnym DBMS.
Projektowanie fizyczne – jak baza danych jest przechowywana na dyskach.
Omów relacyjny model danych.
W modelu relacyjnym, każda relacja (tabela) jest zbiorem rekordów o identycznej strukturze, posiadającym unikalną nazwę, nagłówek i zawartość. Nagłówek to zbiór atrybutów a zawartośc zbiorem krotek.
Na czym polega proces normalizacji baz danych
Normalizacja jest to proces mający na celu eliminację powtarzających się danych w bazie. Normalizacja może spowodować zmniejszenie prędkości bazy, szczególnie przy SELECTach.
1NF: Każda składowa w każdej krotce jest elementarna. Tzn. jest prostą wartością a nie grupą wartości. Wszystkie kluczowe atrybuty muszą być zdefiniowane. Wszystkie atrybuty muszą zależeć od klucza głównego.
2NF: Nie ma częściowych zależności. Żaden atrybut nie jest zależny od części klucza głównego (kompozytowy klucz). Jeżeli klucz główny jest tylko jednym atrybutem, tabela jest w 2NF jeśli jest w 1NF.
3NF: Nie ma przejściowych zależności (atrybutów zależnych od innych atrybutów nie będących kluczem głównym)
Przedstawić koncepcję transakcyjności w relacyjnych bazach danych.
Transakcja – zbiór operacji na bazie danych które stanowią całość i powinny być albo wykonane wszystkie, albo żadna z nich. W przypadku niepowodzenia w trakcie przeprowadzenia operacji, zmiany są cofane.
Techniki modelowania bazy danych, diagramy E/R i UML, narzędzia do modelowania.
Diagramy ERD – graficzne przedstawienie związków pomiędzy encjami.
Problemy współbieżności i wielodostępu w SZBD.
Model ISO OSI. Model TCP/IP. Krótka charakterystyka warstw modelu.
Warstwy ISO OSI:
Fizyczna / Dostępu do internetu
Łącza danych / Dostępu do internetu
Sieciowa / Internetu
Transportowa
Sesji / Aplikacji
Prezentacji / Aplikacji
Aplikacji / Aplikacji
Metody dostępu do medium. Protokół CSMA/CD.
CSMA/CD polega na tym, że stacja sprawdza czy jakaś inna już nadaje. Jeśli tak to czeka aż skończy. Stacja zaczyna nadawać sprawdzając czy ktoś inny nie nadaje równocześnie z nią. Jeśli ktoś nadawał, to przerywa nadawanie i odczekuje losowy odcinek czasu.
Adresowanie IP, podsieci i maski podsieci zmiennej długości.
Ruting w sieciach komputerowych, metody rutingu, porównanie.
Metody dostępu do sieci w technologii bezprzewodowej WiFi.
Podstawowe i złożone topologie sieci komputerowych.
Charakterystyka systemów rozproszonych - zalety i wady.
Modele programowania równoległego.
Miary efektywności obliczeń równoległych.
Środowiska programowania równoległego.
Prawo Amdahla.
Obrazy rastrowe i wektorowe: budowa, właściwości, różnice.
Grafika rastrowa - prymitywy graficzne 2D: kreślenie odcinków, okręgów, wypełnianie obszarów.
Algorytmy poprawy jakości obrazu rastrowego.
Metody skalowania obrazów rastrowych.
Modele barw stosowane w grafice komputerowej (RGB, CMY, HSV, LAB).
Cykl życia oprogramowania.
Model kaskadowy i spiralny, charakterystyka i porównanie.
Metryki oprogramowania, przykłady i obszary zastosowań.
Specyfikacja wymagań funkcjonalnych i niefunkcjonalnych, rola UML w procesie specyfikowania wymagań.
Model logiczny a model fizyczny systemu – rola w procesie tworzenia oprogramowania.
UML w analizie i projektowaniu – omówienie podstawowych cech notacji.
Diagramy stanu oraz diagramy sekwencji, porównanie obszarów stosowania.
Testowanie oprogramowania, omówić model V.
Podstawowe pojęcia niezawodności systemów technicznych, niezawodność systemów oprogramowania, miary niezawodności.
Proces zarządzania bezpieczeństwem systemów informatycznych, polityka bezpieczeństwa.
Kryptosystemy symetryczne oraz metody dystrybucji kluczy w systemach symetrycznych.
Kryptografia asymetrycznej w zagadnieniach bezpieczeństwa sieciowych systemów komputerowych – przykłady zastosowań.
Podpis elektroniczny a podpis cyfrowy, definicje, przykłady zastosowań.
Zapory ogniowe – pojęcia podstawowe, obszary zastosowań.
Systemy wykrywania zagrożeń (IDS) – koncepcja, zasady lokalizacji sondy.
Wirtualne sieci prywatne (VPN) - koncepcja, przykłady zastosowań, stosowane protokoły.
Wyjaśnij określenie "exploitation-exploration trade-off" w kontekście próby definicji sztucznej inteligencji.
Na czym polega uczenie sieci neuronowej algorytmem typu backpropagation.
Omów podstawowe metody bezstratnej i stratnej kompresji danych.
Wymień standardowe metody kompresji sygnałów multimedialnych