1. Noţiuni de baza: Algoritm, Structuri de date, et.

În informatică, o structură de date este o metodă sistematică de stocare a informațiilor și datelor într-un calculator, în așa fel încât ele să poată fi folosite în mod eficient. Deseori o alegere bine făcută a structurii de date va permite și implementarea unui algoritm eficient. Structura de date aleasă este derivată de multe ori dintr-un tip de dată abstract. O structură de date bine concepută permite efectuarea unei varietăți de operații de bază, utilizând puține resurse (ca de exemplu memoria necesară și timpul de execuție). Structurile de date se implementează utilizând tipuri de date, referințe și operații asupra acestora, toate facilitate de către un limbaj de programare.

Un algoritm (cuvântul are la origine numele matematicianului persan Al-Khwarizmi) înseamnă în matematică și informatică o metodă sau o procedură de calcul, alcătuită din pașii elementari necesari pentru rezolvarea unei probleme sau categorii de probleme. De obicei algoritmii se implementează în mod concret prin programarea adecvată a unui calculator, sau a mai multora. Din diverse motive există și algoritmi încă neimplementați, teoretici.

-------------------------------------------------------------------------------------

2. Masina Turing (referat,video).

Fondatorul Mașinii Turing-Alan Turing(1912-1954) .În construcţia teoretică a acestei maşini, a pornit de la o idee inspirată de maşina de scris; astfel, maşina de scris poate fi considerată ca având o memorie de lungime infinită (prin schimbarea continuă a foilor), se poate mişca înainte şi înapoi la o căsuţă de memorie, poate scrie în aceste căsuţe.

Maşina Turing este compusă din următoarele piese:

1. bandă infinită de hîrtie cu pătrăţele - în fiecare pătrăţel se poate scrie exact un caracter din alfabetul nostru;

2. un cap de citire-scriere - se poate mişca deasupra benzii, la stînga sau la dreapta;

3. unitate de control- conţine un număr finit de reguli care indică maşinii ce să facă la fiecare mişcare în funcţie de litera curentă de pe bandă şi starea în care maşina se află.

O mașină Turing funcționează cu un set finit de stări

S={s1,….sn; sn+1=stop} un alfabet finit de simboluri

A={a1……aA; aA+1= blank} și un set finit de instrucțiuni , la care se adaugă o bandă infinit de lungă de memorie.

1. Stările corespund la moduri de funcționare a mașinii, astfel încît mașina Turing este în exact una dintre aceste stări la orice moment de timp.

2. Simbolurile din A codează informația prelucrată de mașină: codează datele de intrare/ieșire și păstrează rezultatele operațiilor intermediare.

3. Instrucțiunile sunt asociate cu stări din S și spun mașinii ce acțiune să efectueze dacă întîlnește un

simbol dat, și în ce stare să fie după efectuarea acestei acțiuni.

4. Există o stare “stop” în urma căreia nu se efectuează nici o instrucțiune, această stare nefiind inclusăîn numărul total de stări.

---------------------------------------------------------------------------------

3 . Structuri de date. Clasificarea. C versus C++. 2. Clasificarea structurilor de date :

I. Structuri de date elementare :- tablouri ( vectori, matrici, şiruri de caractere )- înregistrare- mulţime- fişiereII. Structuri de date dinamice :- structura de tip listă ( listă simplu înlănţuită, dublu înlănţuită, circulară, stivă, coadă )- structura de tip arbore: arbori binari, arbori binari de cautare, arbori oarecare

