1. Co to jest bit?
   Bit (z ang. binary digit) - w informatyce określany jako najmniejsza ilość informacji. Bit przyjmuje jedną z dwóch wartości, które zwykle określa się jako 0 i 1, lub prawda, fałsz. Oznaczamy „b”.

2. W jakim systemie zapisu liczb zapisuje się informacje w „informatyce”?
   W systemie binarnym.

3. Dlaczego binarny system zapisu uznano za dogodną metodę zapisu danych mino koniecznego narzutu na reprezentacje danych (kodowanie)?
   Binarny sposób zapisu informacji związany jest z tym, że komputer jako urządzenie elektroniczne rozpoznać może dwa stany prądowe:
   0 - brak napięcia lub bardzo niskie (mniej niż 10% wartości wysokiego)
   1 - wysokie napięcie.

4. Ile bitów to 1 bajt?
   8 bitów.

5. Ile bajtów ma 1kB?
   1024

6. Czy 1000 bajtów to, to samo co 1kB?
   Nie.

7. Przelicz (25)D=(?)B, (10010101)B=(?)D
   (25)D=(11001)B, (10010101)B=(149)D

8. Przelicz (1A)H=(?)D, (10010101)B=(?)H
   (1A)H=(26)D, (10010101)B=(95)H

9. Ile wartości może reprezentować 1 bajt?
   256

10. Co to jest kod ASCII?
    ASCII [aski] (ang. American Standard Code for Information Interchange) - 7-bitowy kod przyporządkowujący liczby z zakresu 0-127 literom (alfabetu angielskiego), cyfrom, znakom przestankowym i innym symbolom oraz poleceniom sterującym. Przykładowo litera "a" jest kodowana liczbą 97, a polecenie "powrót karetki" - liczbą 13. Istnieją rozszerzenia kodu ASCII do 8 bitów, np. UTF-8.

11. Jak reprezentuje się liczby zmienno przecinkowe?
    Liczba zmiennoprzecinkowa jest komputerową reprezentacją liczb rzeczywistych zapisanych w postaci wykładniczej (zwanej też notacją naukową). Ze względu na wygodę operowania na takich liczbach przyjmuje się ograniczony zakres na mantysę i cechę. Powoduje to, że liczba jest określana z pewną dokładnością i może występować w określonym zakresie.

12. Jakie mamy metody programistyczne?
    -Projektowanie zstępujące
    -Projektowanie wstępujące
    -Abstrakcyjne typy danych

13. Co to jest algorytm?
    Skończony, uporządkowany ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego zadania.

14. Od czego pochodzi nazwa algorytm?
    Pochodzi od nazwiska nazwiska Muhammed ibn Musa Alchwarizmi, matematyka perskiego z IX wieku i początkowo oznaczało w Europie sposób obliczeń oparty na dziesiętnym systemie liczbowym.

15. Podaj algorytm na dodawanie dwóch liczb całkowitych przy założeniu, że są to liczby w zakresie a,b€<0,10>.
    Podaj a; Podaj b; Jeśli a<0 lub a>10, to dane wychodzą poza zakres. Jeśli b>10 lub b<0 to dane wychodzą poza zakres. Jeśli dane są z zakresu <0;10> to oblicz sumę := a + b; Pokaż wynik

16. Jakie są rodzaje algorytmów?
    Iteracyjne - rodzaj algorytmu i programu, w których wielokrotnie wykonuje się pewne instrukcje, dopóki nie zostanie spełniony określony warunek. Rekurencyjne - takie procedury, które w swojej definicji posiadają wywołanie samej siebie. Sekwencyjne - instrukcje wykonywane są w porządku, w jakim zostały wprowadzone.

17. Czym powinien charakteryzować się poprawny algorytm?
    Powinien pokazywać prawidłowy wynik przy prawidłowych danych wejściowych, rozważać wszystkie możliwe warunki, ograniczać czas rozwiązywania problemu do minimum.

18. Narysuj algorytm dla p. 15.
    
    

19. Do czego służy notacja „wielkie O”?
    Wykorzystuje się nią do szacowania efektywności algorytmu. Jest to wygodny sposób porównywania prędkości algorytmów, nie podaje rzeczywistych czasów działania algorytmów ale uzmysławia jaki wpływ na czas pracy ma liczba elementów.

20. Podaj przynajmniej jedną własność notacji „wielkie O”?
    -Funkcja an^k jest O(n^k)
    -Funkcja n^k jest O(n^k+j) dla dowolnego dodatniego j

