Pytania egzaminacyjne - PODSTAWY INFORMATYKI 2002

1. Pojęcie i przykłady algorytmów, metody zapisu, szeregowa i równoległa realizacja algorytmów.

CIEKAWOSTKA

Za twórcę pierwszego niebanalnego algorytmu uważa się Euklidesa (400 - 300r. pne) Jt. Algorytm NWD.

Algorytm - uporządkowany zbiór operacji, taki, że po ich wykonaniu otrzymuje się rozwiązanie dowolnego zadania
z określonej klasy zadań.

Cechy algorytmów:

• ogólność - algorytm przeznaczony jest do rozwiązywania określonej klasy zadań, a nie tylko pojedynczego szczególnego przypadku (np. rozwiązywanie równań różniczkowych 2 rzędu, a nie konkretnego równania)

• skończoność - możliwość uzyskania rozwiązania problemu w skończonej ilości kroków.

• określoność - jednoznaczność wszystkich wszystkich wykonywanych w nim operacji

• efektywność - czas potrzebny na wykonanie tego algorytmu (najczęściej liczony w umownych jednostkach, np. ilości wykonywanych operacji w zależności od danych wejściowych) lub zapotrzebowanie algorytmu na pamięć.

Przykłady

P1. Podać algorytm obliczania:
gdzie x_i ­- dowolna liczba rzeczywista

Rozw:

1. y:=1 ; idź do 2

2. i:=1 ; idź do 3

3. y:=y*x_i ; idź do 4

4. Czy i=n?, jeżeli TAK -> koniec, jeżeli NIE - idź do 5

5. i:=i+1 ; idź do 3

Schemat blokowy:

P2. Podać algorytm znajdujący wartość y=Max {x_i}, i∈<1,n>

Schemat blokowy:

Metody zapisu:

Język naturalny - najbardziej rozpowszechniony.

Zalety: prostota, brak potrzeby przyswajania specyficznych konstrukcji formalnych, szeroki zasób możliwego do użycia słownictwa.

Wady: mała precyzja oraz możliwość błędnej interpretacji (mała ścisłość zapisu), mała zwięzłość.

Schematy blokowe - sformalizowany zapis algorytmów. Algorytm prezentowany jest w postaci bloków operacyjnych oraz linii ilustrujących przepływ sterowania. Jt. Sposób graficzny.

Wada: brak (technicznie) możliwości przedstawienia dużych algorytmów.

Języki formalne - najczęściej używany w praktyce sposób zapisu algorytmu. Językiem formalnym może być dowolny z języków programowania lub specjalnie stworzona w tym celu notacja. Zapewnia ścisłość zapisu.

Funkcje rekurencyjne - używany wszędzie tam, gdzie łatwo można przedstawić rozwiązanie za pomocą rekurencji.

Szeregowa realizacja algorytmów

Instrukcje wykonywane są sekwencyjnie jedna po drugiej, według kolejności wyznaczonej przepływem sterowania.

Oznaczenia:

n+1 - ilość operacji w algorytmie,

o_i - operacja i-ta,

t(x) - chwila czasu, w której wykonywana jest operacja x.

Każdy algorytm posiada charakterystyczną dla niego kolejność operacji, ponumerowanych od 1 do n+1 włącznie.

Znaczy to, że każda operacja o_i musi się zakończyć zanim rozpocznie się operacja o_i+1 lub koniec operacji o_i następuje równocześnie z początkiem operacji o_i+1.

Równoległa realizacja algorytmów

Algorytmy równoległe realizowane są na maszynach wieloprocesorowych

Ten zapis oznacza z kolei, że istnieje taka operacja o_i, która kończy się po rozpoczęciu operacji o_i+1

2. Efektywność algorytmów, efektywność czasowa i pamięciowa i zależności między nimi, przykłady oceny efektywności algorytmów dla szeregowych i równoległych algorytmów sortowania.

Efektywność algorytmów jest podstawowym kryterium ich porównania. Można ją rozpatrywać pod dwoma względami: czasu wykonania i zapotrzebowania na pamięć operacyjną. Aby uniezależnić otrzymane wyniki od maszyny na której realizowany jest algorytm, efektywność czasową algorytmu wyznaczamy poprzez określenie liczby wykonań poszczególnych jego operacji. Efektywność jest funkcją danych wejściowych.

3. Twierdzenie o realizowalności algorytmów w maszynie Turinga, tablica charakterystyczna, przykłady zaprogramowania algorytmów w maszynie Turinga

Maszyna Turinga - automat abstrakcyjny, służący do analizy algorytmów. Składa się z podzielonej na kratki nieskończenie długiej taśmy i głowicy przesuwające się nad taśma. Głowica ma możliwość czytania i zapisywania symboli na taśmę. Pojęcia podstawowe:

1. Zbiór symboli S = {s_i} - zbiór symboli, przetwarzanych przez maszynę Turinga, przyjęty jako alfabet

2. Napis - ciąg symboli alfabetu S

3. Głowica - rozróżnia, czyta i zapisuje symbole alfabetu S. Może przesuwać się wzdłuż taśmy. Przyjmuje zawsze jeden ze stanów q₁,…,q_m.

4. Stan maszyny - jednoznacznie określony stan głowicy qj i odczytany przez nią symbol s_i; S_ij=(s_i,q_j)

5. Ruch maszyny - akcja, jaką ma wykonać maszyna Turinga. Ruch maszyny jest reakcją na stan S_ij. Opisywany jest za pomocą 3 parametrów R_ij = (s_k, K, q_l). s_k - symbol, który ma być zapisany na głowicę,
   K - sposób przesunięcia taśmy, q_l - stan, do którego ma przejść głowica.

Każdy ruch R_ij maszyny związany jest jednoznacznie ze stanem maszyny S_ij. R_ij = T(S_ij)

T - tablica charakterystyczna maszyny Turinga. (tablice przedstawione będą w przykładach tu nie ma sensu tego robić)

TWIERDZENIE:

Każdy algorytm może być realizowany przez odpowiednio zaprogramowaną (za pomocą tablicy charakterystycznej) maszynę Turinga.

Przykład 1

W zbiorze napisów trójliterowych utworzonych z liter a,b,c tylko napis abc jest poprawny. Podać algorytm rozpoznawania tego napisu.

Rozwiązanie

Algorytm:

1. Pobierz symbol. Jeżeli jest nim a, to pobierz następny symbol i idź do 2, w przeciwnym razie idź do 4.

2. Jeżeli pobranym symbolem jest b, pobierz następny symbol i idź do 3, jeżeli nie - idź do 4.

3. Jeżeli pobranym symbolem jest c, idź do 5, jeżeli nie - idź do 4.

4. Sygnalizuj nieprawidłowy napis.

5. Sygnalizuj napis poprawny.

Ponieważ algorytm nie wymaga zapisywania symboli na taśmę i jednocześnie nie występuje konieczność zmiany kierunku przesuwania taśmy, do opisu ruchu maszyny użyję następujących symboli:

P - pobierz następny symbol,

N - nie pobieraj niczego,

q_n - przejdź do stanu n.

W takim razie ruch charakteryzuje równanie R_ij = (K, q_l)

Tablica charakterystyczna

	q1	q2	q3	q4	q5
a	Pq2	Nq4	Nq4	Nq4	Nq5
b	Nq4	Pq3	Nq4	Nq4	Nq5
c	Nq4	Nq4	Nq5	Nq4	Nq5

Stany q₄ i q₅ są stanami końcowymi. Stan q₄ oznacza napis niepoprawny stan q₅ poprawny.

Przykład 2

Zaprojektować maszynę Turinga obliczającą sumę dowolnej liczby zapisanej w systemie dziesiętnym i liczby 1.

Rozwiązanie

