Modul_1

  1. Uogólniony wzór na informacje według Shannona: (slajd 40)

0x01 graphic

gdzie:

I = ilość informacji

P = prawdopodobieństwo wystąpienia zdarzenia

N = logarytmiczna podstawa miary informacji

  1. Wymień trzy jednostki stosowane do określania ilości informacji w systemach komputerowych: (slajd 41)

bit -jednostka bazująca na logarytmie o podstawie 2

dit - jednostka bazujaca na logarytmie o podstawie 10

nit - jednostka bazująca na logarytmie naturalnym

  1. Czy obecne komputery wykorzystują system binarny?(TAK/NIE) (slajd 42)

TAK

  1. Co to jest bit? (slajd 42-43)

bit - najmniejsza nieadresowana jednostka pamięci

  1. Co to jest bajt? (slajd 42-43)

Bajt - najmniejsza adresowalna jednostka pamięci

  1. Co to jest adres komórki? (slajd 42-43)

adres komórki - określa położenie pojedynczej komórki pamieci

  1. Z ilu bitów składa się oktet? (slajd 42)

oktet = 8 bitów = 1 bajt

  1. Przedstawić matryce logiczną (tablice prawdy) dla: negacji (slajd 48-49)

  1. Przedstawić matryce logiczną (tablice prawdy) dla: koniunkcji (slajd 48-49)

  1. Przedstawić matryce logiczną (tablice prawdy) dla: alternatywy niewykluczającej (slajd 48-49)

  1. Przedstawić matryce logiczną (tablice prawdy) dla: równoważności (slajd 48-49)

  1. Przedstawić matryce logiczną (tablice prawdy) dla: alternatywy wykluczającej (slajd 48-49)

0x01 graphic

0x01 graphic

  1. Wymień prawa algebry Bool'a (slajd 55)

0x01 graphic

Modul 2

  1. Czym jest system liczbowy? (slajd 4)

System liczbowy - określa jednolite zasady zapisu liczb oraz reguły działań arytmetycznych na liczbach. W szczególności definiuje: alfabet systemu, operatory arytmetyczne, znaki specjalne

  1. Wymień trzy powszechnie stosowane systemy pozycyjne: (slajd 4)

DEC - system dziesiętny

NKB - system binarny(dwójkowy)

OCT - system ósemkowy

HEX - system szesnastkowy

  1. Który z systemów jest jednocześnie pozycyjny i addytywny? (slajd 4)

System karbowany, który jest jednocześnie pozycyjnym systemem jedynkowym oraz addytywnym.

  1. Wzór na wartość liczby w systemie o podstawie R (slajd 7)

0x01 graphic

L - wartość liczby w systemie dziesiętnym

Ri - podstawa systemu dla i-tej cyfry

ai - i-ta cyfra

  1. Zakres wartości N-cyfrowej liczby w systemie o stałej podstawie R: (slajd 8)

LMIN=0, LMAX=RN-1

lub

0:RN-1

  1. Minimalna ilość cyfr potrzebna do zapisu liczby w zakresie [0…M] w systemie o stałej podstawie R: (slajd 8)

NMIN = floor[(logR M) + 1] = ceil[logR(M + 1)]

gdzie:

floor - jest funkcja zaokrąglającą argument w dół do najbliższej liczby całkowitej

ceil - jest funkcja zaokrąglającą argument w górę do najbliższej liczby całkowitej

  1. Wzór na dobór optymalnej podstawy systemu pozycyjnego: (slajd 9)

E(R, N) = R * N

gdzie:

R - jest podstawą systemu pozycyjnego

N - jest ilością cyfr potrzebnych do zapisania liczby z zakresu [0…M]

  1. Czy kod BCD jest wykorzystywany do unikania tzw. zjawiska hazardu?(TAK/NIE) (slajd 30)

NIE

  1. Czy kod Graya jest szesnastkowym systemem liczbowym?(TAK/NIE) (slajd 30)