-Jeśli f(n) jest O(g(n)) i g(n) jest O(h(n)), to f(n) jest O(h(n))0

21. Jakie mamy typy algorytmów, jeżeli chodzi o rząd złożoności i zachłanności na moc obliczeniową?

- algorytm stały - czas wykonania pozostaje taki sam niezależnie od ilości przetwarzanych elementów.

- algorytm liniowy - czas wykonania wzrasta proporcjonalnie do przyrostu danych

- algorytm kwadratowy - czas wykonania wynosi O(n²)

- algorytm logarytmiczny - czas wykonania wynosi O(log n)

22. Do jakiego typu algorytmu dążymy (chodzi o charakter złożoności obliczeniowej)?
    Do algorytmu logarytmicznego, który można potraktować jako bardzo dobry.

23. Czy „problemy” obliczeniowe mają jednakową złożoność obliczeniową?
    Nie.

24. Co to jest iteracja?
    To czynność powtarzania (najczęściej wielokrotnego) tej samej instrukcji (albo wielu instrukcji) w pętli. Mianem iteracji określa się także operacje wykonywane wewnątrz takiej pętli.

25. Co to jest rekurencja
    To w logice, programowaniu i w matematyce odwoływanie się np. funkcji lub definicji do samej siebie.

26. Co to jest indukcja?
    Pewne zdanie jest niezmiennikiem pętli. Termin indukcja matematyczna używany jest na określenie szczególnej metody dowodzenia twierdzeń (w najbardziej typowych przypadkach o liczbach naturalnych) ale także jest on używany na oznaczenie konstrukcji pewnych obiektów.

27. Podaj przynajmniej trzy algorytmy sortowania.
    Sortowanie bąbelkowe; Sortowanie szybkie; Sortowanie przez wstawianie; Sortowanie kubełkowe; Sortowanie przez wybór; Sortowanie przez scalanie.

28. Podaj definicję wariacji z powtórzeniami i bez powtórzeń.
    Wariacją z powtórzeniami k-wyrazową zbioru n-elementowego A nazywa się każdy k-wyrazowy ciąg elementów tego zbioru. Liczba wszystkich k-wyrazowych wariacji z powtórzeniami zbioru n-elementowego jest równa

Wariacją bez powtórzeń k-wyrazową zbioru n-elementowego A (k≤n) nazywa się każdy k-wyrazowy ciąg k różnych elementów tego zbioru, przy czym kolejność tych elementów ma znaczenie. Gdy k=n, wariację bez powtórzeń nazywa się permutacją. Liczba wszystkich k-wyrazowych wariacji bez powtórzeń zbioru n-elementowego wyraża się wzorem:

29. Co to są permutacje?
    Przekształcenie pewnego zbioru na siebie. Permutacją bez powtórzeń zbioru n-elementowego nazywamy każdy ciąg n-wyrazowy utworzony ze wszystkich elementów tego zbioru.
    Liczba permutacji bez powtórzeń zbioru n-elementowego
    Permutacją z powtórzeniami zbioru n-elementowego nazywamy każdy ciąg n-wyrazowy utworzony z elementów tego zbioru, wśród których pewne elementy powtarzają się odpowiednio n1,n2, … nk razy
    Liczba permutacji z powtórzeniami zbioru n-elementowego, wśród których pewne elementy powtarzają się odpowiednio n1,n2, … nk razy

30. Co to są kombinacje?
    To każdy multizbiór, którego elementami są elementy jakiegoś zbioru skończonego. k-elementową kombinacją zbioru n-elementowego A nazywa się każdy k-elementowy multizbiór składający się z elementów zbioru A. C _n^k =
    =
    

31. Czy prawdopodobieństwo może być większe od 1?
    Nie.

32. Podaj definicję prawdopodobieństwa warunkowego.
    Prawdopodobieństwo warunkowe zajścia zdarzenia
    pod warunkiem, że zaszło zdarzenie
    obliczamy ze wzoru

33. Podaj przykład algorytmu probabilistycznego.
    Albo randomizowany to algorytm, który do swojego działania używa losowości. Algorytm Las Vegas i Monte Carlo.

34. Co to jest model danych?
    Zestaw matematycznych pojęć i definicji dotyczący danych i przetwarzania danych.

35. Co to jest struktura danych?
    Sposób uporządkowania informacji w komputerze.

36. Zaproponuj prostą strukturę danych dla struktury składającej się z 2 elementów.

37. Podaj kilka przykładów modeli danych.
    Hierarchiczny, sieciowy, relacyjny, binarnych relacji, obiektowy, funkcjonalny, zagnieżdżonych relacji, dedukcyjny, dedukcyjno-obiektowy, relacyjno-obiektowy.

38. Czy model systemu plików można uznać za model danych?
    Tak.

39. Co to jest drzewo?
    Jest rodzajem schematu blokowego, który przyjmuje postać odwróconego naturalnego drzewa. W informatyce drzewa są strukturami danych reprezentującymi drzewa matematyczne. W naturalny sposób reprezentują hierarchię danych (obiektów fizycznych i abstrakcyjnych, pojęć, itp.), toteż głównie do tego celu są stosowane. Drzewa ułatwiają i przyspieszają wyszukiwanie, a także pozwalają w łatwy sposób operować na posortowanych danych.

40. Podaj podstawową terminologię dotyczącą drzew.

Drzewa składają się z wierzchołków (węzłów) oraz łączących je krawędzi. Wszystkie wierzchołki połączone z danym wierzchołkiem, a leżące na następnym poziomie są nazywane dziećmi tego węzła. Wierzchołek może mieć dowolną liczbę dzieci, jeśli nie ma ich wcale nazywany jest liściem. Wierzchołek jest rodzicem dla każdego swojego dziecka; każdy węzeł ma dokładnie jednego rodzica. Wyjątkiem jest korzeń drzewa, który nie ma rodzica. W drzewie istnieje dokładnie jedna ścieżka pomiędzy węzłem a korzeniem; przez ścieżkę rozumie się ciąg krawędzi, na rys. przykładowa ścieżka do węzła J jest zaznaczona na czerwono. Liczba krawędzi w ścieżce jest nazywana długością - liczba o jeden większa określa poziom węzła. Z kolei wysokość drzewa to największy poziom istniejący w drzewie (przykładowe drzewo ma wysokość 4).

41. Co to jest drzewo binarne?
    Drzewa binarne są to drzewa, które posiada węzeł główny (drzewo), który posiada co najwyżej dwójkę potomków ? lewy i prawy (poddrzewa). Każdy z potomków może posiadać również najwyżej dwójkę dzieci (lewe dziecko i prawe dziecko).

42. Czym szczególnym wyróżnia się drzewo binarne od „zwykłego” drzewa?
    Wierzchołki w drzewie binarnym mogą posiadać maksymalnie 2 dzieci, natomiast w zwykłym drzewie, dowolną ilość.

43. Czym różni się pełne drzewo binarne od zdegenerowanego drzewa binarnego?
    Pełne drzewo binarne ma w każdym wierzchołku 0 lub 2 następniki. Zdegenerowane zawiera tylko jeden liść.

44. Co to jest drzewo binarne częściowo uporządkowane?

Drzewa binarne częściowo uporządkowane jest to zaetykietowane drzewo binarne
o następujących własnościach: -Etykietami węzłów są elementy z przypisanymi priorytetami; priorytet może być wartością elementu lub przynajmniej jednego z jego komponentów. -Element przechowywany w węźle musi mieć co najmniej tak duży priorytet jak element znajdujący się w dzieciach tego węzła. Element znajdujący się w korzeniu dowolnego poddrzewa jest wiec największym elementem tego poddrzewa.

45. Jak implementujemy zrównoważone drzewa binarne częściowo uporządkowane?

Zrównoważone drzewa częściowo uporządkowane można implementować za pomocą tablicowej struktury danych zwanej stogiem (ang. heap), która umożliwia szybką i zwięzłą implementację kolejek priorytetowych. Stóg jest to po prostu tablicą A, której sposób indeksowania reprezentujemy w specyficzny sposób. Zapisuje kolejne poziomy, zawsze porządkując od lewej do prawej.

46. Gdzie znalazły zastosowania rozwiązania związane z implementacją drzew binarnych?

47. Co to jest STOS?
    Liniowa struktura danych, w której dane dokładane są na wierzch stosu i z wierzchołka stosu są pobierane. Ideę stosu danych można zilustrować jako stos położonych jedna na drugiej książek - nowy egzemplarz kładzie się na wierzch stosu i z wierzchu stosu zdejmuje się kolejne egzemplarze.

48. Co to jest lista?
    To struktura danych używana w informatyce. Jest to pojemnik składający się z połączonych ze sobą w łańcuszek komórek zawierających dane.

49. Podaj jakie operacje można prowadzić na listach?
    Implementacja; Łączenie.

50. Podaj za pomocą jakich struktur można zaimplementować listę.
    Tablicowa i wskaźnikowa.

51. Co wyróżnia listę dwukierunkową względem jednokierunkowej?
    Lista dwukierunkowa - w każdym elemencie listy jest przechowywane odniesienie zarówno do następnika jak i poprzednika elementu w liście. Taka reprezentacja umożliwia swobodne przemieszczanie się po liście w obie strony.
    Lista jednokierunkowa - w każdym elemencie listy jest przechowywane odniesienie tylko do jednego sąsiada (następnika lub poprzednika).

52. Czy istnieje zdefiniowane pojęcie zbioru w matematyce?
    Tak. Zbiór to pojęcie pierwotne w matematyce, a dokładniej w teorii mnogości. Oznacza mnogość, wielość, nieuporządkowany wykaz, kolekcję pewnych różnych elementów rozpatrywanych jako całość.

53. Podaj podstawowe operacje możliwe do wykonania na zbiorach.
    Suma zbiorów; Przekrój; Różnica zbiorów; Różnica symetryczna; Iloczyn kartezjański; Suma rozłączna; Zbiór potęgowy; Dopełnienie zbioru.

54. Co oznacza symbol: Ø?
    Zbiór pusty.

55. Co to jest wektor własny?
    Wektor własny macierzy
    , to taki wektor
    , dla którego istnieje taka wartość λ, że zachodzi równość:
    .
    Wektor własny przekształcenia liniowego
    , to taki wektor
    , dla którego istnieje taka wartość λ, że zachodzi równość:
    .

56. Przedstaw strukturę tablicy mieszającej.

Tablic mieszających używa się do tworzenia struktur danych zawierających informacje, identyfikowane przez pewien klucz. Ze względu na fakt, iż klucz ten może mieć zakres wartości większy niż rozmiar tablicy (np. numer PESEL), lub może mieć postać ciągu znaków (np. nazwisko), potrzebna jest metoda konwersji klucza na indeks w tablicy. Metody takiej dostarcza funkcja mieszająca.

57. Gdzie znalazły zastosowanie tablice mieszające - podaj przykład?
    Sieć peer-to-peer. Protokół Kademlia stosowany w niektórych sieciach typu peer-to-peer. Większość języków programowania posiada implementację tablicy mieszającej w ramach standardowej biblioteki.

58. Co to jest krotka (tuple)?
    Uporządkowany skończony zbiór elementów. Intuicyjnie: uporządkowana lista dowolnych obiektów. Krotka jest uogólnieniem pojęć uporządkowanych: pary (dwójki), trójki, czwórki, itd. na dowolną (skończoną) liczbę elementów. Każdej krotce odpowiada ciąg skończony.

59. Czy rekord w bazie danych można uznać za krotkę?
    Tak, ponieważ krotka jest to skończona lista czyli rekord.

60. Podaj przynajmniej 2 specyficzne własności relacji binarnych.
    Przechodniość; Symetria; zwrotność; antysymetria.

61. Na czym polega relacyjny model danych?
    Dane w modelu relacyjnym są reprezentowane jako zbiór krotek, które w znormalizowanych bazach danych są unikalne i nie gra roli ich kolejność. Dostęp do nich jest realizowany za pomocą algebry relacji - czyli dostęp do danych definiujemy poprzez operatory relacyjne takie jak: rzutowanie, selekcja, złączenie, suma, różnica, produkt kartezjański . Ograniczenie redundancji danych dokonuje się w procesie przejścia do kolejnych postaci normalnych. Zbiory danych powiązane są logicznie za pomocą encji. W ten sposób uniezależnia się widziany przez użytkownika obraz bazy danych od jej postaci fizycznej.

62. Czym różni się w relacyjnych bazach danych indeks główny od indeksu drugorzędnego?

63. Jakie są podstawowe 4 kroki związane z projektowaniem bazy danych?

1. Wybór schematu bazy danych.

2. Wybór klucza.

3. Wybór indeksu głównego.

4. Kiedy utworzyć indeks drugorzędny?

64. Co to jest algebra relacyjna?
    Jest to model operowania danymi w bazie danych, oparty na logicznym rachunku predykatów (funkcja zdaniowa, forma zdaniowa). Wyróżnia się dwie odmiany: rachunek na krotkach - język SQL oraz na dziedzinach - interfejs QBE.

65. Co oznacza skrót SQL, oraz na jakiej algebrze bazuje ten język?
    Structured Query Language - strukturalny język zapytań. Bazuje na algebrze relacyjnej.

66. Na czym polega optymalizacja zapytań SQL?

Polega ona na napisaniu zapytania w taki sposób, aby wyszukiwanie informacji na bazie danych działało jak najszybciej i jak najefektywniej.

67. Co realizuje zdanie SQL typu SELECT?

SELECT służy do wybierania danych z jednej lub kilku tabel. Może być używany jako osobna instrukcja lub jako zapytanie lub podzapytanie w innych poleceniach

68. Jak można nazwać inaczej pojedynczy rekord bazy danej tabeli?
    Pole.

69. Co to jest graf?
    Zbiór wierzchołków, które mogą być połączone krawędziami, w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków.

70. Czym różni się graf skierowany od grafu niekierowanego?
    Ruch po grafie skierowanym możliwy jest tylko w kierunkach wskazywanych przez krawędzie a w grafie niekierowanym w obie strony.

71. Czym charakteryzuje się graf pełny?
    Graf, którego każdy wierzchołek jest połączony bezpośrednio krawędzią z każdym innym.

72. Co to są grafy planarne i nieplanarne?
    Graf planarny to graf, który można narysować na płaszczyźnie tak, by krzywe obrazujące krawędzie grafu nie przecinały się ze sobą. Graf nieplanarny jest to graf, którego krzywe przecinają się ze sobą np. grafy pełne K₅ i K_3,3.

73. Za pomocą jakich dwóch sposobów można reprezentować (i implementować) graf?
    Macierze sąsiedztwa są preferowanym sposobem reprezentacji grafów wówczas, gdy grafy są gęste, to znaczy, kiedy liczba krawędzi jest bliska maksymalnej możliwej ich liczby. Listy sąsiedztwa jeśli graf jest rzadki to ta reprezentacja może pozwolić zaoszczędzić pamięć.

74. Co to jest minimalne drzewo rozpinające?
    Jest to drzewo rozpinające danego grafu o najmniejszej z możliwych wag, tj. takie, że nie istnieje dla tego grafu inne drzewo rozpinające o mniejszej sumie wag krawędzi.

75. Czego przykładem może być algorytm Kruskala?

Algorytm Kruskala wyznacza minimalne drzewo rozpinające. Jest to algorytm zachłanny, który wybiera krawędzie o najmniejszych wagach.

76. Czego dotyczy algorytm Dijkstry i algorytm Floyda?
    Algorytm Dijkstry służy do rozwiązywania problemu najkrótszej ścieżki w grafie skierowanym, o nieujemnych wagach krawędzi.

Algorytm Floyda służy do wyznaczania najmniejszej odległości pomiędzy parami wierzchołków (przy korzystaniu z wierzchołków pośrednich). Graf musi być skierowany i nie posiadać cykli o ujemnej długości. Warunek nieujemności cyklu wynika z tego, że w grafie o ujemnych cyklach najmniejsza odległość między niektórymi wierzchołkami jest nieokreślona, ponieważ zależy od liczby przejść w cyklu

77. Jakie są trzy równoważne opisy wzorców?

78. Co to jest wzorzec?

Wzorzec projektowy - w inżynierii oprogramowania, uniwersalne, sprawdzone w praktyce rozwiązanie często pojawiających się, powtarzalnych problemów projektowych.

79. Czym się różni automat deterministyczny od automatu niedeterministycznego?
    Deterministyczny to abstrakcyjna maszyna o skończonej liczbie stanów, która zaczynając w stanie początkowym czyta kolejne symbole pewnego słowa, po przeczytaniu każdego zmieniając swój stan na stan będący wartością funkcji jednego przeczytanego symbolu oraz stanu aktualnego. Jeśli po przeczytaniu całego słowa maszyna znajduje się w którymś ze stanów oznaczonych jako akceptujące (końcowe), słowo należy do języka regularnego, do rozpoznawania którego jest zbudowana.
    Niedeterministyczny to maszyna o skończonej liczbie stanów, która zaczynając w stanie początkowym czyta kolejne symbole pewnego słowa. Po przeczytaniu każdego symbolu zmienia ona swój stan na stan będący elementem zbioru, który jest wartością funkcji przejścia. Jeśli po przeczytaniu całego słowa maszyna znajduje się w którymś ze stanów oznaczonych jako akceptujące (końcowe), mówimy że automat akceptuje czytane słowo.

80. Na czym polega tzw. minimalizacja automatów?

81. Co to jest wyrażenie regularne?
    To wzorzec, który opisuje łańcuchy symboli. Teoria wyrażeń regularnych jest związana z teorią tzw. języków regularnych. Wyrażenia regularne mogą określać zbiór pasujących łańcuchów, mogą również wyszczególniać istotne części łańcucha.

82. Podaj co najmniej 3 prawa algebraiczne wyrażeń regularnych.

Tożsamość sumowania: ( ჆| R ) Ⴚ ( R | ჆) Ⴚ R

Tożsamość złożenia: ၥ R Ⴚ R ၥ Ⴚ R

Przemienność sumowania: (R | S) Ⴚ (S | R )

Łączność sumowania: ( (R | S) | T ) Ⴚ ( R | ( S | T ) )

Łączność złożenia: ( ( R S ) T ) Ⴚ ( R ( S T ) )

83. Co to jest gramatyka bezkontekstowa?
    To gramatyka formalna, w której wszystkie reguły wyprowadzania wyrażeń są postaci:
    gdzie A jest dowolnym symbolem nieterminalnym i jego znaczenie nie zależy od kontekstu, w jakim występuje, a Γ to dowolny (być może pusty) ciąg symboli terminalnych i nieterminalnych.

84. Jakie 3 kategorie syntaktyczne należy zdefiniować aby otrzymać jednoznaczną gramatykę?

85. Jakie są kategorie syntaktyczne definiujące jednoznaczną gramatykę - podaj nazwy i opisz je.

86. Co to jest PARSER?
    (inaczej analizator składniowy) w informatyce program dokonujący analizy danych wejściowych w celu określenia ich gramatycznej struktury w związku z formalną gramatyką.

87. Co to jest algebra Boole'a?
    Algebry Boole'a są specjalnym typem struktur algebraicznych rozważanych w matematyce, teoretycznej informatyce oraz elektronice cyfrowej. Teoria algebr Boole'a jest poddziałem matematyki na styku teorii porządków częściowych, algebry, logiki matematycznej i topologii.

88. Podaj tabele prawdy dla dwóch zdań logicznych: y=a+b oraz y=a*b.

89. Podaj prawa de Morgan'a.
    I prawo De Morgana (prawo zaprzeczenia alternatywy)
    Negacja alternatywy jest równoważna koniunkcji negacji
    
    II prawo De Morgana (prawo zaprzecza koniunkcje)
    Negacja koniunkcji jest równoważna alternatywie negacji
    
    gdzie p i q oznaczają zdania w sensie logiki.

90. Jaki operator logiczny ma najwyższy priorytet?

NOT

91. Co to są tablice Karnaugh'a?

92. Co to jest bramka logiczna?
    Element konstrukcyjny maszyn i mechanizmów(zazwyczaj: układ scalony).

93. O czym mówi twierdzenie Gödel'a?

94. Podaj symbol bramki cyfrowej realizującej funkcje NOT oraz OR.
    NOT ~ OR υ

95. Co to jest układ kombinacyjny?
    Jest jednym z rodzajów układów cyfrowych. Charakteryzuje się tym, że stan wyjść zależy wyłącznie od stanu wejść.

96. Co to jest układ sekwencyjny?
    Jest jednym z rodzajów układów cyfrowych. Charakteryzuje się tym, że stan wyjść y zależy od stanu wejść x oraz od poprzedniego stanu, zwanym stanem wewnętrznym, pamiętanego w zespole rejestrów (pamięci).

97. Podaj rozwinięcie skrótu LSI, MSI oraz VLSI, ULSI.
    Large Scale of Integration; Medium Scale of Integration; Large Scale of Integration; Ultra Large Scale of Integration; SSI - Small Scale of Integration.

98. Co to jest problem typu NP zupełny?
    To problem, który należy do klasy NP oraz dowolny problem należący do NP może być do niego zredukowany w czasie wielomianowym. Czasami zamiast redukcji w czasie wielomianowym używa się redukcji w pamięci logarytmicznej.

99. Dlaczego problem typu NP., NP. zupełne są tak trudne w realizacji lub też praktycznie niemożliwe do wykonania w rozsądnym czasie.

100. Kim był Alan Tubing?
     Angielski matematyk, twórca maszyny Turinga i jeden z twórców informatyki. Po wojnie Alan Turing zaprojektował jeden z pierwszych elektronicznych, programowanych komputerów. Był również pomysłodawcą tak zwanego testu Turinga - eksperymentu będącego próbą formalnego zdefiniowania sztucznej inteligencji.

---