|
Nie obrażaj więc mojej inteligencji poprzez czynione na pokaz zaniżanie własnej.
UrszulaBoryczka
SKRYPT Uniwersytetl¡ski WydziałInformatykiiNaukioMateriałach Wprowadzeniedoinformatyki Spistre±ci Rozdział1.Arytmetykabinarna .................................. 5 1.1.Rozwini¦ciedwójkowe ...................................... 5 1.1.1.Regułazamiany...................................... 6 1.2.Dowodyzapisuliczbwtrzechkodach.............................. 7 1.3.Dowódzapisuliczbbinarnychwpostaciułamkowej...................... 9 1.4.Przesuni¦cialiczbbinarnych...................................11 1.5.Porównanieoperacjidodawaniaiodejmowaniawsystemiebinarnymwtrzechkodach zapisu................................................13 1.6.Mno»enieliczbbinarnych.....................................15 1.6.1.Metodabezpo±rednia...................................15 1.6.2.MetodaBootha......................................15 1.7.Dzielenieliczbbinarnych.....................................19 1.7.1.Metodaporównawcza..................................19 1.7.2.Metodanierestytucyjna.................................21 Rozdział2.Logikabinarna ......................................25 2.1.Podstawowezagadnienialogikibinarnej.............................25 2.2.DefinicjaalgebryBoole’aipostulatyHuntingtona.......................26 2.3.Funkcjeboolowskie........................................30 Rozdział3.Translacjawyra»e«arytmetycznych ........................35 3.1.Podstawoweinformacjeotranslacjiitranslatorach.......................35 3.2.Algorytmtranslacjiwyra»e«naONP..............................36 3.3.Algorytmprzej±ciazpostacipostfiksowejnaposta¢infiksow¡................38 3.4.Algorytmkonwersjizinstrukcj¡warunkow¡..........................39 3.5.AlgorytmtranslacjizapisuONPnaj¦zyksymboliczny....................41 Rozdział4.MaszynaTuringaiautomatysko«czone ......................43 4.1.MaszynaTuringa.........................................43 4.2.Wyra»eniaregularne.......................................48 4.3.Automatysko«czone.......................................49 4.3.1.Deterministycznyautomatsko«czony..........................50 4.3.2.Niedeterministycznyautomatsko«czony........................51 4.3.3.Automatsko«czonyz " -ruchami.............................52 4.4.Konstruktory...........................................52 4.4.1.Konstruktordiagramuprzej±¢dlasumyteoriomnogo±ciowej r = r 1 + r 2 ......53 4.4.2.Konstruktordlazło»enia r = r 1 r 2 ............................53 4.4.3.Konstruktordladomkni¦cia r = r 1 ...........................54 Rozdział5.Gramatykiij¦zykiformalne .............................57 5.1.Gramatyki–podstawoweinformacje..............................57 5.2.Gramatykibezkontekstowe....................................57 5.3.J¦zykwyra»e«algebraicznych..................................58 5.4.Drzewowywodudlagramatykibezkontekstowej........................59 5.5.KlasyfikacjaChomsky’ego....................................60 Spistabel .................................................63 Spisrysunków ..............................................65 Bibliografia ................................................67 Rozdział1 Arytmetykabinarna Wtymrozdzialeprzedstawionyzostaniesposóbkodowanialiczbbinarnych.Ponadtozaprezen- towanab¦dzieregułazamianyzjednegosystemuliczenianainny(np.zsystemudwójkowego naczwórkowy).Zostan¡zaprezentowanetak»etrzykodyzapisuliczbybinarnej.Podanezo- stan¡równie»algorytmypodstawowychoperacjiarytmetycznych(tj.dodawania,odejmowania, mno»eniaorazdzielenia),jakiemo»nawykona¢naliczbachbinarnychwrazzichdowodami. Algorytmytezostan¡poparteprzykładami. 1.1.Rozwini¦ciedwójkowe Najpopularniejszymsposobemkodowaniainformacjizawartychwliczbachjestkodowanieinfor- macjiwpozycyjnymsystemiedziesi¦tnym.Wsystemietym,abyprzedstawi¢liczb¦naturaln¡ u»ywasi¦symboli:dziesi¦ciucyfrod0do9.Je±linatomiastchcemyprzedstawi¢liczb¦całkowit¡ musimyrównie»u»y¢10cyfr(0...9);dodatkowowykorzystujemyznak„minus”i„plus”oraz znak„przecinka”,któryoddzielacz¦±¢całkowit¡odułamkowej. Wsystemiedwójkowymnatomiastznak„kropki”oddziela bitznakowy odcz¦±cicałkowitej liczby,natomiastznak„przecinka”podobniejakwsystemiedziesi¦tnymoddzielacz¦±¢cał- kowit¡odułamkowej.Wniektórychsytuacjach,stosujesi¦skróconyzapisliczbbinarnych– wtedybezpo±redniopobicieznakowymnast¦pujekropka,aponiejcyfrycz¦±ciułamkowej. Cz¦±¢całkowitawtakichprzypadkachjestrównazero;wzapisiejestonapomijana(formalnie rzeczbior¡c,pobicieznakowympowinnanast¡pi¢kropka,potemzero,nast¦pnieprzecinek,a nako«cudopierocyfrycz¦±ciułamkowej). Istniejewielesystemówkodowanialiczb,zjakimistykamysi¦nacodzie«,jednaktoko- dowaniewsystemiebinarnymjestnajbardziejrozpowszechnionew±ródsposobówkodowania (rzeczjasnawinformatyce),zewzgl¦dunaprzystosowanieurz¡dze«informatycznychdopra- cyzci¡gamikodowymiwelektronicznychsystemachlicz¡cych.Liczbywtakichsystemachs¡ przedstawianejakoci¡gizerijedynek.W±ródkodowaniabinarnegomo»emyrozró»ni¢dwa rodzajekodowania. Pierwszysposóbtodwójkowekodowaniecyfrrozwini¦ciapozycyjnego(jesttotzw.kodBCD, ang.BinaryCodedDecimal),wktórymposzczególnejcyfrzedziesi¦tnejprzyporz¡dkowujemy odpowiednici¡gzerijedynek. Drugimnatomiastsposobemjestdwójkowysystempozycyjny,czyliprzedstawienieliczb wsystemiepozycyjnymopodstawiedwa.Dwójkowysystempozycyjnytosystemdwóchznaków –dwóchcyfr0i1.Cyfrydwójkowenazywamyrównie»cyframibinarnymi(zang.BinaryDigit). L ( A )= n − X a i · 2 i -sumaarytmetyczna i = − m Wyró»niamydwasposobyzapisuliczb: 1.Ka»dacyframo»eprzybiera¢ró»newarto±ciwzale»no±ciodjejpoło»eniawliczbie( system pozycyjny ). 2. Systemniepozycyjny ,wktórymwarto±¢cyfrniezale»yodichpozycjiwliczbie(np.cyfry rzymskie). |
Menu
|