1.ARYTMETYKA DWOJKOWA DZIALAN ARYTM NA LICZB DWOJK B-Z ZNAKU Ukł cyfr dodaj arytm liczby dwójk naz się sumator.Aby dodać2liczby dwójk sumuje sie pary bitów na poszczeg poz, rozpocz od najmniej znacz bitu.Przy sumow bit na każdej pozycji należy uwz gl bit przenieś z niższ pozyc. Liczby dwójk mogą być dodaw tylko parami. Niemożn dodaw kilku liczb dwójkowych. Dodaw większ iloś liczb dwójkowych wykon się p sekwencyj dodaw poszczeg (liczb) argumentów. Taki proces sumow kolej argument określa się jako sumow akumulacyjne
Ukł cyfr,odejm arytm liczby dwójk naz się subtraktorem. Operac odejm liczb dwójk zastęp się oper dodaw uzupełn odjemnika, aby wykorzyst do tego celu sumatory.1. przedstaw się odjemnik w 1 z kodów uzupełnień(zazwyczU2) 2.wykon się sumow z odjemną.W celu uzysk poprawnego wyniku, należy jedynkę z poz przenieśprzenieść na poz najniższą (tzw. przenieś zwrotne lub cykliczne)i dodać.Wykorzystjc uzupełń do podstwy dan systemu liczb elimin.e się przenieśzwrotne i dlat oper odejmow staje się prostsza.
Met mnoż liczb 2jk jest pdbn do mnoż liczb dzieśtnh i polga na określ, a nast dodaniu ilocz częściow.Przy mnoż liczb 2jkwh iloczny część są równ mnożnej P, jeśl odpowdnm czynnkm z mnożnika jest bit 1, lub=zeru, if tym czynnkm jest bit 0.Oper mnoż polega na realiz ciągu przesu mnożnej w lewo i akumulcj dodawań. W ogól przyp przy mnoż a-bitowej liczby P przez b-biłową liczbę Q otrzym się ilocz F o liczbie bitów równej a + b.Oznacz że jeśl oby2 mnoż lczby mają tę sam długść słowa,to wynik wymag podwój długość słowa .
Dziel liczb 2jkwh wykon się metodą porównawczą, pdbnie do dziel dziesiętnego, wykon ciąg kolejn mnoż i odejmow.Poniew odjemnikiem jest zawsz dzielnik, przy oper odejmow wpis się go w kodzie uzupełnieniowym, najczęśćj U2. W proc dziel wyst sekwncyjnie oper porównania z dzielnikiem reszt częściowych o liczb bitów równej liczb bitów dzielnika (w tym przypdku 3). Jeśli dzielnik jest większy wpisujemy do wyniku 0, przeswmy się z dźelnkiem o1poz w prawo i wykorzstjmy kol bit dzielnej. Jeśli jest <=, to wpis do wyniku 1, pod resztę częściową wpisjmy dzielnik w kodzie U2 (011) i dokonuj sumow, po czym wykorzystjmy koljn bit dzielnej, dokonjm porówn itd.
W rezultaće mnoż 2 n-bitow liczb bez znaku otrzym się liczbę 2n-bitową.Przy pewnh działanah wynik może mieć dowolnie dużo bitów, zależnie od wymag dokładności.Jeśli jedn wynik ma być przedstwny w postaci liczby o mniejsz liczbie bitów to najprostszą oper jest obcięcie „zbytecznych" mniej znaczcyh bitów.Przy wielokrot powtarzan obcięcia liczb podczas liczenia należy się jednak liczyć ze wzrostem błędu ostatecznego wyniku. Kożystńjsze jest zaokrąg polegaj na określeniu m-bitowej liczb tak,aby możlwie zapobiec narastaniu lub akumulow się błędów zaokrąg podcz liczenia. Najbardziej znana metoda zaokrąglania polega na dodaniu 1 na najwyższej pozycji w odciętej części zaokrąglonej liczby i dodanie wynikłego stąd przeniesienia (0 lub 1) do skróconej liczby. 2.Niedomiar i Nadmiar Niedomiar przy działaniach na liczbach zmiennopozycyjnych występuje wtedy, gdy w trakcie obliczeń pojawi się liczba o wykładniku mniejszym od Lmin(W). Może on być interpretowany jako zero, albo zainicjować wykonanie denormalizacji mantysy. W ostatnim przypadku kosztem zmniejszenia dokładności otrzymuje się jednak wynik niezerowy. Nadmiar ma miejsce wtedy, gdy w trakcie obliczeń pojawi się liczba o wykładniku większym od Lmax(W) = 2w-1 - 1. Może to spowodować błąd w obliczeniach i dlatego w praktyce pojawienie się nadmiaru wymaga sygnalizacji lub uruchomienia procedur korekcyjnych. 3. Języki formalne Językiem nazywa się niepusty, skończony zbiór różnych słów nad danym alfabetem. Znaczenia tych słów tworzą semantykę języka, a reguły ich używania stanowią składnię języka. Na słowach określa się operację złożenia (dostawienia, zetknięcia, konkatenacji). Złożeniem słów Ai i Aj jest słowo Ak powstałe przez zetknięcie ze sobą łańcuchów znaków stanowiących te słowa w taki sposób, że słowo Ai, jest wpisane z lewej strony, a słowo Aj z prawej, przy czym n(Ak) = ni(Ai) + nj(Aj). Operację złożenia zapisuje się przy użyciu znaku kółeczka ,, °", kwadracika „□", znaku „&", znaku dodawania „ + ", stosowane są także nawiasy ostre. Na przykład, dla słów Ai = zkd i Aj = abcde Ak = Ai° A j = Ai□ A j = Ai& A j = <Ai Aj> = zkdabcde . Szczególnym słowem jest jedyne słowo o długości 0. Jest to słowo puste, czyli funkcja pusta. Oznaczamy je przez ε, ε = A0. Elementy : Alfabet. Alfabet definiuje się jako skończony, niepusty zbiór różnych znaków (A = {a, b,...,z}, D = {0, I,...,9}, który zazwyczaj jest uporządkowany.Słowo (ciąg) informacyjne - to skończony łańcuch znaków Alfabetu: Ai = zkd, Aj = abcde). Długość słowa – to liczba n znaków tworzących słowo (ciąg) Ai = 3, Aj = 5. 4. Hierarchia Chomsky'ego. Hierarchia Chomsky'ego składa się z czterech poziomów: 0. Języki typu zero, czyli rekurencyjnie przeliczalne. 1.Języki typu jeden, czyli kontekstowe (monotoniczne). 2.Języki typu dwa, czyli bezkontekstowe. 3.Języki typu trzy, czyli regularne. *Język rekurencyjnie przeliczalny(0) to język, dla którego istnieje gramatyka typu 0, której produkcje są postaci alfa -> beta , gdzie α i β są dowolnymi słowami. Gramatyki typu 0 są równoważne maszynom Turinga. *Język kontekstowy(1) to język, który można wygenerować za pomocą gramatyki kontekstowej, której produkcje są postaci αA β -> α γ β, gdzie α i β są dowolnymi słowami, A nieterminalem, γ - niepustym słowem. Gramatyki kontekstowe są równoważne automatom liniowo ograniczonym.B-> b ABcd-> abCDBcd *Język bezkontekstowy(2) to język, który można wygenerować za pomocą gramatyki bezkontekstowej, która po lewej stronie reguł ma pojedyncze nieterminale, po prawej zaś dowolne słowa. Np. A -> aBc, A->BC. Gramatyki bezkontekstowe są równoważne niedeterministycznym automatom ze stosem. * Język regularny(3) to język, który można wygenerować za pomocą gramatyki liniowej – takiej, która po lewej stronie reguł ma pojedyncze nieterminale, po prawej zaś słowa zawierające co najwyżej jeden nieterminal (na początku lub na końcu każdego słowa - jest to wtedy odpowiednio gramatyka lewostronnie lub prawostronnie liniowa) Gramatyki liniowe są równoważne automatom skończonym. A -> a, A->abc, A-> B, A->aB, A-abcB 5.Maszyna Turinga Maszyny z nieograniczoną pamięcią Q = ∞ – to maszyny liczące – komputery. Matematyczny model – to maszyna Turinga . Alan Turing wymyślil maszynę w 1936 r. Celem Turinga było zbudowanie modelu, za pomocą którego można by zbadać ograniczenia „procesów obliczeniowych". Było to po opublikowaniu w 1931r. W tym samym roku, jako narzędzie do analizy siły wyrazu procesów algorytmicznych, Emil Post zaprezentował inny model (zwany obecnie systemem produkcji Posta), który, jak udowodniono, ma takie same możliwości jak |
maszyny Turinga. Modele opracowane przez tych naukowców wciąż służą jako cenne narzędzia do badań w dziedzinie informatyki. Każdy problem, który daje się rozwiązać na maszynie Turinga lub Posta, ma także rozwiązanie na nowoczesnym komputerze. Jeśli tylko język programowania obejmuje cechy języka maszyny Turinga , to jest pewność, że dostarczy sposobów wyrażenia rozwiązania każdego problemu, który da się rozwiązać za pomocą komputera. Stosując język maszyny Turinga , odkryjemy, że są problemy, których współczesne komputery nie są w stanie rozwiązać i których żadna algorytmiczna maszyna przyszłości nie będzie w stanie rozwiązać. Wśród problemów, które można rozwiązać na komputerze, są problemy, których rozwiązanie jest tak złożone, że są one w istocie nierozwiązywalne pod względem praktycznym. 6. Klasyfikacja problemów. Nierostrzygalne -> problem stopu. Rozstrzygalne -> Klasa P O(n), O(n^2), O(n^3) > 1. Minimalne drzewo w grafie 2. Minimalna droga w sieci 7. Funkcje nierozstrzygalne i rozstrzygalne. Są funkcje, w których związku między wartością wejściową a wynikiem nie daje się wyznaczyć algorytmicznie. Mówi się, że takie funkcje są Nieobliczalne (Nierozstrzygalne ). Funkcje, których wyniki można określić algorytmicznie na podstawie wartości wejściowych, są Obliczalne (Rozstrzygalne) . Nie ma algorytmicznej metody znalezienia wartości wyjściowych funkcji nieobliczalnych. Funkcje te są poza zasięgiem możliwości współczesnych oraz przyszłych komputerów. Aby coś policzyć na komputerze, trzeba najpierw znaleźć algorytm wykonujący niezbędne obliczenia. Poznanie granicy między funkcjami obliczalnymi i nieobliczalnymi jest równoważne poznaniu granic możliwości komputerów. Teza Churcha - Turinga stanowi ważny krok w kierunku określenia tych granic. Znaczenie tego stwierdzenia polega na tym, że daje ono pogląd na możliwości i ograniczenia sprzętu komputerowego. Mówiąc precyzyjnie, zbiór funkcji obliczalnych w sensie Turinga stanowi zbiór, z którym porównuje się moc obliczeniową różnych systemów. Jeśli system obliczeniowy jest w stanie obliczyć wszystkie funkcje obliczalne w sensie Turinga, to jest uważany za system uniwersalny. 8. Złożoność problemów Każde obliczenie na maszynie Turinga składa się z co najmniej tylu kroków ile wynosi długość słowa wejściowego. Konwencja: Symbol n oznacza długość słowa wejściowego. Mówimy, że (deterministyczna lub nie) maszyna Turinga ma złożoność czasową T(n) jeśli dla dowolnego n, każde obliczenie tej maszyny dla dowolnego słowa wejściowego w o długości n składa się z co najwyżej T(n) kroków. Musi zachodzić warunek T(n) > n. Maszyna ma złożoność pamięciową S(n) jeśli każde jej obliczenie się zatrzymuje, i na dodatek, dla dowolnego n w każdym obliczeniu dla dowolnego słowa wejściowego w o długości n, maszyna używa co najwyżej S(n) klatek na każdej taśmie roboczej. Mówiąc o złożoności czasowej T(n) i pamięciowej S(n), mamy w istocie na myśli max{T(n),n} i max{Sr(n), n}. 1. f(n) = Ozczymśwśrodku (g(n)) - Mówimy, że problem ma złożoność czasową Ozczymśwśrodku(g(n)), gdzie f(n) jest pewnym wyrażeniem matematycznym zależnym od n, n > n0 , jeśli istnieje algorytm o złożoności czasowej nie mniejszej niż c1g(n) i nie większej niż c2g(n) rozwiązujący ten problem. c1 i c2 - to dowolne stałe. 2. f(n) = O(g(n)) - Mówimy, że problem ma złożoność czasową O(g(n)), jeśli istnieje algorytm o złożoności czasowej nie większej niż cg(n) rozwiązujący ten problem, gdze c - dowolna stała, n > n0 . 3. f(n) = podkowa(g(n)) - Mówimy, że problem ma złożoność (czasową) podkowa(f(n)), jeśli nie ma algorytmu rozwiązującego go o mniejszej złoźoności niż cg(n) gdzie c - stala., n > n0 9. Klasy P i NP. Klasa P - Problem jest problemem wielomianowym, jeśli należy do klasy O(f (n)), gdzie f (n) jest albo wielomianem, albo jest ograniczone przez wielomian (n, n2, n3, ...). Taki problem może być rozwiązany na deterministycznej maszynie Turinga za wielomianowy czas. Klasa NP - Problem nie jest problemem wielomianowym, jeśli należy do klasy O(f (n)), gdzie f (n) nie opisuje się wielomianem, a jest eksponentą (2n, an, n!, ... ). Taki problem może być rozwiązany na niedeterministycznej maszynie Turinga za wielomianowy czas. 10. Podstawowe układy kombinacyjne: bramki Istnieją dwa rodzaje graficznych symboli elementów logicznych: 1. symbole o kształcie prostokątnym i 2. symbole o kształtach zróżnicowanych. AND/OR/XOR/NOT/DAND(Z1)/ DOR(ZUB)/Bufor wzmacniający/ Element opózniający/Wskaźnik negacji/Wskaźnik polaryzacji (Slajd 8.3 rysunki <- w ściągę nie wejdą) 11. Sposoby opisu układów sekwencyjnych Automat skończony, czyli model matematyczny układu sekwencyjnego, jest określony przez piątkę AS = (X, Y, Q, δ, λ), gdzie X - alfabet wejściowy: X = {x1,..., xn}, x ∈B, Y - alfabet wyjściowy: Y = (y1, y2,..., ym), y∈B, Q - alfabet stanów: Q={q0, q1, q2,…, qk -1}, q∈B, δ – funkcja przejść : X → Q,, λ – funkcja wyjść : X → Y. Jeżeli automat ma odrębny początkowy stan q0 , to taki automat nazywa się inicjalny i poznaczy się jak (A, qo ). Jeżeli automat nie jest inicjalny, to każdy jego stan Q = (q0, q1, ... qk-1) może być początkowy. Nieinicjaly automat można rozpatrywać jak k inicjalnych automatów. W układach sekwencyjnych związki między stanami X, Y i Q określa się w postaci dwóch funkcji opisujących 1. automat Mealy'ego lub 2. automat Moore'a 12. Klasyfikację układów cyfrowych Układy logiczne rozdzielają się na Kombinacyjne i Sekwencyjne. Kombinacyjne już nie idą dalej. Sekwencyjne dzielą się na Synchronicze i Asynchroniczne.Synchroniczne nie idą dalej. Asynchroniczne dzielą się na Wyzwalane poziomem i Wyzwalane zboczem. 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ść; stan wyjść opisują funkcje boolowskie - w przeciwieństwie do układów sekwencyjnych, których stan wyjść zależy od stanu wejść oraz od poprzedniego stanu wyjść. W układach kombinacyjnych nie występuje sprzężenie zwrotne. 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, zwanego stanem wewnętrznym, pamiętanego w zespole rejestrów (pamięci). W układach asynchronicznych zmiana sygnałów wejściowych X natychmiast powoduje zmianę |
wyjść Y. W związku z tym układy te są szybkie, ale jednocześnie podatne na zjawisko hazardu i wyścigu W układach synchronicznych zmiana stanu wewnętrznego następuje wyłącznie w określonych chwilach, które wyznacza sygnał zegarowy (ang. clock). Każdy układ synchroniczny posiada wejście zegarowe oznaczane zwyczajowo symbolami C, CLK lub CLOCK. Charakterystyczne dla układów synchronicznych, jest to, iż nawet gdy stan wejść się nie zmienia, to stan wewnętrzny - w kolejnych taktach zegara - może ulec zmianie. 13. Funkcjonalne bloki kombinacyjne Funkcjonalne bloki kombinacyjne dzielą sie na Komutatory, Konwertery kodów i bloki artymetyczne. Komutatory dzielą się na multipleksy i demultipleksy Konwentery dziela się na kodery, dekodery, transkodery Bloki arytm. dziela sie na sumatory, komparatory, jednostki arytmetyczno-logiczne i uklady kontroli parzystości ================ Multiplekser -wybiera jeden z sygnałów z wejść informacyjnych X0-Xn, wskazany przez wejście adresowe A0-Aa i przekazuje go na wyjście Y układu Demultiplekser - posiada jedno wejście informacyjne X, Ladr wejść adresowych oraz Linf =2Ladr wyjść informacyjnych. Wejścia adresowe służą do określania, na które z wyjść informacyjnych przekazany zostanie sygnał z wejścia. Koder należy do klasy układów kombinacyjnych. Jest to układ posiadający k wejść oraz n wyjść (k=2n). Dekoder należy do klasy układów kombinacyjnych. Jest to układ posiadający n wejść oraz k wyjść (k=2n). Transkoder to układ cyfrowy o n wejściach oraz k wyjściach. Jego działanie polega na zamianie dowolnego kodu cyfrowego (poza kodem 1 z N) na inny, dowolny kod cyfrowy (również z wyjątkiem kodu 1 z N) Sumator – cyfrowy układ kombinacyjny, który wykonuje operacje dodawania dwóch (lub więcej) liczb dwójkowych.Są dwa główne rodzaje sumatorów: z przeniesieniami szeregowymi i z przeniesieniami równoległymi Komparator jest układem kombinacyjnym służącym do porównywania dwóch liczb dwójkowych (kod binarny)(wykonanie cyfrowe) albo dwóch napięć (wykonanie analogowe). Jednostka arytmetyczno-logiczn to jedna z głównych części procesora, prowadząca proste operacje na liczbach całkowitych.ALU jest układem cyfrowym, służącym do wykonywania operacji arytmetycznychoraz operacji logicznych pomiędzy dwiema liczbami. 14. Bazowa architektura komputera Bazowa architektura komputera (przerobiony slajd na tekst, więc będzie dziwnie)Od lewej, blok sterownia idzie strzałką do mikroprocesora. Mikroprocesor idzie w góre strzałką obustronną do pamięci stałej, w doł do pamięci o dostępie swobodnym. W prawo idzie strzałką obustronną do interfejsu sterujacego, który taką samą strzałką idzie w doł do urządzeń wejścia-wyjscia. Mikroprocesor to układ scalony o bardzo dużym stopniu upakowania, zawierający nawet do kilku setek milionów tranzystorów. Jest on podstawowym urządzeniem przetwarzającym i sterującym komputera. Wykonuje większość arytmetycznych i logicznych operacji przetwarzania danych. Architektura mikroprocesora powinna spełniać trzy podstawowe warunki. Pamięć stała jest elementem przeznaczonym do przechowywania niezmiennych komponentów oprogramowania systemu informatycznego pomiędzy seansami pracy komputera. W pamięci stałej umieszczane są tylko te spośród nich, do których dostęp jest niezbędny dla funkcjonowania systemu. Pamięć o dostępie swobodnym przeznaczona jest do przechowywania danych i programów sterujących, wykonywanych w chwili obecnej przez komputer. Pozwala na praktycznie nieograniczoną liczbę zapisów i odczytów informacji. Interfejsy sterujące to specjalizowane procesory przeznaczone do zarządzania urządzeniami wejścia-wyjścia. Urządzenia wejścia-wyjścia to w większości konstrukcje elektromechaniczne, wyposażone w sterowanie mikroprocesorowe, których zadaniem jest przedstawianie użytkownikowi informacji przetworzonej w komputerze oraz przyjmowanie informacji od użytkownika i wprowadzanie jej do komputera. Blok sterowania ma za zadanie wytwarzanie impulsów synchronizujących pracę całego komputera. Dzięki niemu rozpoczynanie i zakańczanie przetwarzania w poszczególnych blokach komputera będzie zsynchronizowane 1.Arytmetyka dwojkowa, dzialania arytmetyczne na liczbach 2. Niedomiar i Nadmiar. 3. Języki formalne 4. Hierarchia Chomsky'ego 5. Maszyna Turinga 6. Klasyfikacja problemów 7. Funkcje nierozstrzygalne i rozstrzygalne 8. Złożoność problemów 9. Klasy P i NP 10. Podstawowe układy kombinacyjne: bramki 11. Sposoby opisu układów sekwencyjnych 12. Klasyfikację układów cyfrowych 13. Funkcjonalne bloki kombinacyjne 14. Bazowa architektura komputera 15. Klasyfikacja architektur równoległych 16. Neurokomputery |
|---|