Wstep do informatyki -UW.pdf

Wyk“adzeWstƒpu

doInformatyki

Rok2004-2005

MarekZawadowski

Wydzia“Matematyki,InformatykiiMechaniki

UniwersytetWarszawski

3stycznia2005

Spistre–ci

1Wstƒp(1/2) 4

1.1Literatura............................. 4

1.2Zaliczenieiegzamin....................... 4

1.3HistoriaInformatyki....................... 4

2Wprowadzenie(21/2) 5

2.1AlgorytmEuklidesa....................... 5

2.2Problemalgorytmiczny...................... 6

2.3Sortowanieliczb.......................... 6

2.4Analizaz“o»ono–cialgorytmu.................. 7

2.5Wie»eHanoi............................ 8

2.6Wyszukiwanies“owaws“owniku.................10

2.7Tablicerzeczywistegoczasudzia“aniaalgorytm ó w.......10

2.8Komputerod–rodka.......................12

3JƒzykPascal(4) 14

3.1Jƒzykiprogramowaniawysokiegopoziomu...........14

3.2Diagramysk“adniowe.......................14

3.3Formalnade nicjajƒzykaimperatywnego...........16

3.4Zmienne..............................17

3.5Typyproste............................18

3.6Typystrukturalne........................20

3.7Przegl¡dinstrukcjijƒzykaPascal ................21

3.8Procedury.............................29

3.9Proceduryrekurencyjne.....................34

3.10Poprawno–¢program ó w.....................40

4Podstawowemetodyprogramowania(5) 43

4.1Metodapowrot ó w(pr ó bib“ƒd ó w)...............43

4.2Metoda’dzielirz¡d„’ ......................48

4.3Sortowanieprzypomocypor ó wna«...............52

4.4Programowaniedynamiczne...................54

4.5Algorytmyzach“anne.......................59

4.6Algorytmsortowaniaprzezkopcowanie(heapsort).......63

4.7Podsumowanie..........................67

5Reprezentacjaliczbnakomputerze(2) 69

5.1Systemyliczboweor ó »nychpodstawach............69

5.2Reprezentacjasta“opozycyjnaliczbca“kowitych........71

5.3Operacjearytmetycznesta“opozycyjne.............73

5.4Reprezentacjazmiennopozycyjnaliczbrzeczywistych.....74

5.5Arytmetykazmiennopozycyjna.................76

5.6Wybraneproblemynumeryczne.................79

6Dynamicznestrukturydanych(4) 82

6.1Podstawowedynamicznestrukturydanych...........82

6.2Typywska„nikowe........................86

6.3Implementacjalist........................91

6.4Drzewabinarnychposzukiwa«(BST)..............95

6.5Strukturydanychdlarodzinyzbior ó wroz“¡cznych......101

7Algorytmygrafowe(5) 105

7.1Grafyireprezentacjegraf ó w...................105

7.2Sk“adowesp ó jnegrafuniezorientowanego...........108

7.3Przeszukiwaniegrafuwszerz(BFS)...............110

7.4Przeszukiwaniegrafuwg“¡b(DFS)...............117

7.5Sortowanietopologiczne.....................122

7.6Silniesp ó jnesk“adowegrafu...................123

7.7Minimalnedrzeworozpinaj¡ce..................129

8Z“o»ono–¢algorytm ó w(3) 133

8.1Problemydecyzyjne.......................133

8.2Algorytmywery kuj¡ce.....................134

8.3Redukowalno–¢problem ó wiproblemP=NP..........136

8.4Problemynieobliczalne......................138

8.5Metodyprzybli»one........................139

9Rozwi¡zywanieuk“ad ó wr ó wna«liniowych 146

9.1Mno»eniemacierzy........................146

9.2Rozwi¡zywanieuk“ad ó wr ó wna«liniowychniejednorodnych

metod¡rozk“aduLUP......................146

9.3Obliczanierozk“aduLUP....................150

9.4Macierzeodwrotne........................154

9.5Wyznacznikmacierzykwadratowej...............154

1Wstƒp(1/2)

1.1Literatura

1.Og ó lnewprowadzenie:D.Harel,Rzeczoistocieinformatyki

2.Algorytmy:

•T.H.Cormen,C.E.Leiserson,R.L.Rivest,IntroductiontoAlgo-

rithms(WprowadzeniedoAlgorytm ó w)

•L.Banachowski,K.Diks,W.Rytter,Algorytmyistruktury

danych

•A.V.Aho,J.E.Hopcroft,J.D.Ulman,Projektowanieianaliza

algorytmowkomputerowych

3.JƒzykPascal:

•M.Iglewski,J.Madey,S.Matwin,Pascal

•R.K.Kott,ProgramowaniewjƒzykuPascal

1.2Zaliczenieiegzamin

Zaliczenie:programikolokwium.Egzamin:pisemny,poobusemestrach.

1.3HistoriaInformatyki

IVw.p.n.e.Euklides:algorytmEuklidesa(pierwszyniebanalnyalgo-

rytm).

IXwn.e.Algorismus(MuhammadibnMusaal-Kwarizmi=Muhammad

synMusyzKworyzmu),algorytmydodawaniaodejmowania,mno»e-

nia,idzielenialiczbdziesiƒtnych.

XIXw.n.e.JosephJaquard,maszynatkackasterowanaalgorytmem.

CharlsBabbage,maszynar ó »nicowadoobliczaniawzor ó wmatem-

atycznychiprojektmaszynyanalitycznej,mechanicznegoprototypu

komputera.

1920-30r.AlanTuring,EmilPost,JohnvonNeuman,KurtG ö del,Alnzo

Church,StephenKleene:badaniapojƒciafunkcjiobliczalnej.

1945r.J.vonNeuman,pierwszykomputer(UPensylvenia)(?)

196-r.Informatykastajesienow¡dziedzin¡wiedzy.

2Wprowadzenie(21/2)

2.1AlgorytmEuklidesa

•Danewej–ciowe:dwieliczbynaturalnem,n>0.

•Wynik:NWD(m,n).

Opisalgorytmu.Odejmujliczbƒwiƒksz¡odmniejszeja»dowyr ó wnania

liczb.

Zapisalgorytmu.

a:=m;b:=n;

dop ó kia<>bwykonuj {NWD(a,b)=NWD(m,n),a,b>=1}

je–lia<btob:=b-a

wprzeciwnymprzypadkua:=a-b

wypisz(a)

Walgorytmieu»yli–mynastƒpuj¡cychoperacjielementarnych:

1.czteryinstrukcjeprzypisania;

2.iteracjanieograniczona(pƒtlawhile);

3.instrukcjawarunkowa;

4.instrukcjawej–ciawyj–cia.

Wnawiasach{}zapisali–myniezmiennikpƒtli,tzn.takiezdaniekt ó re

je–lijestprawdziweprzywej–ciudopƒtlitopozostajeprawdziwepoka»dym

pe“nymwykonaniupƒtli.

Czyprogramrobitocochcemy?Tak:

1.Poka»dymwykonaniupƒtliprawdziwyjestniezmiennikpƒtli

NWD(a,b)=NWD(m,n),a,b1.

2.Powyj–ciuzpƒtlia=b.Zatema=NWD(a,b).

3.Pƒtlawykonujesiƒconajwy»ejm+n−2razy(wszczeg ó lno–cinie

mo»edzia“a¢wniesko«czono–¢).

Ad1.Wystarczypokaza¢,»eje–lia>btoNWD(a,b)=NWD(a−b,b).

Wtymceluwystarczypokaza¢,»eliczbakdzieliaibwiwgdydzieli(a−b)

ib.

Ad2.Oczywiste.

Ad3.Ka»dewykonanieinstrukcjiwarunkowejzmniejszasumƒa+bo

conajmniej1.Zdrugiejstronymamya1,b1.Zateminstrukcja

warunkowamo»eby¢wykonanaconajwy»ejm+n−2razy.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: