🗊Презентация Paradigme de proiectare a algoritmilor

Категория: Математика
Нажмите для полного просмотра!
Paradigme de proiectare a algoritmilor, слайд №1Paradigme de proiectare a algoritmilor, слайд №2Paradigme de proiectare a algoritmilor, слайд №3Paradigme de proiectare a algoritmilor, слайд №4Paradigme de proiectare a algoritmilor, слайд №5Paradigme de proiectare a algoritmilor, слайд №6Paradigme de proiectare a algoritmilor, слайд №7Paradigme de proiectare a algoritmilor, слайд №8Paradigme de proiectare a algoritmilor, слайд №9Paradigme de proiectare a algoritmilor, слайд №10Paradigme de proiectare a algoritmilor, слайд №11Paradigme de proiectare a algoritmilor, слайд №12Paradigme de proiectare a algoritmilor, слайд №13Paradigme de proiectare a algoritmilor, слайд №14Paradigme de proiectare a algoritmilor, слайд №15Paradigme de proiectare a algoritmilor, слайд №16Paradigme de proiectare a algoritmilor, слайд №17Paradigme de proiectare a algoritmilor, слайд №18Paradigme de proiectare a algoritmilor, слайд №19Paradigme de proiectare a algoritmilor, слайд №20Paradigme de proiectare a algoritmilor, слайд №21Paradigme de proiectare a algoritmilor, слайд №22Paradigme de proiectare a algoritmilor, слайд №23Paradigme de proiectare a algoritmilor, слайд №24Paradigme de proiectare a algoritmilor, слайд №25
Скачать
Вы можете ознакомиться и скачать презентацию на тему Paradigme de proiectare a algoritmilor. Доклад-сообщение содержит 25 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Paradigme de proiectare a algoritmilor Despre paradigme de proiectare a algoritmilor Paradigma divide-et-impera Prezentarea generala a paradigmei Studii de caz cautare binara constructia arborelui binar de cautare sortare prin interclasare sortare rapida (quick sort) selectionare transformarea Fourier rapida “chess board cover” linia orizontului
Описание слайда:
Paradigme de proiectare a algoritmilor Despre paradigme de proiectare a algoritmilor Paradigma divide-et-impera Prezentarea generala a paradigmei Studii de caz cautare binara constructia arborelui binar de cautare sortare prin interclasare sortare rapida (quick sort) selectionare transformarea Fourier rapida “chess board cover” linia orizontului

Слайд 2


Despre paradigmele de proiectare a algoritmilor Avantajele aduse de constructia modelului matematic: eliminarea ambiguitatilor si inconsistentelor utilizarea intrumentelor matematice de investigare diminuarea efortului de scriere a programelor
Описание слайда:
Despre paradigmele de proiectare a algoritmilor Avantajele aduse de constructia modelului matematic: eliminarea ambiguitatilor si inconsistentelor utilizarea intrumentelor matematice de investigare diminuarea efortului de scriere a programelor

Слайд 3


Paradigma divide-et-impera Modelul matematic P(n): problema de dimensiune n baza daca n  n0 atunci rezolva P prin metode elementare divide-et-impera divide P in a probleme P1(n1), ..., Pa(na) cu ni  n/b, b > 1 rezolva P1(n1), ..., Pa(na) in aceeasi maniera si obtine solutiile S1, ..., Sa asambleaza S1, ..., Sa pentru a obtine solutia S a problemei P
Описание слайда:
Paradigma divide-et-impera Modelul matematic P(n): problema de dimensiune n baza daca n  n0 atunci rezolva P prin metode elementare divide-et-impera divide P in a probleme P1(n1), ..., Pa(na) cu ni  n/b, b > 1 rezolva P1(n1), ..., Pa(na) in aceeasi maniera si obtine solutiile S1, ..., Sa asambleaza S1, ..., Sa pentru a obtine solutia S a problemei P

Слайд 4


Paradigma divide-et-impera: algoritm procedure DivideEtImpera(P, n, S) begin if (n <= n0) then determina S prin metode elementare else imparte P in P1, ..., Pa DivideEtImpera(P1, n1, S1) ... DivideEtImpera(Pa, na, Sa) Asambleaza(S1, ..., Sa, S) end
Описание слайда:
Paradigma divide-et-impera: algoritm procedure DivideEtImpera(P, n, S) begin if (n <= n0) then determina S prin metode elementare else imparte P in P1, ..., Pa DivideEtImpera(P1, n1, S1) ... DivideEtImpera(Pa, na, Sa) Asambleaza(S1, ..., Sa, S) end

Слайд 5


Paradigma divide-et-impera: complexitate presupunem ca divizarea + asamblarea necesita timpul O(nk)
Описание слайда:
Paradigma divide-et-impera: complexitate presupunem ca divizarea + asamblarea necesita timpul O(nk)

Слайд 6


Cautare binara generalizare: s[p..q] baza: p  q divide-et-impera divide: m = [(p + q)/2] subprobleme: daca a < s[m] atunci cauta in s[p..m-1], altfel cauta in s[m+1..q] asamblare: nu exista complexitate: aplicind teorema: a = 1, b = 2, k = 0  T(n) = O(log n) calculind recurenta: T(n) = T(n/2) + 2 = T(n/4) + 4 = ... = T(1) + 2h = 2log n + 1
Описание слайда:
Cautare binara generalizare: s[p..q] baza: p  q divide-et-impera divide: m = [(p + q)/2] subprobleme: daca a < s[m] atunci cauta in s[p..m-1], altfel cauta in s[m+1..q] asamblare: nu exista complexitate: aplicind teorema: a = 1, b = 2, k = 0  T(n) = O(log n) calculind recurenta: T(n) = T(n/2) + 2 = T(n/4) + 4 = ... = T(1) + 2h = 2log n + 1

Слайд 7


Constructia arborelui binar problema intrare: o lista ordonata crescator s = (x0 < x1 < ... < xn-1) iesire: arbore binar de cautare echilibrat care memoreaza s algoritm generalizare: s[p..q] baza: p > q  arborele vid divide-et-impera divide: m = [(p + q)/2] subprobleme: s[p..m-1]  t1, s[m+1..q]  t2 asamblare: construieste arborele binar t cu radacina s[m], t1 subarbore stinga si t2 subarbore dreapta. complexitate: aplicam teorema: a = 2, b = 2, k = 0  T(n) = O(n)
Описание слайда:
Constructia arborelui binar problema intrare: o lista ordonata crescator s = (x0 < x1 < ... < xn-1) iesire: arbore binar de cautare echilibrat care memoreaza s algoritm generalizare: s[p..q] baza: p > q  arborele vid divide-et-impera divide: m = [(p + q)/2] subprobleme: s[p..m-1]  t1, s[m+1..q]  t2 asamblare: construieste arborele binar t cu radacina s[m], t1 subarbore stinga si t2 subarbore dreapta. complexitate: aplicam teorema: a = 2, b = 2, k = 0  T(n) = O(n)

Слайд 8


Sortare prin interclasare (Merge sort) generalizare: a[p..q] baza: p  q divide-et-impera divide: m = [(p + q)/2] subprobleme: a[p..m], a[m+1..q] asamblare: interclaseaza subsecventele sortate a[p..m] si a[m+1..q] initial memoreaza rezultatul interclasarii in temp copie din temp[0..p+q-1] in a[p..q] complexitate: timp a = 2, b = 2, k = 1 T(n) = O(n log n) spatiu suplimentar: O(n)
Описание слайда:
Sortare prin interclasare (Merge sort) generalizare: a[p..q] baza: p  q divide-et-impera divide: m = [(p + q)/2] subprobleme: a[p..m], a[m+1..q] asamblare: interclaseaza subsecventele sortate a[p..m] si a[m+1..q] initial memoreaza rezultatul interclasarii in temp copie din temp[0..p+q-1] in a[p..q] complexitate: timp a = 2, b = 2, k = 1 T(n) = O(n log n) spatiu suplimentar: O(n)

Слайд 9


Sortare rapida (Quick sort) generalizare: a[p..q] baza: p  q divide-et-impera divide: determina k intre p si q prin interschimbari a.i. dupa determinarea lui k avem: p  i  k  a[i]  a[k] k < j  q  a[k]  a[j]
Описание слайда:
Sortare rapida (Quick sort) generalizare: a[p..q] baza: p  q divide-et-impera divide: determina k intre p si q prin interschimbari a.i. dupa determinarea lui k avem: p  i  k  a[i]  a[k] k < j  q  a[k]  a[j]

Слайд 10


Quick sort: partitionare initial: x  a[p] (se poate alege x arbitrar din a[p..q]) i  p+1 ; j  q pasul curent: daca a[i]  x atunci i  i+1 daca a[j]  x atunci j  j-1 daca a[i] > x > a[j] si i < j atunci swap(a[i], a[j]) i  i+1 j  j-1 terminare: conditia i > j operatii k  i-1 swap(a[p], a[k])
Описание слайда:
Quick sort: partitionare initial: x  a[p] (se poate alege x arbitrar din a[p..q]) i  p+1 ; j  q pasul curent: daca a[i]  x atunci i  i+1 daca a[j]  x atunci j  j-1 daca a[i] > x > a[j] si i < j atunci swap(a[i], a[j]) i  i+1 j  j-1 terminare: conditia i > j operatii k  i-1 swap(a[p], a[k])

Слайд 11


Quick sort: complexitate complexitatea in cazul cel mai nefavorabil: T(n) = O(n2) complexitatea medie
Описание слайда:
Quick sort: complexitate complexitatea in cazul cel mai nefavorabil: T(n) = O(n2) complexitatea medie

Слайд 12


Selectionare problema intrare: o lista a = (x0, x1, ..., xn-1) iesire: cel de-al k+1-lea numar cel mai mic algoritm pp. i  j  a[i]  a[j] cel de-al k+1-lea numar cel mai mic este caracterizat de: (i)i < k  a[i] <= a[k] (j)k < j  a[k] <= a[j] divide-et-impera divide: partitioneaza(a, p, q, k1) subprobleme: daca k1 = k atunci stop; daca k < k1 atunci selecteaza din a[p..k1-1], altfel selecteaza din a[k1+1..q] asamblare: nu exista complexitate: n + k log(n/k) + (n-k) log(n/(n-k))
Описание слайда:
Selectionare problema intrare: o lista a = (x0, x1, ..., xn-1) iesire: cel de-al k+1-lea numar cel mai mic algoritm pp. i  j  a[i]  a[j] cel de-al k+1-lea numar cel mai mic este caracterizat de: (i)i < k  a[i] <= a[k] (j)k < j  a[k] <= a[j] divide-et-impera divide: partitioneaza(a, p, q, k1) subprobleme: daca k1 = k atunci stop; daca k < k1 atunci selecteaza din a[p..k1-1], altfel selecteaza din a[k1+1..q] asamblare: nu exista complexitate: n + k log(n/k) + (n-k) log(n/(n-k))

Слайд 13


Transformata Fourier discreta I descrierea unui semnal domeniul timp: f(t) domeniul frecventa: F() Transformata Fourier directa:
Описание слайда:
Transformata Fourier discreta I descrierea unui semnal domeniul timp: f(t) domeniul frecventa: F() Transformata Fourier directa:

Слайд 14


Transformata Fourier discreta - aplicatie Filtrarea imaginilor transformata Fourier a unei functii este echivalenta cu reprezentarea ca o suma de functii sinus eliminand frecventele foarte inalte sau foarte joase nedorite (adica eliminand niste functii sinus) si aplicand transformata Fourier inversa pentru a reveni in domeniul timp, se obtine o filtrare a imaginilor prin eliminarea “zgomotelor” Compresia imaginilor o imagine filtrata este mult mai uniforma si deci va necesita mai putini biti pentru a fi memorata
Описание слайда:
Transformata Fourier discreta - aplicatie Filtrarea imaginilor transformata Fourier a unei functii este echivalenta cu reprezentarea ca o suma de functii sinus eliminand frecventele foarte inalte sau foarte joase nedorite (adica eliminand niste functii sinus) si aplicand transformata Fourier inversa pentru a reveni in domeniul timp, se obtine o filtrare a imaginilor prin eliminarea “zgomotelor” Compresia imaginilor o imagine filtrata este mult mai uniforma si deci va necesita mai putini biti pentru a fi memorata

Слайд 15


Transformata Fourier discreta II cazul discret xk = f(tk) k=0,…,n-1 tk = kT, T = perioada de timp la care se fac masuratorile
Описание слайда:
Transformata Fourier discreta II cazul discret xk = f(tk) k=0,…,n-1 tk = kT, T = perioada de timp la care se fac masuratorile

Слайд 16


Transformata Fourier discreta III rolul radacinilor unitatii de ordinul n
Описание слайда:
Transformata Fourier discreta III rolul radacinilor unitatii de ordinul n

Слайд 17


Transformata Fourier discreta IV
Описание слайда:
Transformata Fourier discreta IV

Слайд 18


Chess board cover problem
Описание слайда:
Chess board cover problem

Слайд 19


Chess board cover problem
Описание слайда:
Chess board cover problem

Слайд 20


Chess board cover problem
Описание слайда:
Chess board cover problem

Слайд 21


Linia orizontului
Описание слайда:
Linia orizontului

Слайд 22


Linia orizontului
Описание слайда:
Linia orizontului

Слайд 23


Linia orizontului
Описание слайда:
Linia orizontului

Слайд 24


Linia orizontului
Описание слайда:
Linia orizontului

Слайд 25


Linia orizontului
Описание слайда:
Linia orizontului

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию