Continut

• Algoritmi de prelucrare a sirurilor de caractere: Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp, Deplaseaza-aduna
• Algoritmi de prelucrare a grafurilor: union-find, determinarea componentelor tare conexe, identificarea grafurilor bipartite, metoda Ford-Fulkerson
• Algoritmi de criptare si decriptare: generare numere aleatoare, lucrul cu numere mari, criptare simetrica si asimetrica
• Algoritmi de compresie: compresie aritmetica, compresie cu arbori spay
• Retele neurale: retele Hopfield, modelul perceptronului, retele BackPropagation, retele QuickPropagation, retele Cascade-Correlation, harti Kohonen, extragerea regulilor simbolice din retele neurale
• Algoritmi genetici: algoritmi unipopulatie, algoritmi multipopulatie coevolutivi, evoluarea retelelor Cascade-Correlation

Teme de semestru 1999-2000
Se alege una din urmatoarele 5 teme si se elaboreaza programul in C sau C++ (eventual Java). Programul se aduce pe discheta la ultimul laborator de SPTR si se prezinta cu explicatii si rulare pe mai multe cazuri de test. Fiecare program va contine comentarii. Consideratiile de eficienta vor apare (acolo unde este cazul) in comentarii.

TEMA Nr. 1
1.1 Fie G = (V,E) un graf neorientat si conex, iar w: E -->R o functie cost. Presupunem ca |E| > |V|.
 i) gasiti o implementare eficienta pentru reprezentarea multimilor disjuncte (incluzand operatori pentru creearea unei multimi formate dintr-un singur element, pentru gasirea reprezentantului unei multimi si pentru reuniunea a doua multimi) si utilizati-o pentru gasirea componentelor conexe ale unui graf si a arborelui de acoperire minimal.
Comentati eficienta algoritmului si a structurii de date.
 ii) aratati ca exista mai mult de un arbore de acoperire minimal si construiti un algoritm eficient care gaseste "urmatorul arbore de acoperire minimal", i.e. cel cu costul mai mare decat al arborelui de acoperire minimal, dar mai mic decat al tuturor celorlalti arbori de acoperire.

1.2 Scrieti un algoritm care gaseste componentele tare conexe ale unui graf orientat.
Programul va contine proceduri pentru afisarea grafului si a arborilor in fiecare etapa a constructiei. (fie grafic, fie analitic). Eficienta implementarii este o cerinta importanta.
 

TEMA Nr. 2
Implementati un editor de text simplu. Utilizatorul va putea sa scrie text, sa se intoarca si sa modifice textul scris, sa salveze intr-un fisier textul scris, si sa incarce un fisier text. De asemenea, va putea sa caute un sablon in text, in mod repetat, sau sa modifice aparitiile unui sablon. Utilizati algoritmul Boyer-Moore care foloseste doua euristici: euristica caracterului nepotrivit si cea a sufixului bun. Implementati de asemenea o cautare care dupa un sablon ce contine simboluri don't care, clase de caractere, complemente ale unor clase de caractere precum si o cautare de tipul "sound like".
Incercati sa comparati performantele (numar de comparatii) algoritmilor folositi pentru diferite texte.

Obs. 1. Nu este necesara o interfata elaborata (ferestre, cursor, etc). Limitati-va la
minimum necesar.

Obs. 2. Euristica sufixului bun in cazul algoritmului Boyer-Moore.
Se considera portiunea P[j+1..m] de sablon care a fost identificata in momentul descoperirii unei nepotriviri la P[j]. Se cauta un prefix maxim P[1..k] al sablonului, a.i. unul dintre P[j+1..m] si P[1..k] sa fie sufixul celuilalt. Sablonul se deplaseaza la dreapta cu  m-k pozitii. Fiecare euristica propune o deplasare, algoritmul alege valoarea maxima propusa.

Obs. 3. Facultativ! Implementati o facilitate de verificare a cuvintelor folosite ("spelling"). Gasiti o structura de date eficienta pentru pastrarea dictionarului.
 

TEMA Nr. 3
3.1. Sa se implementeze o memorie asociativa Hopfield cu N noduri.
Aplicatie: Considerati reprezentarea pe 12x10 pixeli a imaginii alb/negru a fiecareia din urmatoarele cifre: 0 1 2 3 4.
Initializati reteaua Hopfield (N=12x10=120 noduri) pe baza celor 5 sabloane binare astfel obtinute (+1-negru,-1-alb). Aplicati la intrarea retelei variante distorsionate ale sabloanelor (o varianta distorsionata a unui sablon S poate fi obtinuta astfel: se inverseaza aleator - cu o probabilitate de 25%- fiecare pixel al sablonului S).
Faceti o afisare a sablonului aplicat si a sablonului obtinut la iesirea retelei, precum si a numarului de iteratii (ar trebui ca la  iesire sa obtineti sablonul nedistorsionat).

3.2. Sa se implementeze un perceptron multistrat cu M straturi, N1 noduri de intrare si N2 noduri de iesire, care sa foloseasca pentru invatare algoritmul standard de BackPropagation. Functia de transfer este functia sigmoida.
Aplicatie: Considerati 70 de sabloane de 6x6 pixeli (=>N1=36), de tipul urmator:
        ----------------
        |         |       |
        |   a    |  b    |
        ----------------
        |         |       |
        |   c    |  d    |
        ----------------
cu maxim 2 din subpatratele a,b,c,d colorate (nuante de gri). Daca sablonul are 2 subpatrate colorate, ele au o latura comuna si aceeasi culoare (ar tb. sa rezulte 8 clase de sabloane, adica N2=8). Incercati si sabloane distorsionate.
Scalati valorile elementelor sabloanelor, a.i. sa se incadreze in  (-1,+1). Antrenati reteaua pe baza a 2/3 din nr. de sabloane, afisand curba de erori. Evaluati performantele retelei, mai intai pe sabloanele de antrenament, apoi pe cele ramase ("sabloane de test").

Nota: Alegerea dimensiunii retelei se face prin "trial & error".
Indicatie: In general sunt necesare cel mult 2 straturi ascunse, iar nr. de noduri/strat ascuns trebuie sa fie mai mic dacat nr. sabloane antrenament, altfel reteaua ajunge sa "memoreze" sabloanele, pierzand din capacitatea de generalizare.
 

TEMA Nr. 4
Implementati problema acoperirii maximale a vectorilor. Problema consta in a gasi N vectori binari care identifica intr-un procent cat mai mare o alta multime de K vectori binari, unde K >> N. Multimea de N vectori se numeste "setul de identificare" iar cea de K vectori "setul tinta". Deoarece K este mult mai mare decat N, setul de identificare trebuie sa contina sabloane ce identifica mai multi vectori din setul tinta astfel incat cei N vectori sa acopere tinta in mod optim
(cat mai bine, altfel spus sa generalizeze tinta).
Coeficientul de identificare S a doi vectori x si y de lungime L este dat de suma bitilor de aceeasi valoare din pozitii identice din cei doi vectori
                S(x,y) = Suma(1, daca xi=yi, o daca xi<>yi), i=1,L
Coeficientul de identificare a unui set de identificare M este dat de relatia
                S(M) = (1/K) * Suma(max(S(m1,ti), ..., S(mN,ti))), i=1,K
unde mi si ti sunt elemente din setul de identificare si, respectiv, setul tinta.

Sa se utilizeze pentru modelarea si respectiv rezolvarea acestei probleme una din urmatoarele solutii:
- retele neurale
- algoritmi de cautare pe siruri de caractere
- algoritmi genetici
Sa se indice complexitatea timp a rezolvarii date. Intrebare la care trebuie sa se raspunda: problema admite o unica solutie sau mai multe?

Optional: Sa se implementeze doua solutii alternative si sa se compare performantele.
 

TEMA Nr. 5
Sa se implementeze un comparator de siruri de caractere utilizand algoritmul "deplaseaza-aduna" pentru cazurile:
a - identificare cu clase de caractere (inclusiv don't care symbols) si k nepotriviri
b - identificare exacta pe siruri de 2 dimensiuni
c - identificarea de la punctul a) pe siruri de 2 dimensiuni
d - implementati o facilitate de verificare a cuvintelor folosite ("spelling") utilizand acest algoritm. Gasiti o structura de date eficienta pentru pastrarea dictionarului. Sa se indice complexitatea timp a rezolvarii in fiecare caz.