alg.pdf

Syllabus

Wprowadzenie

Poprawno Ļę algorytmów (analiza algorytmów)

Sortowanie

Elementarne struktury danych

Wyszukiwanie

Zaawansowane struktury danych

Programowanie dynamiczne

Literatura

T. Cormen, Ch. Lieserson, R. Rivest, Wprowadzenie do Algorytmów, WNT, 1997

R. Sedgewick, Algorytmy w C++, RM, 1999

N. Wirth, Algorytmy + struktury danych = programy, WNT, 2001

O co w tym wszystkim chodzi?

Rozwi Ģ zywanie problemów:

– Układanie planu zaj

– Balansowanie własnego budet

– Symulacja lotu samolotem

– Prognoza pogody

Dla rozwizania problemów potrzebujemy procedur, recept, przepisów –

inaczej mówic algorytmów

Historia

Nazwa pochodzi od perskiego matematyka Muhammeda ibn Musa

Alchwarizmiego (w łaci ı skiej wersji Algorismus ) – IX w n.e.

Pierwszy dobrze opisany algorytm – algorytm Euklidesa znajdowania

najwi ħ kszego wspólnego podzielnika, 400-300 p.n.e.

XIX w. – Charles Babbage, Ada Lovelace.

XX w. – Alan Turing, Alonzo Church, John von Neumann

Struktury danych i algorytmy

Algorytm – metoda, zestaw działa ı (instrukcji) potrzebnych do

rozwi Ģ zania problemu

Program – implementacja algorytmu w jakim Ļ j ħ zyku programowania

Struktura danych – organizacja danych niezb ħ dna dla rozwi Ģ zania

problemu (metody dost ħ pu etc.)