Structuri de Date si Algoritmi - Structuri de Date si Algoritmi

Extras din document

Scurt istoric. Noţiuni de baza: Algoritm, Structuri de date, etc. Pentru prima data in sec 9 dHr Abu Abdullah a scris o lucrare despre efectuarea calculelor numerice algebrice. Prin algoritm se intelege – reguli de baza carora se fac calcule matematice. Kroneker si Dedekind introduc funtii recursive la care se va referi algoritmul. In sec 20 se propune teoria algoritmilor, recursivitatea care se introduc axiomatic. Algoritm – succesiune de pasi si proprietatile / regulile sistemului cibernetic – i/o data. Cerintele algoritmului: claritate (descriere precisa, toate etapele de calcul sa fie prevazute), generalitate (sa rezolve o anumita clasa de probleme), finitudine (furnizeaza rezultate intr-un nr finit de pasi), unicitate (etapele algoritmului trebuie prezentate in mod unic), discretitate (executarea secventiala a pasilor simpli, fiecarui pas fiindu-i dat timp). Operatori de baza – i/o, atribuire, decizie. Reprezentarea algoritmului – schema logica, pseudo cod, limbaj de programare. Structuri elementare – liniara (etape de calcul ce succed una dupa alta),alternativa (ramificarea executiei in functie de valoarea de adevar a conditiei evaluate), repetitiva (executie repetata de nr finit de ori a unei secvente de instructiuni ciclu). Tipuri de structuri de date: baza (simboluri, cifre a caror divizare nu are sens, sunt determinate de arhitectura calculatorului), complexe (construite de utilizator pentru sarcini specifice). Structura de date – unitate de soft care poate stoca si procesa multimi de acelasi tip sau date unite-n calcul logic precum adaugare, cautare, stergere,editare; ofera funcții integrate care formeaza interfata ei; este posibilitatea realizarii unui tip abstract de date). Teoria algoritmilor si Mașina Turing. Algoritm – succesiune de pasi si proprietatile / regulile sistemului cibernetic – i/o data. Cerintele algoritmului: claritate(descriere precisa, toate etapele de calcul sa fie prevazute), generalitate (sa rezolve o anumita clasa de probleme),finitudine (furnizeaza rezultate intr-un nr finit de pasi), unicitate (etapele algoritmului trebuie prezentate in mod unic),discretitate (executarea secventiala a pasilor simpli, fiecarui pas fiindu-i dat timp). Operatori de baza – i/o, atribuire, decizie.Reprezentarea algoritmului – schema logica, pseudo cod, limbaj de programare. Schema logica – prezentare grafica care permite vizualizarea inlantuirii si subordnarii secventelor de operatii. Masina Turing – mecanisme extrem de elementare de dispozitive de prelucrare a simbolurilor care pot fi adaptate pentru a simula logica oricarui calculator. Orice problema algoritmica poate fi rezolvata de Turing. Concept: persoana virtuala executa procedura...