Limbajul de programare C este un limbaj de programare  a calculatoarelor, conceput de Dennis Ritchie  la începutul anilor 1970.C++ este o extindere a limbajului C. Limbajului C++ este contituit ca un superset al limbajului C. Aceasta înseamnă că orice program scris în limbajul C este în acelaşi timp şi un program scris în limbajul C++. Trebuie însă să remarcăm că această afirmaţie este adevărată cu mici excepţii.Ex: compilatorul C++ face unele controale suplimentare faţă de compilatorul C. Aceste controale se referă înprimul rând la tipurile parametrilor funcţiilor, precum şi la tipurile valorilor returnate de ele.Cu C++ scriem "clase" de obiecte, pe cînd cu C vom scrie doar functii si proceduri. In felul acesta (se spune ca) C++ ar fi mai intuitiv si mai usor de implementat decat C.Ca şi limbajul C, limbajul C++ se bucură de o portabilitate mare şi este implementat pe o gamă largă decalculatoare începând cumicrocalculatoare şi până la cele maimari supercalculatoare. Întrediferitele implementări ale limbajuluiC++ există diferenţe legate despecificul calculatoarelor, dar acestediferenţe nu sunt esenţiale.Cele mai importante diferențe între C/C++ sunt:1.inline —funcțiile inline apar în secțiunea de declarare a variabilelor globale în C++, iar in C acestea apar în așa zisele „fișiere statice“.2. Cuvântul cheie bool are în C99 propriul său header, <stdbool.h>. În variantele anterioare de C tipul de date boolean nu era definit, în schimb erau folosite o serie de metode (incompatibile) pentru a simula acest tip de date.3.Constantele caracter (cuprinse între apostrofuri) au dimensiunea unui int în C și char în C++. Cu alte cuvinte, în C, sizeof('a') == sizeof(int); în C++, sizeof('a') == sizeof(char). Chiar și în aceste condiții, valoarea acestui tip de constante nu va depăși valoarea maximă ce poată fi păstrată de char, deci o conversie de genul (char)'a' este sigură.\----------------------------------------------------------------------------------------

4.Algoritmi combinatoriali. Introducere.In foarte multe aplicatii ale matematicii se cere determinarea numarului de elemente ale unor multimi, numarul submultimilor unei multimi satisfacand anumite proprietati sau numarul modalitatilor de

dispunere a elementelor multimii intr-o ordine specificata: Anumite probleme de numarare apar frecvent in aritmetica, geometrie, teoria numerelor, probabilitati, statistica. In cursul dezvoltrii matematicii s-a conturat o noua ramura a acesteia, care se ocupa cu aspectele ridicate de operatia de numarare:combinatorica. ---------------------------------------------------------------------------------

5.Permutari, Combinari, Aranjamente.

Permutarile unei multimi

Fie A={a1, a2, …, an} o multime finita cu n elemente.Multimea A se poate ordona in mai multe moduri.

Definitie.Se numeste permutare a multimii A oricare multime ordonata care se formeaza cu cele n elemente ale acesteia. Numarul permutarilor unei multimi cu n elemente se noteaza Pn. Convenim ca multimea vida se poate ordona intr-un singur mod si P0=1.

Aranjamente sicombinari. Fie A={a1, a2, …,an} o multime finita cu n elemente si m ε {0, 1, 2, …,n} Se stie ca multimea A are in total 2ⁿ submultimi.

Combinari

Definitie

Submultimile multimii A avand fiecare cate m elemente se numesc combinari de n elemente luate cate m. Numarul combinarilor de n elemente luate cate m se noteaza Cn.

AranjamenteDefinitie Submultimile ordonate cu m elemente ale multimii A se numesc aranjamente de n elemente luate cate m. Numarul aranjamentelor de n elemente luate cate m se noteaza An Se observa ca doua combinari de n elemente luate cate m se deosebesc prin natura elementelor. Doua aranjamente de n elemente luate cate m se deosebesc prin natura elementelor sau prin ordinea acestor elemente. Fiecare submultime cu m elemente poate fi ordonata in m! moduri. Rezulta, asadar, ca vom avea de m! ori mai multe aranjamente de n elemente luate cate m decat combinari de n elemente luate cate m.

Se obtin relatiile:An=m!Cn sau Cn=An/m! (1)

Relatiile (1) permit aflarea unui numar cunoscand celalalt numar dintre An si Cn.

Teorema Fie A o multime finita cu n elemente si 0 ≤ m ≤ n un numar natural. Atunci: An=n!/(n-m)! (2)

6.Formule   Herigonne, Pascal. Demonstratie.   Exemple si aplicatii practice.

Formula lui Pascal

Cºn+C¹n+…+Cnⁿ=2ⁿ

DemonstratieFie A={a1, a2, … ,an} o multime finita.Numarul tuturor submultimilor cu 0, 1, 2, …, n elemente ale lui A.Acestea sunt in numar de Cºn, C¹n,…,CⁿnPrin adunare rezulta relatia ceruta.

Formula Herigonne

      , sau 

          

Teorema Cn=n!/(n-m)!m!

