Teoria informacji-zajmuje się badaniem problemów informacji oraz sposobów jej kodowania(podstawy Claude Shannon).

Teoria Shannona-każdemu znakowi odpowiada ciąg znaków(bitów)

Kod źródła-jest to zbiór wszystkich słów kodowych dla znaków(komunikatów) jakie dane źródło może wytworzyć

Długość słowa kodowego- liczba bitów wystepujących w słowie kodowym.

Kod parzystości-polega na tym, że każde słowo kodowe bedące ciągiem cyfr binarnych posiada na ustalonej dodatkowej pozycji cyfrę 1, gdy liczba jedynek w slowie jest nieparzysta lub cyfrę 0 w przypadku przeciwnym.

Kod parzystości krzyżowy-informacje są przesyłane jak w kodzie parzystości lecz po określonej liczbie słów kodowych wstawiane jest slowo parzystości, które posiada 1 bit na tych pozycjach, których suma jedynek w słowach poprzedzających slowo parzystości(od ostatniego sł. parzystości) jest nieparzysta.

Ilość jednostek informacji- log₂(1/p_i)

P_i- prawdopodobieństwo słowa kodowego

Średnia ważona ilości informacji-(entropia informacyjna)(H)[bit]

H=

Średnia ważona-długość słowa kodowego(L)

L=

p₁-prawdopodobieństwo wystąpienia i-tego komunikatu

d₁-długość słowa kodowego i-tego komunikatu

Redundancja danego sposobu kodowania dla źródła: różnica L-H

- Im mniejsza redundancja tym trudniej wykryc przekłamanie w transmisji

-Tw. Shanonna mówi, że redundancja jest liczbę nieujemną

-Pamięc nietrwała: to pamięć RAM

RAM-wielokrotny zapis i odczyt niesekwencyjny

ROM-jednokrotny zapis i wielokrotny odczyt

-Niepozycyjny system liczenia: system rzymski, pozostałe systemy pozycyjne

-Dwa bity mogą przyjmować cztery różne stany :00, 01, 10,11 trzy bity mogą przyjmować osiem stanów: 000, 001, 010, 100, 011, 101, 110, 111, Ciąg n bitów może przyjmować 2ⁿ różnych stanów.

-Bajt=8bitów, czyli binarna liczba 8-bitowa może przybierać jedną z 256 wartości (2 ⁸)

-Każdy element komputera połączony jest z główną magistralą:

-CPU połączony jest magistralą danych,

-pamięć magistralą adresową,

-system we/wy magistralą sterującą,

Procesor charakteryzują następujące elementy:

-długość słowa(słowo jest to ciąg ustalonej liczby bitów),

-liczba rejestrów(rejestr jest to układ pamiętający),

-lista rozkazów(rozkaz jest to informacja dla procesora jaką czynność ma wykonać)

Przykład. Źródło wytwarza dwa różne komunikaty z jednakowym prawdopodobieństwem p₁=p₂=0,5 lecz o różnych długościach d₁=6 bitów, d₂=2 bity. Śr. Długość słowa kodowego dla tego źródła wynosi: L=0,5(6+2)=4bity

Przykład.2 Określić redundancję dla źródła wysyłającego 4 rożne komunikaty.

nr	Prawdop.	Dł. Sł.
1	0,5	4
2	0,25	2
3	0,125	6
4	0,123	10

L=0,5*4+0,25*2+0,125*(6+10)=4,5[bit]

H=0,5*log₂2+0,25*log₂4+2*0,125*log₂8=1,75[bit]

L-H=4,5-1,75=2,75[bit]

Cechy poprawnego algorytmu:

1) uniwersalność(pozwala na rozwiązanie całej klasy zadań)

2)ścislość(czynność algorytmu jak i kolejnosc wykonania jest opisana jasno i wyraźnie

3)jednoznaczność(wielokrotne wykorzystanie dla takich samych danych prowadzi do uzyskania identycznych wyników

4)kompletność(uwzględnia wszystkie możliwe przypadki jakie mogą nastąpić podczas jego wykonania

5) skończoność(rozwiązanie otrzymamy po skończonej ilości czynności.

Podstawowe struktury danych:

1)Lista(dostęp do dowolnego elementu, wstawienie elementu, usuniecie elementu)

2)Stos(LIFO)(dostęp do ostatniego elementu)

3)Kolejka(FIFO)(pobierać elementy można tylko z początku, dopisywać elementy można na końcu)

4)Drzewa(składają się z węzłów i krawędzi; wyróżniony węzeł nazywamy korzeniem, drzewa krawędzie-gałęzie drzewa. Węzły z których wychodzi tylko jedna krawędź-liście, pozostałe-węzły wewnętrzne. Drzewo binarne-ojciec może mieć co najwyżej dwóch synow; ojciec(przodek)+syn(potomek);

drzewo BTS

5)Grafy(uporządkowane, nieuporzadkowane)

Notacja polska odwrotna-(ONP) jest sposobem zapisu wyrażeń arytmetycznych, w których znak wykonywanej operacji umieszczony jest po operandach (zapis postfiksowy) a nie pomiędzy nimi jak w zapisie algebraicznym (zapis infiksowy)

---