Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Metoda eoristica

o prezentare la metoda eoristica de rezolvare(tine de domeniul informaticii), care include si 3 probleme ))
by

Mihai Covrig

on 11 May 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Metoda eoristica

Exemple
Probleme Exemple
Probleme *urmeaza a fi utilizati de un numar mic de ori, ceea ce face ca un efort mare de programare sa nu se justifice; Eoristici 1) – Programarea aplicatiilor pe procesoare

Sa consideram problema programarii unor aplicatii pe mai multe procesoare: Se cere programarea a m aplicatii independente de durate (lungimi) diferite L= pe n procesoare astfel ca timpul de executie a lor (in ansamblu) sa fie cat mai mic, stiind ca:

§ procesoarele pot functiona simultan si pot procesa orice aplicatie;

§ procesarea unei aplicatii, odata inceputa pe un procesor, nu poate fi intrerupta si, deci, nici mutata pe alt procesor.

O programare este bine definita daca:

§ o aplicatie neprogramata este preluata de primul procesor liber;

§ procesoarele intra in functiune fara intarzieri. 2) Brainstorming Cind: Google Sunt preferati la utilizare??!! Metoda Eoristica Proprietati furnizeaza solutii „suficient” de bune, nu neaparat optimale este usor de implementat si obtine rezultate intr-un timp rezonabil, mai scurt decat in cazul utilizarii altor algoritmi optimali. Descrierea metodei O mare parte a algoritmilor de optim au un timp de executie de ordin exponential si necesita o cantitate mare de memorie. Pentru eliminarea acestui inconvenient, adeseori in practica sunt elaborati algoritmi care furnizeaza solutii nu neaparat optime, dar „suficient de bune” intr-un timp mult mai scurt si necesitand o cantitate de memorie acceptabila. Elaborarea acestor algoritmi are la baza, de regula, idei naturale, empirice, „de bun simt”. In cea mai mare parte a cazurilor, algoritmii Greedy incep ca algoritmi euristici, in care alegerea unui element se face astfel incat sa produca un optim local. Ulterior, in cazul algoritmilor Greedy, se demonstreaza faptul ca optimul local implica optim global. Insa in unele cazuri: optim local+optim local=optim global Da, cind... *efortul de determinare a unei solutii optime este prea mare fata de castigul obtinut Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici Eoristici (Rezolvate eoristic) (rezolvate matematic) Procedeul euristic utilizat provine dintr-o idee „de bun simt” si anume aceea de a alege, de fiecare data, aplicatia neprogramata cu cel mai mare timp de executie si a o programa pe procesorul care se va elibera primul. In acest sens, se va efectua in prealabil o sortare a aplicatiilor in ordine descrescatoare a timpilor lor de executie. Algoritmul este descris astfel:
P1. Se sorteaza descrescator aplicatiile dupa durata executiei;
P2. pentru fiecare aplicatie i
o se cauta procesorul cel mai putin ocupat, fie acesta p_min
o se programeaza aplicatia i pe procesorul p_min n=2 procesoare m=5 aplicatii L=2,3,3,2,2 Rezolvare eoristica #include<iostream.h>void ProgLucr(int *L,int *P,int m,int n)
deleteT;
}
main()
ProgLucr(L,P,m,n); for(i=0;i<m;i++) cout<<' Aplicatia de durata '<<Li<<' alocata pe procesorul '<<Pi<<endl;
deleteP;
deleteL;
return 0;
} Procesor 1 : | 3 | 2 | 2 |

Procesor 2 : | 3 | 2 |

T=7 > Rezolvare matematica metoda incercarilor xD Procesor 1 : | 3 | 3 |

Procesor 2 : | 2 | 2 | 2 |

T=6 Colorarea hartilor cu 4 culori Se cere colorarea unei harti, data prin matricea de vecinatati ale tarilor, cu un numar dat de culori (se poate demonstra ca patru culori sunt suficiente). Ideea euristica ce sta la baza acestui algoritm este de a colora pe rand fiecare tara cu prima culoare pe care vecinii deja colorati sai nu o folosesc. Rezolvare eoristica #include<iostream.h>
#include<math.h>
int *X,**V,n,r=4;
char *culori[]=;
void harta()
}
main()
harta();
for(i=0;i<n;i++) cout<<endl<<'Tara '<<i<<'-> culoarea '<<culori[X[i]]; for(i=0;i<n;i++)
delete V[i];
delete V;
delete[]X;
return 0;} Rezolvare matematica matematica vizuala, numararea vecinilor, si cunoasterea numarului de culori.... Traseul comis-voiajorului 3) Se considera n orase legate doua cate doua prin drumuri. Fiecare drum are asociat un cost cunoscut necesar parcurgerii sale. Un comis-voiajor trebuie sa plece dintr-un oras, sa treaca o singura data prin toate celelalte si sa se intoarca de unde a plecat astfel incat sa parcurga un drum de cost cat mai mic. Se cere sa se determine traseul comis-voiajorului.
O idee naturala, specifica metodelor euristice, este aceea de a pleca din orasul initial catre cel mai apropiat oras (cu cel mai mic cost al deplasarii) si tot asa, avand grija sa nu trecem de doua ori prin acelasi oras. Cand toate orasele au fost vizitate, ne intoarcem in orasul initial.
#include <iostream.h>
int ComisVoiajor(int *Cost[], int n, int *Traseu) //incudem nod_nou in traseu si ne deplasam in el Traseu[i]=nod_nou; cost+=cost_min; Vizitat[nod_nou]=1; nod_curent=nod_nou;
}
//incheiem lantul: inludem in traseu nodul initial Traseu[n]=0;
cost+=Cost[nod_curent][0]; delete[]Vizitat;
return cost;
}
main()
cout<<'Costurile dintre orase:'<<endl; for(i=0;i<n;i++)
for(int j=i+1;j<n;j++)
cout<<'Traseul are costul '<<ComisVoiajor(Cost,n,Traseu)<<' si consta in:'<<endl;
for(i=0;i<=n;i++) cout<<Oras[Traseu[i]]<<' ';
for(i=0;i<n;i++) delete[]Oras[i]; delete[]Oras; delete[]Traseu; for(i=0;i<n;i++) delete[]Cost[i]; delete[]Cost; return 0;
} Rezultat Eoristic Bucuresti (170) Brasov(170) Tg. Mures(320) Arad(740) Iasi(410) Bucuresti, in total 1810 km. Rezultat Matematic Bucuresti(170) Brasov(310) Iasi (330) Tg. Mures(320) Arad(560) Bucuresti,

un total mai mic, de numai 1690 km Sfirsit! Efectuat: Covrig Mihai
clasa XI "A"
profesor:Schitco Natalia Multumesc pentru atentie Nota: 10*n, n>3 xD Informatica
Full transcript