Aby do dowolnej liczby dodać 1 trzeba przeanalizować jej ostatnią cyfrę. Jeżeli jest to 0-8, to dodanie 1 sprowadzi się do zapisu w tym miejscu danej cyfry zwiększonej o 1 tzn. jednej z cyfr 1-9. Jeżeli ostatnią cyfrą jest 9, to należy w jej miejscu wpisać 0 i dodać 1 do cyfry przedostatniej lub napisać 1, jeżeli nie występuje cyfra przedostatnia.

Algorytm:

1. Jeżeli cyfra z zakresu 0-8 pisz odpowiednio 1-9 i idź do 3, w przeciwnym wypadku pisz 0, przesuń głowicę w lewo i idź do 2

2. Jeżeli miejsce puste Ø pisz 1, idź do 3, jeśli nie idź do 1.

3. Sygnalizuj koniec.

Np.

Stan maszyny	q1	q2	q1	q3
Stan taśmy	89 ↑	80 ↑	80 ↑	90 ↑

Każda kolumna to jeden krok algorytmu a strzałki pionowe to pozycja głowicy maszyny dla danego stanu.

Tablica charakterystyczna

	q1	q2	q3
9	0Lq2	q1	q3
Ø	-	1q3	q3
0	1q3	q1	q3
1	2q3	q1	q3
…	…	…	…
8	9q3	q1	q3

4. Definicja gramatyki, przykłady gramatyk, notacja BNF

Języki formalne umożliwiają ścisłe i jednoznaczne opisy tworzonych konstrukcji. Za twórcę lingwistyki formalnej uważa się Chomsky'ego.

Język formalny składa się z:

alfabet - dowolny zbiór symboli, z których będą zestawiane słowa języka

słowo - uporządkowany ciąg symboli alfabetu

język - zbiór wszystkich możliwych słów

gramatyka - zbiór reguł umożliwiających generowanie słów danego języka jak też rozróżnienie słów poprawnie zbudowanych od niepoprawnie zbudowanych

Przykład 1

Alfabet - {a, b}

Słowo - np. aaaab, bbbb, a, b

Gramatyka - Reguła 1: a jest poprawne (tzn. słowo złożone z pojedynczego symbolu a jest poprawne)

Reguła 2: Jeżeli α jest poprawne to aαb też jest poprawne.

Przykłady poprawnych słów:

a - na podst. Reguły 1

aab - na podst. Reguły 1 i Reguły 2

aaabb - na podst. Reguły 1 i dwukrotnie stosowanej Reguły 2

Gramatyki Chomsky'ego

Gramatykę Chomsky'ego określa związek 4 elementów:

G = < V, Σ, P, σ >

V - alfabet terminalny: określa zbiór symboli, z których będą budowane słowa generowane przez gramatykę G

Σ - alfabet metajęzyczny: zbiór symboli pomocniczych używanych przy określaniu reguł opisujących konstruowanie słów poprawnych w sensie gramatyki G

P - lista produkcji: zestaw reguł

σ - głowa (aksjomat) języka: podaje z jakiej konstrukcji można wyprowadzić wszystkie generowane przez gramatykę G napisy.

Język generowany przez gramatykę G jt. Zbiór wszystkich możliwych słów powstałych na bazie listy produkcji i wyprowadzonych z głowy języka.

L(G) = { x: x ∈ Z ∧ σ ⇒ x }

Z - zbiór wszystkich możliwych słów

⇒ - ozn. proces wywodu słowa x z głowy σ na podstawie listy produkcji P

Przykład 2

Rozważamy gramatykę generującą proste wyrażenia arytmetyczne. Poniżej poszczególne elementy składowe gramatyki.

Alfabet terminalny V: V = { a, b, d, +, *, (, ) }

Alfabet metajęzyczny Σ: Σ = { W, S, C }

Semantyka powyższych symboli jest następująca:

W - wyrażenie

S - składnik