Formula combinarilor a fost stabilita in 1634 de catre matematicianul francez Pierre Herigonne.

7. Recursia. Algoritm recursiv. Functii recursive. Exemple: n! ; Numerele lui Fibbonacci.

Recursivitatea, folosita cu multa eficienta in matematica, s-a impus in programare, odata cu aparitia unor limbaje de nivel inalt, ce permit scrierea de module ce se autoapeleaza (PASCAL,LISP,ADA,ALGOL,C sint limbaje recursive).

Orice program recursiv poate fi transformat in unul iterativ, dar algoritmul sau poate deveni mai complicat si mai greu de inteles. De multe ori, solutia unei probleme poate fi elaborata mult mai usor, mai clar si mai simplu de verificat, printr-un algoritm recursiv.

Exista:

1. Algoritmi de traversare si inversare a unei structuri

2. Algoritmi care implementeaza definitii recursive

Tipuri de algoritmi:

1. Algoritmi de divizare

procedure rezolva(x:problema); begin if {x e divizibil in subprobleme} then

begin {divide pe x in parti x1,...,xk} rezolva(x1); {...} rezolva(xk);{combina solutiile partiale intr-o}

{solutie pentru x}

end else {rezolva pe x direct} end;

2. Algoritmi cu revenire (backtracking)

3. Algoritmi "inlantuie si limiteaza" (Branch and Bound)

--------------------------------------------------------------------

8.Sortare prin simplă inserare (Straight insertion). Posibilitati de imbunatatire a metodei.

1. Cazul mediu : O(N^2)2. Cazul defavorabil : O(N^2)3. Memorie folosita : O(1)4. Stabil : DA5. Sortare descrescatoare : j > 0 && a[j - 1] <

a[j]6. Sortare crescatoare : j > 0 && a[j - 1] > a[j]

Analiza :

Spre deosebire de alti algoritmi de sortare, sortarea prin insertie este folosita destul de despentru sortarea tablourilor cu numar mic de elemente. De exemplu, poate fi folosit pentru a imbunatati rutina de sortare rapida.

Sortarea prin insertie seamana oarecum cu sortarea prin selectie. Tabloul este impartit imaginar in doua parti - o parte sortata si o parte nesortata. La inceput, partea sortata contine primul element al tabloului si partea nesortata contine restul tabloului. La fiecare pas, algoritmul ia primul element din partea nesortata si il insereaza in locul potrivit al partii sortate.

Cand partea nesortata nu mai are nici un element, algoritmul se opreste.

-------------------------------------------------------------------------------------

9.Sortare prin simplă selectare (Straight selection). Posibilitati de imbunatatire a metodei.

1. Cazul mediu : O(N^2)2. Cazul defavorabil : O(N^2)3. Memorie folosita : O(1)4. Stabil : DA5. Sortare descrescatoare : min < a[j]6. Sortare crescatoare : min > a[j]

Analiza :