NIE

Modul 3

  1. Wymień minimum trzy podstawowe typy danych: (slajd 4)

Podstawowe typy danych: typ całkowity, zmiennoprzecinkowy, stałopozycyjny, znakowy, logiczny

  1. Czy istnieją abstrakcyjne typy danych(TAK/NIE) (slajd 4)

TAK

  1. Co to jest zmienna? (slajd 6)

Zmienna - to obszar pamięci zarezerwowany do przechowywania wartości danego typu, którego zawartość może być modyfikowana w trakcie działania pogramu

  1. Co to jest stała? (slajd 6)

Stała - to obszar pamięci zarezerwowany do przechowywania wartości danego typu, którego zawartość zostaje ustalona raz w momencie rezerwacji i nie może być modyfikowana podczas działania programu

Modul_4

  1. Adresowanie jednowymiarowej komórki tablicy: (slajd 10)

CellAddress = BaseAddress + Index * sizeof(cell)

  1. Adresowanie dwuwymiarowej komórki tablicy: (slajd 12)

CellAddress = BaseAddress + (ColIndex * N + RowIndex) * sizeof(cell)

CellAddress = BaseAddress + (RowIndex * M + ColIndex) * sizeof(cell)

Modul_5

  1. Czy algorytm musi być uniwersalny? (slajd 4)

TAK

  1. Czym różni się algorytm deterministyczny od niedeterministycznego? (slajd 4)

Algorytm deterministyczny wielokrotnie uruchamiany z tym samym zestawem danych wejściowych, generuje za każdym razem te same wyniki, a algorytm niedeterministyczny, może generować różne wyniki

  1. Narysuj trzy symbole blokowe i nazwij je (slajd 7-11)

  1. Co to jest algorytm rekurencyjny? (slajd 24)

Algorytm rekurencyjny to inaczej podprogram, który wywołuje sam siebie

Modul_6

  1. O czym informuje złożoność obliczeniowa algorytmu? (slajd 5)

Złożoność obliczeniowa algorytmu informuje o szybkości wzrostu zapotrzebowania na zasoby teoretycznego modelu komputera, potrzebne do rozwiązania określonego zadania algorytmicznego, w zależności od wzrostu rozmiaru tego zadania.

  1. Podział złożoności obliczeniowej algorytmów ze względu na rodzaj zasobów (slajd 5)

złożoność czasowa - dotyczy ilości operacji elementarnych potrzebnych do rozwiązania zadania

złożoność pamięciowa - dotyczy ilości pamięci potrzebnej do rozwiązania zadania

  1. Czy maszyna Turinga jest abstrakcyjnym, uniwersalnym modelem komputerem?(TAK/NIE) (slajd 17)

TAK

  1. Czy liczba programów dla maszyny Turinga jest skończona?(TAK/NIE) (slajd 17)

NIE, jest nieskończona

  1. Czym jest klasa zadań algorytmicznych? (slajd 23)

Klasa zadań algorytmicznych jest to zbiór problemów algorytmicznych o podobnej złożoności obliczeniowej

  1. Charakterystyka zadania klasy P (slajd 23)

Zadania klasy P - zbiór zadań, dla których istnieją algorytmy wyznaczające ich rozwiązania w czasie wielomianowym na deterministycznej maszynie Turinga

  1. Charakterystyka zadania klasy NP (slajd 23)

Zadania klasy NP - zbiór zadań, dla których istnieją algorytmy wyznaczające ich rozwiązania w czasie wielomianowym na niedeterministycznej maszynie Turinga

  1. Wymień minimum trzy strategie algorytmiczne: (slajd 24-29)

- strategia wędruj i sprawdzaj

- strategia dziel i zwyciężaj

- strategia zachłanna

- programowanie dynamiczne

- przeszukiwanie probabilistyczne

- strategie ewolucyjne