C - czynnik

Głowa języka σ: σ = W

Lista produkcji P:

P = { W → S

W → W + S

S → C

S → C * S

S → S * C

C → a

C → b

C → d

S → ( W ) }

Powyższy zapis sprawdzamy wyprowadzając napis ( a + b ) * d z głowy języka na podstawie listy produkcji, ma ono postać:

W → S → C * S → (W) * S → (W + S) * C → (S + S) * C → (C + C) * C → (a + c) * d

Udało się! :-) wyprowadzić zadany napis. Jest on więc prostym wyrażeniem arytmetycznym. Poniżej jeszcze jeden sposób dowodzenia poprawności napisu - drzewo wywodu:

			W
			S
C						S
( W )						C
W + S						d
S			C
C			b
A

Notacja BNF

Notacja Backusa (zw. rozszerzoną) jest jednym ze sposobów prezentowania listy produktów.

Symbole używane w notacji BNF:

<> - zapis symboli metajęzyka

::= - „jest zdefiniowany jako”

| - alternatywa

Przykład 3

Przedstawimy listę produkcji z poprzedniego przykładu za pomocą notacji BNF:

<W> ::= <S> | <W> + <S> | <S> + <W>

<S> ::= <C> | <C> * <S> | <S> * <C>

<C> ::= (<W>) | a | b | d

Symbole zapisane bez nawiasów ostrych <> i nie będące symbolami używanymi przez notację Backusa sa symbolami terminalnymi.

Innymi słowy odróżniane są symbole terminalne od pomocniczych

5. Algebra Łukasiewicza, pojęcie translacji i przykład algorytmu translacji wyrażeń arytmetycznych z notacji nawiasowej na odwrotną notację polską

Zwana inaczej Odwrotną Notacją Polską (ONP).Jest to przykład notacji umożliwiającej zapisanie dowolnego wyrażenia arytmetycznego bez użycia nawiasów zmieniających kolejność wykonywanych działań.

Ze względu na łatwość obliczania wyrażeń zpisanych w ONP przy użyciu stosu znalazła ona szerokie zastosowanie w arytmetyce komputerów.

Gramatyka prostych wyrażeń arytmatycznych w ONP :

V = {a,b,d,+,*}

P: <W> ::= <Z><Z><O> | <Z>

<Z> ::= <X><X><O> | <X>

<X> ::= a | b | d

<O> ::= + | *

A oto przykład prostego wyrażenia arytmetycznego i odpowiadający mu zapis w ONP

P: <W> ::= <O><Z><Z> | <Z>

<Z> ::= <O><X><X> | <X>

<X> ::= a | b | d

<O> ::= + | *

Należy zaznaczyć że w podanych tutaj(buehehehehe rotfl ;)) definicjach gramatyk zbiór symboli terminalnych został ograniczony jedynie w celu zwiększenia czytelności.Nic nie stoi na przeszkodzie aby zdefiniować gramatyke ONP na podstawie pełnego zestawu symboli stosowanego w matematyce.

Algorytm obliczający wartość wyrażenia zapisanego w ONP :

T

N

T

N T

Przykład: Obliczyć wyrażenie : 2 3 4 5 + * +

Krok Wejście Stos

1. 2 2

2. 3 2 3

3. 4 2 3 4

4. 5 2 3 4 5

5. + 2 3 9

6. * 2 27

7. + 29

Translacja - tłumaczenie tekstu zapisanego w jednym języku formalnym na inny język.

Jako przykład można przytoczyć przetworzenie tekstu zapisanego w jakimś języku wysokiego poziomu na kod maszynowy.

DEFINICJA: Translacja to przekład tekstów zredagowanych w jednym języku źródłowym na równoważny semantycznie tekst w innym języku - wynikowym

Podajmy teraz algorytm dokonujacy translacji prostych wyrazen arytmetycznych w konwersji nawiasowej w proste wyrazenia arytmetyczne w ONP