Acest algoritm selecteaza la fiecare pas`ul i cel mai mic element din vectorul de la pasul i+1 pana la n.Valoarea minima de la pasul i este pusa in vector la pozitia i,facandu-se intereschimbarea cu pozitia actuala a minimului.Nu este un algoritm indicat pentru vectorii mari, in majoritatea cazurilor oferind rezultate mai slabe decat insertion sort si bubble sort .

-------------------------------------------------------------------------------------

10 .Sortare prin simplu schimb (Buble sort). Posibilitati de imbunatatire a metodei.

1. Cazul mediu : O(N^2)2. Cazul defavorabil : O(N^2)3. Memorie folosita : O(1)4. Stabil : DA

5. Sortare descrescatoare : a[i] < a[i+1]6. Sortare crescatoare : a [i] > a[i+1]

Analiza :Sortarea prin metoda bulelor se considera drept una din cele mai putin efective metode desortare dar cu un algoritm mai putin complicat.Ideea de baza a sortarii prin metoda bulelor este in a parcurge tabloul de la stanga spre dreapta,fiind comparate elementele alaturate a[ i ] si a[i+1]. Daca vor fi gasite 2 elemente neordonatevalorile lor vor fi interschimbate

------------------------------------------------------------------

11. Sortare de tipul Shaker. (Shakersort).Principiu: reprezinta o varianta a metodei bubblesort, avind urmatoarele imbunatatiri:-la fiecare parcurgere a subtabloului a[i],...,a[N] se memoreaza indicele k al ultimei interschimbari efectuate, astfel incit la urmatoarea trecere un capat al subtabloului va fi marcat de k (intre 1 si k tabloul este ordonat);-se schimba alternativ sensul de parcurgere al subtablourilor pentru doua treceri consecutive.

Implementarea algoritmului in Pascal:

procedure ShakerSort; VAR j,k,l,r : TipIndex; x : TipElement; begin l:=2; r:=N; k:=N; repeat for j:=r downto l do if a[j-1].cheie>a[j].cheie then begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x; k:=j end; l:=k+1; for j:=l to r do if a[j-1].cheie>a[j].cheie then begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x; k:=j end; r:=k-1 until l > r end; {ShakerSort}La sortarile bubblesort si shakersort, M si C sint proportionali cu N*N, metodele fiind mai putin performante decit cele anterioare.

12.Parametrii care reflecta eficienta algoritmelor si programelor.

Pentru rezolvarea unei probleme exista de obicei mai multi algoritmi. Cand analizam un algoritm intai trebuie sa ne asiguram ca algoritmul duce la rezolvarea problemei si apoi sa vedem cat de eficient o face. Analiza unui algoritm presupune determinarea timpului necesar de rulare al algoritmului. Acesta nu se masoara in secunde, ci in numarul de operatii pe care le efectueaza. Numarul de operatii este strans legat de timpul efectiv de executie (in secunde) a algoritmului, dar nu acesta nu constituie o modalitate de masurare a eficientei algorimului deoarece un algoritm nu este "mai bun" decat altul doar daca il vom rula pe un calculator mai rapid sau este"mai incet" daca il rulam pe un

calculator mai putin performant. Analiza algoritmilor se face independent de calculatorul pe care va fi implementat sau de limbajul in careva fi scris. In schimb, presupune estimarea numarului de operatii efectuate.. Sigur ca eficienta unui algoritm depinde si de spatiul de memorie necesar rularii algoritmului. Un rol important in evaluarea eficientei unui algoritm il au valorile de intrare pentru care se aplica algoritmul. Cand se face analiza unui algoritm trebuie sa se ia in considerare toate clasele de valori de intrare posibile.Numim cel mai bun caz, cazul in care se efectueaza cele mai putine operatii,cel mai rau caz este cazul in care se efectueaza cele mai multe operatii. Asa cum am discutat mai sus, orice algoritm prezinta un necesar de timp si de memorie ce formeaza asa numita complexitatea algoritmului. Sigur ca nu vom putea calcula chiar timpul de executie a algoritmului ci vom determina o functie care depinde de marimea problemei de rezolvat si care este direct proportionala cu timpul de executie. Aceasta functie examineaza modul de crestere al timpului de executie in cazul cresterii marimei problemei rezolvate de catre algoritm. Aceasta functie se numeste rata de crestere a algoritmului. Comparand functiile de crestere a doi algoritmi putem determina care dintre ei este mai rapid si deci eficient. Pentru un algoritm dat, vom putea estima timpul minim, adica timpul de executie in cazul cel mai bun si timpul maxim, adica timpul de executie in cazul cel mai rau. Cele doua cazuri extreme apar foarte rar si o analiza completa presupune determinarea timpului mediu de executie definit ca media aritmetica a timpilor de executie corespunzatoare tuturor cazurilor posibile. Din pacate, acest lucru este mai greu si uneori ne vom limita la estimarea timpului maxim al unui algoritm.

13.Sortarea cu micsorarea incrementului. ( Shell Sort)Sortarea cu micsorarea incrementului (shellsort) este o extensie simplã al Insertion sortului care câstigã vitezã permitând schimbarea elementelor aflate departe. Ideea de bazã o constituie rearanjarea elementelor din tabela A în asa fel încât, luând fiecare a h-a element (începând de oriunde), sã obtinem o tabelã sortatã. Astfel spunem cã tabela este h-sortatã. O tabelã , h-sortatã este formatã din h subtabele sortate independent, intercalate. Folosind astfel o procedurã pentru fiecare secventã a valorii lui h care se terminã în 1, va produce o tabelã sortatã.Algoritmul este : shell-sort (a) h ← 1 pana cand h<n/9 h ← 3*h+1pana cand h>0 pentru i ← h+1 pana la n t ← a[i] j ← i pana cand (j>h si a[j-h] > t) interschimba(a[j], a[j-h]) j ← j-h h ← h/3-------------------------------------------------------------------------------------

14.Sortarea prin intermediul arborilor. Sortarea piramidala.   (Heapsort) Algoritmul HeapSort.

Este un algoritm, care a primit deumirea de aranjarea piramidala (HeapSort). Ideea sa consta din: in loc de completare aborele se formeaza un sir a[1], a[2],…,a[n] aranjat in piramida , aranjarea consta ca fiecare a[i] sa indeplineasca conditia a[i]<=a[2i]si a[i]<=a[2i+1]. Apoi piramida se foloseste pentru aranjare. Cea mai clara metoda de constructi a piramidei,se uita la aranjarea sirul intr-un arbore, prezentat in fig.2.9. Sirul este reprezentat ca arbore binar a carui virf corespunde cu elimentul sirului a[1]. La nivelul doi se gasesc elementele a[2]si a[3]. La nivelul trei a[4],a[5], a[6] a[7] si asa mai departe. Se observa ca petru un sir cu un numar impar de elemente, arborele va fi echilibrat, dar pentr-un un sir cu un numar par de elimente, n elimente a[n] va fi in partea stinga a foii asemanator cu un arbore

15.Algoritmul QuickSortMetoda de sortare a fost propusă de către Charles Hoare în 1962. Această metodă este dezvoltarea unei metode simple de schimb şi atât de eficientă, încât a devenit cunoscută sub numele de “metoda de sortare rapidă – QuickSort”. Ideea de bază a algoritmului constă în faptul că selectează la întîmplare un element x al matricei, după aceasta matricea se analizează din stînga, pînă cînd nu întîlneşte elementul a[i] astfel încît a[i]>x , şi apoi matricea se studiază din partea dreaptă, pînă cînd nu întîlneşte elementul a[j] astfel încît a[j]<x. Aceste 2 elemente sunt schimbate, precum şi procesul de vizualizare, compararea şi schimbul continuă pînă cînd vom ajunge la elementul x. În rezultat, matricea se divide în două părţi – stînga şi dreapta, în partea stînga valorile cheie vor fi mai mici decât x, iar în partea dreaptă valorile cheie vor fi mai mari decât x. În continuare procesul continuă recursiv pentru partea stîngă şi dreaptă a matricei, pînă cînd fiecare parte nu va conţine exact un element. Cunoaştem, ca de obicei , recursia poate fi înlocuită prin iteraţii, dacă să păstrăm în memorie indicii corespunzători din matrice. Să urmăm acest proces, ca de exemplu, în matricea noastră standard (tabel 2.6).Tabelul 2.6. Exemplu QuickSort.

Algoritmul nu este numit fara motiv sortarea rapidă,întrucîtpentru evaluarea lui numărul de comparaţii şi schimburi este O(nlogn). De fapt, de cele mai multe ori, tablourile de sortare utilizează anume acest algoritm.

Îmbunătăţiri

În practică pentru a creşte viteza, dar nu cea asimptotică, putem face cîteva optimizări:

În cazul funcţiei de partiţie elementul central este selectat în mijloc. Această alegere îmbunătăţeşte estimarea timpului mediu, în cazul în care matricea este ordonată parţial.

1'. Putem selecta media din primele elemente, ultimele şi cele mijlocii. Maxim Razin: În acest caz, numărul de treceri va scădea de 7/6 ori.

1. Pentru matrici mai scurte se numeşte sortare prin inserare. Din cauza recursiei şi a altor „calcule adaugătoare” QuickSort nu este un algoritm eficient pentru tablouri mici.

2. Dacă ultimul operator al funcţiei este un apel la această funcţie, atunci se numeşte coadă-recursivă. Aceasta are sens să fie înlocuită prin iteraţii – în acest caz mai bine de utilizat stiva.

3. După rupere mai întîi se sortează prima secţiune. Aici, de asemenea, mai bine de utilizat stiva, întrucît secţiunile mici se sortează mai rapid şi ele au nevoie de o stivă mai mică. Cerinţele de memorie sunt reduse de la n la logn.