Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
6
Rozdział0Wprowadzenie
Opis:Algorytmzakłada,żejegodanewejścioweskładająsięzdwóchdodatnich
liczbcałkowitychipoleganaobliczeniunajwiększegowspólnegodzielnikatych
dwóchwartości.
Procedura:
Krok1.PrzypiszMiNodpowiedniowartośćwiększejimniejszejzdwóch
wartościwejściowych.
Krok2.PodzielMprzezNinazwijresztęR.
Krok3.JeśliRniejestrówne0,przypiszMwartośćN,przypiszNwartośćR
iwróćdokroku2;wprzeciwnymrazienajwiększymwspólnym
dzielnikiemjestwartośćaktualnieprzypisanadoN.
Rysunek0.2AlgorytmEuklidesadoznajdowanianajwiększegowspólnegodzielnikadwóchdodat-
nichliczbcałkowitych
Określenieograniczeńmożliwościalgorytmicznychzostałowprowadzonejako
elementmatematykiwlatach30.XXwiekuwrazzpublikacjątwierdzeniaoniezu-
pełnościKurtaGödla.Twierdzenietozasadniczomówi,żewkażdejteoriimatema-
tycznejobejmującejnasztradycyjnysystemarytmetycznyistniejątwierdzenia,któ-
rychprawdziwościlubfałszuniemożnaustalićmetodamialgorytmicznymi.Krótko
mówiąc,jakiekolwiekpełnebadanienaszegosystemuarytmetycznegowykracza
pozamożliwościdziałańalgorytmicznych.Taświadomośćwstrząsnęłapodstawami
matematyki,abadaniemożliwościalgorytmicznych,którepotymnastąpiło,było
początkiemdziedzinyznanejdziśjakoinformatyka.Wrzeczywistościtowłaśnie
naukaoalgorytmachstanowirdzeńinformatyki.
0.2Historiainformatyki
Dzisiejszekomputerymająbogatągenealogię.Jednymzpoczątkowychnarzędzi
obliczeniowychbyłoliczydło.Historiamówinam,żeprawdopodobniemiałoono
swojekorzeniewstarożytnychChinachibyłoużywanewewczesnychcywiliza-
cjachgreckichirzymskich.Maszynajestdośćprosta,składasięzkoralikównaw-
leczonychnapręty,którezkoleisązamontowanewprostokątnejramie(rysunek
0.3).Gdykoralikisąprzesuwanewzdłużprętów,ichpozycjereprezentujązapisane
wartości.Towłaśniewpozycjachkoralikówtegotypunkomputer”reprezentuje
iprzechowujedane.Sterowaniewykonaniemalgorytmuwymagaudziałuczło-
wieka.Zatemsamoliczydłojestjedyniesystememprzechowywaniadanychimusi
byćpołączonezczłowiekiem,abystworzyćkompletnąmaszynęobliczeniową.
Wokresiepośredniowieczu,aprzedepokąnowożytnązaczętoposzukiwać
bardziejwyrafinowanychmaszynobliczeniowych.Kilkuwynalazcówzaczęłoeks-
perymentowaćztechnologiąkółzębatych.WśródnichbyliBlaisePascal(1623–
1662)zFrancji,GottfriedWilhelmLeibniz(1646–1716)zNiemieciCharlesBab-
bage(1792–1871)zAnglii.Maszynytereprezentowałydanepoprzezpozycjekół