1.Priorytety działań

Priorytet Operacja

1 . *

• +

W konwersji nawiasowej priorytet działania oraz nawiasy wpływają na kolejność w jakiej wyrażenie jest obliczane np.: a+b*d obliczamy najpierw b*d a potem dodajemy.

W ONP priorytety zależne są jedyne od miejsca w którym znajduje się operator.

Aby dokonać konwersji będziemy pobierać kolejne znaki wyrażenia które ma zostać przekształcone znak po znaku począwszy od lewej do prawej dalsze post zależne jest od pobranego symbolu, jeśli pobrany znak jest :

- argumentem to przesyłamy go na wyjście

- nawiasem otwierającym”(„ to kładziemy go na stos

-nawiasem zamykającym „)” to zawartość stosu aż do znaku „(” przesyłamy na wyjście i usuwamy znak „(”

-operatorem to przeglądamy stos i szukamy operatora o priorytecie wyższym lub równym jeśli taki znajdziemy to przesyłamy zawartość stosu na wyjście jeśli nie to operator odkładamy na stos. Stos przeszukujemy do napotkania nawiasu „(” lub do końca stosu.

-znacznikiem końca wprowadzania napisu to kopiujemy zawartość stosu na wyjście w przeciwnym wypadku sygnalizujemy błąd.

Dokonać konwersji wyrażenia (((a)) + b + d )*( d + e ) na ONP:

T

N

T

N

T

N

T N

N

T

N T

Postępując zgodnie z danym algorytmem otrzymamy kolejno :

Wejście Stos Wyjście

( (

( ((

( (((

a ((( a

) ((

) (

+ (+

b (+ b

+ (++

d (++ d

) ++

* *

( *(

d *( d

+ *(+

e *(+ e

) * +

*

Tak więc wyrażeniu (((a)) + b + d )*( d + e ) odpowiada wyrażenie abd++de+* w ONP

6. Elementy konstrukcyjne komputera. Rejestry, liczniki, kodery i dekodery. Magistrale i problemy związane z ich projektowaniem.

Elementy konstrukcyjne komputera:

1. Bramki: AND, OR, NOT, NAND, NOR - wybaczcie, ale nie będę opisywał bramek, bo “koń jaki jest każdy widzi”

2. Przerzutniki:

1. SR (nie będę dokładnie opisywał, wpiszę tylko te informacje których mogliśmy nie mieć na TA i tabelę stanów) - istotną cechą przerzutnika jest jego niejednoznaczność. Jeżeli na jego obu wejściach pojawi się jednocześnie sygnał jedynki logicznej, stan obu wyjść jest stanem niskim. Jest to błędem, gdyż opis przerzutnika sr zakłada, że jedno z wyjść jest negacją drugiego, a w tym przypadku nie jest to spełnione.

qk	rk	sk	qk+1
1	1	1	?
1	1	0	0
1	0	1	1
1	0	0	1
0	1	1	?
0	1	0	0
0	0	1	1
0	0	0	0

2. JK - w stosunku do sr różni się tym, że dla sygnałów wejściowych j=k=1 zmienia on stan obu wyjść na przeciwny.

qk	jk	kk	qk+1
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	0

3. Pamięć Operacyjna (PaO) - rozróżniamy magnetyczne(ruchome) i półprzewodnikowe (statyczne(na przerzutnikach) i dynamiczne(oparte o kondensatory i tranzystory unipolarne).

Rejestry

Rejestr - zbiór przerzutników służących do przechowywania informacji cyfrowej. Wyróżniamy rejestry szeregowe i równoległe. W dalszych rozważaniach wykorzystamy rejestr równoległy (układ niepowiązanych ze sobą przerzutników), a operacje wpisu lub zerowania wykonywane są na wszystkich bitach (przerzutnikach) równolegle.

Operacji wpisu do rejestru n-bitowego można dokonać stosując jeden z dwu możliwych układów. Pierwszy to układ wpisu z uprzednim zerowaniem, w którym przed ustawieniem odpowiednich przerzutników musi nastąpić zerowanie (do przerzutników wpisywane są tylko jedynki, dlatego wymagane jest zerowanie) (ponieważ nie będzie rysunku wyobraźcie sobie dwa rzędy przerzutników sr - rząd górny to przerzutniki A, dolny B, na wejście r każdego z przerzutników A wchodzi sygnał wpis, a na wejście s każdego przerzutnika A wchodzi przez AND sygnał wpis i sygnał Q przerzutnika B). Innym rozwiązaniem jest układ z wejściem forsowanym (na wejście r każdego przerzutnika A wchodzi przez AND sygnał wpis i nieQ z przerzutnika B, na wejście s przez AND sygnał wpis i Q z przerzutnika B). Jeżeli w układzie tym wejście q któregokolwiek z przerzutników B jest w stanie wysokim i jednocześnie sygnał wpis=1, to na wejściu s odpowiedniego przerzutnika A również pojawi się sygnał jedynki i przejdzie on w stan wysoki. Dla q=0 i wpis=1 przerzutnik A zostaje wyzerowany i jest w stanie niskim.

Kodery i dekodery

Informacja w maszynach cyfrowych może być zapisywana za pomocą zmiennych binarnych dwoma sposobami:

1. Zbiorowi danych elementarnych odpowiada równoliczny zbiór zmiennych binarnych, stąd każdej danej odpowiada jedna zmienna.

2. Zbiorowi danych elementarnych odpowiada kombinacja zmiennych binarnych.

Dysponując n zmiennymi binarnymi można sposobem pierwszym zapisać n danych, sposobem drugim 2ⁿ danych.

Kodowaniem nazywamy przejście z pierwszego sposobu na drugi, a operację odwrotną dekodowaniem. Odpowiadające temu układy to koder i dekoder.

Jednym z prostszych kod jest kod dwójkowy, w którym kolejnym danym wejściowym L₀ do L_n zostaj przyporządkowana kombinacja zmiennych binarnych z₁ do z_m, które wartościowane są jako kolejne potęgi dwójki. Suma wartości zmiennych daje numer danej wejściowej.

Przykład. Jeżeli na wejściu L₅ pojawi się sygnał, na wyjściu będzie stan odpowiadający liczbie 5 w systemie dwójkowym, czyli 101.

Rozpatrzmy koder dwójkowy, posiadający osiem wejść i trzy wyjścia (2³ = 8). Tablica poniżej pokazuje zależności, jakie mogą wystąpić w takim układzie. Należy pamiętać, że na wejściu jedynka logiczna może pojawić się tylko na jednej linii.

Numer wybranego wejścia	z3	z2	z1
0	0	0	0
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7	1	1	1

Z tablicy można ułożyć równania zmiennych:

z₁ = L₁ + L₃ + L₅ + L₇

z₂ = L₂ + L₃ + L₆ + L₇

z₃ = L₄ + L₅ + L₆ + L₇

Rozwiązanie równań jest układ zbudowany na bramkach OR lub z zastosowaniem matrycy kodowej.

Przy realizacji zadania odwrotnego można skorzystać z tej samej tablicy. Równania napisane na jej podstawie mają postać:

L₀ = nieZ₁ * nieZ₂ * nieZ₃

L₁ = Z₁ * nieZ₂ * nieZ₃

L₂ = nieZ₁ * Z₂ * nieZ₃

…

L₇ = Z₁ * Z₂ * Z₃

Podobnie rozwiązanie może być na bramkach (tym razem AND) lub matrycy.

Magistrale i problemy związane z ich projektowaniem

Magistrala - zbiór przewodów (s_i do s_n) łączących poszczególne elementy (rejestry) komputera. O tym, z i do którego rejestru dana zostanie przesłana decydują sygnały sterujące (dla każdego rejestru osobny). Przesyły międzymagistralowe to multipleksowanie. Wyróżniamy multipleksowanie rozwidlające - wpisanie stanu magistrali na jedną z kilku wybranych, oraz koncentrujące - przepisanie stanu wybranej magistrali na daną. Sygnały sterujące przepływem danych są rozróżniane na poziomowe i impulsowe. Sygnał wyjściowy powinien zostać wysłany odpowiednio wcześniej i trwać przez dłuższy okres czasu tak, aby był sygnałem stabilnym w momencie odczytu
(np. przez jakiś rejestr). Przyjęto, że sygnały sterujące wyjściami poszczególnych elementów są sygnałami poziomowymi (na schemacie oznaczone liniami z przekreśleniem) - czas trwania = cały takt. Sygnały impulsowe występując pod koniec taktu i mają wartość 1.

Problemy z projektowaniem magistral biorą się stąd, że magistrala jest linią długą i dlatego:

1. Zniekształca sygnał (np. z poziomego robi paraboliczny)

2. Opóźnia sygnał

3. Powoduje, że sygnał traci na mocy

Liczniki

Wspomnę krótko, że na wykładzie był tylko licznik z krążącą jedynką (na przerzutnikach sr mam nadzieję, że dacie radę go narysować, nie mam skanera, więc nie da rady go tu zamieścić), w książce o licznikach nie ma nic.

7. Jednostka arytmetyczno-logiczna, jej konstrukcja i działanie.

JAL - z ang. ALU = Arithmetic-Logic Unit.

Podstawowy zespół funkcjonalny procesora. Służy do wykonywania operacji arytmetycznych i logicznych (jak sama nazwa na to wskazuje).

Zasady operacji na liczbach zapisanych dwójkowo w systemie binarnym.

Liczba całkowita w systemie dwójkowym jest postaci : a_n a_n-1... a_i ... a_{0 ,} a_{i =} {0, 1}.

a_n - bit najstarszy, a₀ - bit najmłodszy.

Liczba dwójkowa system dziesiętny: L = : a_n * 2ⁿ + a_{n - 1} * 2^{n - 1} + ... + a₁ * 2¹ + a₀ * 2⁰

Podstawową operacją JAL jest dodawanie. Operacją dodawania można wykonać odejmowanie (suma liczb dod. i ujemn.), mnożenie (dodawanie wielokrotne).

Zasady przy dodawaniu liczb dwójkowych : 0 + 0 = 00, 0 + 1 = 01, 1 + 0 = 01, 1 + 1 - 10, gdzie ostatni zapis oznacza 0 na pozycji, na której jest aktualnie wykonywane dodawanie i dodanie 1 na pozycji bardziej znaczącej liczby, czyli przeniesienie.

Zapisanie liczby całkowitej wymaga dodatkowego bitu znaku : 0 - liczba dodatnia, 1 - liczba ujemna. Bit znaku jest najstarszym bitem liczby binarnej.

Zapis liczby ujemnej w kodzie „uzupełnieniowym do 2” : liczbę ujemną tworzy się przez negację liczby dodatniej, a następnie dodania 1, pamiętając również o 1 na pozycji znaku. Przykład:

(+5) = 0.101

(-5) =

1. negacja 0.101 czyli 1.010

2. następnie 1.010 + 1

3. ostatecznie 1.011.

Elementy składowe JAL.

Podstawowe techniki realizacji operacji na słowach maszynowych:

1. szeregowa - wykonywanie operacji bit po bicie, nie stosowana już.

2. równoległa - operację wykonuje się na wszystkich n bitach, przez n operatorów elementarnych, stosowana w „Maszynie W”.

Moduły układu wykonującego operację (zależną od funkcji obwodu elementarnego) na operandach znajdujących się w przerzutnikach Z1 i Z2.




Po wprowadzeniu sygnału sterującego następuje wykonanie działania. Dla słowa n-bitowego potrzeba n modułów, ponieważ jeden moduł operuje na jednym bicie operandów. Jest to układ równoległy. Rejestr W nazywany jest akumulatorem. Służy do przechowywania wyniku operacji lub zastępuje jeden z rejestrów wejściowych. Pokazano to na poniższym rysunku. Mówimy wtedy o operatorze elementarnym z akumulatorem.




Weak - sygnał wpisu do akumulatora liczby z wyjścia obwodu elementarnego, jest to wynik operacji.

Oper - synonim sygnału sterującego, wprowadza zawartość akumulatora do układu jako drugiego elementu operacji. Oper zostaje po jakimś czasie usunięty. Na jego miejsce pojawią się sygnały dod, ode, przep. Jest to sygnał poziomowy.

Układ realizujący przepisywanie. W momencie pojawienia się sygnału weak sygnał prosty z przerzutnika Z doprowadzany jest do wejścia s akumulatora, a sygnał zanegowany do wejścia r.

Układ realizujący sumę logiczną. Działanie układu przedstawia poniższa tabela. AK' to wartości, które mogą wystąpić w akumulatorze po wykonaniu operacji sumy. Z AK AK' 1 1 1 1 0 1 0 1 1 0 0 0

Półsumatory

Jego zadaniem jest dodawanie dwóch cyfr.

2 wejścia : ai - dodajnik i-tego bitu bi - dodajna i-tego bitu

2 wyjścia: suma si przeniesienie pi+1




Wyjście sumy na i-tej pozycji jest ustawione, jeżeli na wejściach jest nieparzysta liczba jedynek, czyli gdy jedno z wejść jest ustawione, a drugie nie. Z kolei sygnał przeniesienia pojawia się na wyjściu gdy na wejściu wystąpiłyby dwie jedynki.

s_i = ( !a_i + b_i ) + ( a_i + !b_i )

p_i = a_i * b_i

! - negacja

ai	bi	si	pi+1
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Sumatory

Sumator wykonuje dodawanie z przeniesieniem. Umożliwia on dodawanie liczb wielocyfrowych. Wymaga to uwzględnienia poszczególnych bitów i przeniesienia z pozycji mniej znaczącej. Aby to zrealizować bierze się pod uwagę również stan wejścia p_i.




Za pomocą sumatorów jednobitowych można budować sumatory liczb n-bitowych. Przeniesienie z ostatniego członu może zostać wykorzystane jako sygnał błędu przepełnienia sumatora.




ai	bi	pi	si	pi+1
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

Struktura JAL




Przedstawiona struktura wykonuje operację na zawartości akumulatora i magistrali S.

Weak - sygnał impulsowy, zezwala na zmianę wartości akumulatora (każda operacja musi zakończyć się wywołaniem tego sygnału)

Przep - przepisanie danej z magistrali do akumulatora

Zer - zerowanie AK (na wejście r podano 1 logiczną)

Dod, Ode - na wejście sumatora wprowadzane są dane z magistrali, a następnie otwierane za pomocą tych sygnałów. Sygnały te do drugiego wejścia sumatora podają w tym samym momencie zawartość akumulatora.

Oznaczenia JAL na schematach maszyn cyfrowych.




Podstawy informatyki - egzamin ustny 2002 2

START

y:=1

i:=1

y:=y*x_i

i=n

KONIEC

i:=i+1

N

T

START

i:=1

y:=x_i

i=n

KONIEC

i:=i+1

N

T

x_i>y

N

T

START

Pobierz symbol z lewej ku prawej

argument

operator

stos

Pobierz argumenty ze stosu wykonaj działanie wynik na stos

0

BŁĄD

KONIEC

START

Czytaj z lewej ku prawej

argument

(

)

operator

0

Wyjście

Stos

Zawartość stosu aż do ( na wyjście

Czy wyższy w stosie od ( lub dna

stos

Zawartość stosu do ( lub do dna na wyjście

BŁAD

KONIEC

---