Modul_1
Uogólniony wzór na informacje według Shannona: (slajd 40)
gdzie:
I = ilość informacji
P = prawdopodobieństwo wystąpienia zdarzenia
N = logarytmiczna podstawa miary informacji
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
Czy obecne komputery wykorzystują system binarny?(TAK/NIE) (slajd 42)
TAK
Co to jest bit? (slajd 42-43)
bit - najmniejsza nieadresowana jednostka pamięci
Co to jest bajt? (slajd 42-43)
Bajt - najmniejsza adresowalna jednostka pamięci
Co to jest adres komórki? (slajd 42-43)
adres komórki - określa położenie pojedynczej komórki pamieci
Z ilu bitów składa się oktet? (slajd 42)
oktet = 8 bitów = 1 bajt
Przedstawić matryce logiczną (tablice prawdy) dla: negacji (slajd 48-49)
Przedstawić matryce logiczną (tablice prawdy) dla: koniunkcji (slajd 48-49)
Przedstawić matryce logiczną (tablice prawdy) dla: alternatywy niewykluczającej (slajd 48-49)
Przedstawić matryce logiczną (tablice prawdy) dla: równoważności (slajd 48-49)
Przedstawić matryce logiczną (tablice prawdy) dla: alternatywy wykluczającej (slajd 48-49)
Wymień prawa algebry Bool'a (slajd 55)
Modul 2
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
Wymień trzy powszechnie stosowane systemy pozycyjne: (slajd 4)
DEC - system dziesiętny
NKB - system binarny(dwójkowy)
OCT - system ósemkowy
HEX - system szesnastkowy
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.
Wzór na wartość liczby w systemie o podstawie R (slajd 7)
L - wartość liczby w systemie dziesiętnym
Ri - podstawa systemu dla i-tej cyfry
ai - i-ta cyfra
Zakres wartości N-cyfrowej liczby w systemie o stałej podstawie R: (slajd 8)
LMIN=0, LMAX=RN-1
lub
0:RN-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
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]
Czy kod BCD jest wykorzystywany do unikania tzw. zjawiska hazardu?(TAK/NIE) (slajd 30)
NIE
Czy kod Graya jest szesnastkowym systemem liczbowym?(TAK/NIE) (slajd 30)
NIE
Modul 3
Wymień minimum trzy podstawowe typy danych: (slajd 4)
Podstawowe typy danych: typ całkowity, zmiennoprzecinkowy, stałopozycyjny, znakowy, logiczny
Czy istnieją abstrakcyjne typy danych(TAK/NIE) (slajd 4)
TAK
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
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
Adresowanie jednowymiarowej komórki tablicy: (slajd 10)
CellAddress = BaseAddress + Index * sizeof(cell)
Adresowanie dwuwymiarowej komórki tablicy: (slajd 12)
CellAddress = BaseAddress + (ColIndex * N + RowIndex) * sizeof(cell)
CellAddress = BaseAddress + (RowIndex * M + ColIndex) * sizeof(cell)
Modul_5
Czy algorytm musi być uniwersalny? (slajd 4)
TAK
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
Narysuj trzy symbole blokowe i nazwij je (slajd 7-11)
Co to jest algorytm rekurencyjny? (slajd 24)
Algorytm rekurencyjny to inaczej podprogram, który wywołuje sam siebie
Modul_6
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.
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
Czy maszyna Turinga jest abstrakcyjnym, uniwersalnym modelem komputerem?(TAK/NIE) (slajd 17)
TAK
Czy liczba programów dla maszyny Turinga jest skończona?(TAK/NIE) (slajd 17)
NIE, jest nieskończona
Czym jest klasa zadań algorytmicznych? (slajd 23)
Klasa zadań algorytmicznych jest to zbiór problemów algorytmicznych o podobnej złożoności obliczeniowej
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
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
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