Przeglad podstawowych algorytmow_All.pdf

Kuźnia Talentów

Informatycznych:

Algorytmika

i programowanie

Przegląd podstawowych

algorytmów

Marcin Andrychowicz,

Tomasz Kulczyński, Błażej Osiński

Przegląd podstawowych

algorytmów

Rodzaj zajęć: Kuźnia Talentów Informatycznych

Tytuł: Przegląd podstawowych algorytmów

Autor: Marcin Andrychowicz, Tomasz Kulczyński, Błażej Osiński

Redaktor merytoryczny: prof. dr hab. Maciej M Sysło

Zeszyt dydaktyczny opracowany w ramach projektu edukacyjnego

Informatyka+ — ponadregionalny program rozwijania kompetencji

uczniów szkół ponadgimnazjalnych w zakresie technologii

informacyjno-komunikacyjnych (ICT).

www.informatykaplus.edu.pl

kontakt@informatykaplus.edu.pl

Wydawca: Warszawska Wyższa Szkoła Informatyki

ul. Lewartowskiego 17, 00-169 Warszawa

www.wwsi.edu.pl

rektorat@wwsi.edu.pl

Projekt graficzny okładki: FRYCZ I WICHA

Warszawa 2010

Publikacja nie jest przeznaczona do sprzedaży.

Przegląd podstawowych

algorytmów

Marcin Andrychowicz,

Tomasz Kulczyński, Błażej Osiński

< 4 >

Informatyka +

Streszczenie

Celem tego kursu jest przekazanie podstawowej wiedzy o popularnych problemach i ich rozwiąza-

niach(algorytmach)lubmetodachtworzeniarozwiązań.Omówionezagadnieniasąbardzoróżnorodne.

Obejmują techniki budowania algorytmów takie, jak: programowanie dynamiczne, rekurencja, strate-

giezachłanne.Zawartesątakżepodstawowe zagadnieniazkilkuważnychdziedzinalgorytmiki:teorii

grafów,przetwarzaniatekstówigeometriiobliczeniowej.Każdyztychtematówzostajewprowadzony

wrazznajbardziejznanymiproblemamiialgorytmami.

ZakładanajestznajomośćjęzykaC++,aleprogramującywPascaluczyjeszczeinnymjęzykutakże

powinniporadzićsobiezezrozumieniemzawartychwkursietreści.

W tekście użyte zostają wielokrotnie pojęcia matematyczne, które mogą okazać się nowe nawet

dlauczniakończącegoszkołęponadgimnazjalną.Ichnieznajomośćniestanowiproblemuwkorzystaniu

zkursu,gdyżsąjednakomawianewniezbędnymzakresie.

Spistreści

Streszczenie 4

1 Programowaniedynamiczne 5

1.1 Idea..................................................................... 5

1.2 Znaneproblemy............................................................ 6

2 Sortowanie 8

2.1 Sortowanieprzezwybór ..................................................... 8

2.2 Sortowanieprzezscalanie.................................................... 10

3 Wyszukiwaniebinarne 12

4 Sortowaniepozycyjne 13

4.1 Sortowanieprzezzliczanie ................................................... 13

4.2 Sortowanieleksykograﬁczne.................................................. 14

5 Algorytmyzachłanne 15

6 Rekurencja 17

6.1 AlgorytmEuklidesa......................................................... 17

6.2 WieżeHanoi .............................................................. 17

7 Przeszukiwanieznawrotami(backtracking) 18

7.1 Problem8hetmanów ....................................................... 18

8 Grafy—Wprowadzenie 19

8.1 Cotojestgraf?............................................................ 19

8.2 Reprezentacjagrafunakomputerze ........................................... 20

8.3 Przeszukiwaniegrafów ...................................................... 22

9 Algorytmygrafowe 24

9.1 ProblemcykluiścieżkiEulera................................................ 24

9.2 AlgorytmDijkstry.......................................................... 25

9.3 AlgorytmBellmana-Forda ................................................... 27

10 Algorytmytekstowe 27

10.1 Algorytmnaiwnywyszukiwaniawzorca......................................... 28

10.2 AlgorytmKnutha-Morrisa-Pratta ............................................. 28

11 Algorytmygeometryczne 29

11.1 Podstawy................................................................. 29

11.2 Polepowierzchni........................................................... 31

11.3 Problemznajdowaniawypukłejotoczki ........................................ 31

Literatura

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: