TPA

Get Started. It's Free
or sign up with your email address
Rocket clouds
TPA by Mind Map: TPA

1. arb huffman

1.1. scop: codificare simboluri optima fata de frecv (nr aparitii)

1.2. ex: HARABABURA

1.2.1. H(1)A(4)R(2)B(2)U(1)

1.2.1.1. r

1.2.1.1.1. 6(1)

1.2.1.1.2. 4(0)

2. Ordinul de complexitate

2.1. Tipuri

2.1.1. logaritmica

2.1.2. liniara

2.1.3. patratica

2.1.4. exponentiala

3. copaci bengoshi

3.1. bicolori

3.1.1. rad neagra

3.1.2. nr de ngre pe orice traseu rad ->frunza e acelasi

3.1.3. rosu are neaparat copii negri

3.1.4. nod inserat rosu

3.2. 2-3

3.2.1. orice nod are 2/3 copii

3.2.2. toate frunzele sunt pe acelasi nivel (ech)

3.3. B-arbori

3.3.1. generalizare 2-3 arb cu prop

3.3.2. f = factor de minimizare

3.3.3. ord arb = 2f-1

3.4. digitali

3.4.1. chei de aceasi lungim

3.4.1.1. fiecare nod contine un "array" cu indici toate cheile (o sigura data)

3.4.1.2. se construiesc cheile pe un drum de la rad la frunze, bifand pozitia coresp. din nod

3.4.2. chei de lungime diferita

3.4.2.1. ?

4. greedy

4.1. rucsac

4.1.1. alegerea locala optima (profit maxim pe unitate de greutate)

5. arb cost min

5.1. Algoritmul lui Kruskal

5.2. Algoritmul lui prim

6. divite et impera

7. quicksort

8. mergesort

9. programaredinamica

10. cautare pe siruri

10.1. KMP(fail)- border(st la dr)

10.1.1. border maxim in P => subsir X cu border maxim y (subsir <= P)

10.1.1.1. shift la dr cu X.length - y.length

10.2. Boyer Moore(jump) dr la st

10.2.1. bad char heuristic

10.2.1.1. mismatch( char T = s, char P = d)

10.2.1.1.1. gasesc s in P

10.2.1.1.2. nu gasesc S in p,

10.2.2. good suffix

10.2.2.1. mismatch

10.2.2.1.1. sufixul din T se cauta in stanga sufix P

10.2.3. 0\preprocessing tale and salt function

10.3. Rabin KARP(hash)

10.3.1. de la st la dr

10.3.2. se compara h(P) cu h(T{P.length})

10.3.2.1. verificare daca exista coliziuni

11. ?

11.1. Backtracking

11.2. NP complete

11.3. alg probabilistici

11.3.1. Monte Carlo

11.3.2. las vegas