Post on 11-Feb-2020
FIŞA DISCIPLINEI
1. Date despre program1.1 Instituţia de învăţământ superior Universitatea “Alexandru Ioan Cuza” din Iaşi1.2 Facultatea Facultatea de Informatică1.3 Departamentul1.4 Domeniul de studii Informatică1.5 Ciclul de studii Master1.6 Programul de studii / Calificarea Optimizare Computațională
2. Date despre disciplină2.1 Denumirea disciplinei Analiza experimentală a algoritmilor2.2 Titularul activităţilor de curs Conf. dr. Răschip Mădălina2.3 Titularul activităţilor de seminar Conf. dr. Răschip Mădălina2.4 An de studiu 1,2 2.5 Semestru 1 2.6 Tip de evaluare E 2.7 Regimul discipinei* OP* OB – Obligatoriu / OP – Opţional
3. Timpul total estimat (ore pe semestru şi activităţi didactice)3.1 Număr de ore pe săptămână 4 din care: 3.2 curs 2 3.3 seminar/laborator 23.4 Total ore din planul de învăţământ 56 din care: 3.5 curs 28 3.6 seminar/laborator 28Distribuţia fondului de timp oreStudiu după manual, suport de curs, bibliografie şi altele 14Documentare suplimentară în bibliotecă, pe platformele electronice de specialitate şi pe teren 14Pregătire seminarii/laboratoare, teme, referate, portofolii şi eseuri 28TutoriatExaminări 4Alte activităţi ...................................
3.7 Total ore studiu individual 563.8 Total ore pe semestru 1163.9 Număr de credite 8
4. Precondiţii (dacă este cazul)
4.1 De curriculumOptimizare combinatorială, Cercetări operaționale, Invățare automată
4.2 De competenţe Algoritmi, clase de complexitate
5. Condiţii (dacă este cazul)
5.1 De desfăşurare a cursului
5.2 De desfăşurare a seminarului/ laboratorului
6. Competenţe specifice acumulate
Co
mp
ete
nţe
pro
fes
ion
ale
C1. Abilitatea de a modela probleme (de optimizare) din lumea reală folosind diferite unelte (bazate pe grafuri, programare în numere întregi (mixta), programare cu restricții) și de a proiecta algoritmi eficienți pentru le rezolva.C2. Abilitatea de a analiza eficiența algoritmilor (asimptotic): analiza cazului nefavorabil, analiza cazului mediu, analiza amortizată, analiza smooth.C3. Abilitatea de a utiliza structuri de date și algoritmi specifici memoriei externe, structuri de date si algoritmi de tipul cache-aware sau cache-oblivious pentru a proiecta algoritmi eficienți.C4. Abilitatea de a proiecta experimente, de a evalua și raporta rezultatele obținute.
Co
mp
ete
nţe
tra
ns
vers
ale
CT1. Cunoașterea tehnicilor avansate de a îmbunătăți eficiența unui algoritm.CT2. Abilitatea de a selecta cele mai bune valori ale parametrilor unui algoritm (folosind tehnici de automated tuning) și de a prezice timpul de execuție al unui algoritm.
7. Obiectivele disciplinei (din grila competenţelor specifice acumulate)
7.1
Ob
iec
tiv
ul
ge
ne
ral
Studenții trebuie să fie capabili să elaboreze algoritmi eficienți pentru probleme de optimizare din lumea reală, să analizeze complexitatea algoritmilor, să verifice corectitudinea acestora și să analizeze dpdv statistic rezultate experimentale obținute.
7.2
Ob
iec
tiv
ele
sp
ec
ific
e
La finalizarea cu succes a acestei discipline, studenţii vor fi capabili să: Modeleze probleme (de optimizare) din lumea reală. Proiecteze algoritmi eficienți. Analizeze asimptotic un algoritm. Utilizeze structuri de date și algoritmi specifici modelelor de tip memorie externă, cache-aware și
cache-oblivious. Proiecteze experimente, să evalueze și să raporteze rezultatele experimentale. Configureze in mod automat un algoritm. Să prezică timpul de execuție a unui algoritm.
8. Conţinut
8.1 Curs Metode de predare Observaţii(ore şi referinţe bibliografice)
1. Introducere in Ingineria Algoritmilor. Predare însoțită de slide-uri 2
2. Modelarea problemelor Predare însoțită de slide-uri 2
3. Proiectarea algoritmilor Predare însoțită de slide-uri 2
4-5. Analiza algoritmilor Predare însoțită de slide-uri 4
6.
Modele de calcul realiste (structuri de date și algoritmi specifici modelelor de tipul memorie externa, cache-aware, cache-oblivious)
Predare însoțită de slide-uri 2
7.Aspecte legate de implementarea algoritmilor. Corectitudinea si verificareaunui algoritm.
Predare însoțită de slide-uri 2
8-9.Experimentare. Planificarea experimentelor. Evaluarea datelor. Raportarea rezultatelor experimentale.
Predare însoțită de slide-uri 4
10. Configurarea automată a algoritmilor Predare însoțită de slide-uri 2
11-12.
Selecția automată a algoritmilor. Predicția timpului de execuție a unui algoritm
Predare însoțită de slide-uri 4
13-14.
Studii de caz Predare însoțită de slide-uri 4
Bibliografie
Referinţe principale:
Algorithm Engineering: Bridging the Gap between Algorithm Theory and Practice, M. Muller-Hannemann, S. Schirra (Eds.), Springer, 2010
Experimental Methods for the Analysis of Optimization ALgorithms, Th. Bartz-Beielstein, M. Chiarandini, L. Paquete, M. Preuss (Eds.), Springer 2010
J.A. Rice, Mathematical Statistics and Data Analysis, Duxbury Press, 2006
8.2 Seminar / Laborator Metode de predare Observaţii(ore şi referinţe bibliografice)
1.Unelte de modelare. Formulare MIP. CPLEX.
Exerciții, metode interactive 2
2.Programare cu restricții. Modelare CPLEX
Exerciții, metode interactive 2
3.CPLEX - Statistici si tehnici de tuning pentru performanță
Exerciții, metode interactive 2
4.Proiect – modul 1: modelare - prezentare
Lucru individual, evaluare 2
5.Librării pentru tipuri de date și algoritmi eficienți
Exerciții, metode interactive 2
6.Tipuri de date și algoritmi pentru modele de tip memorie externă, cache-aware, cache oblivious
Exerciții, metode interactive 2
7. Analiza exploratorie a datelor Exerciții, metode interactive 2
8.Proiect – modul 2: implementarea algoritmilor si evaluarea acestora
Lucru individual, evaluare 2
9-10.
Analiza statistică a datelor Exerciții, metode interactive 4
11. Configurarea automată a algoritmilor Exerciții, metode interactive 2
12.Predicția timpului de execuție a unui algoritm
Exerciții, metode interactive 2
13. Tuning Exerciții, metode interactive 2
14. Proiect- modul 3: tuning Lucru individual, evaluare 2
BibliografieTutoriale online – disponibile pe pagina laboratorului
9. Coroborarea conţinutului disciplinei cu aşteptările reprezentanţilor comunităţii, asociaţiilor profesionale şi angajatorilor reprezentativi din domeniul aferent programului
Conținutul cursului este conceput pentru a răspunde necesităților angajatorilor din industria software și nu numai.
10. Evaluare
Tip activitate 10.1 Criterii de evaluare 10.2 Metode de evaluare10.3 Pondere în nota finală (%)
10.4 Curs Test scris 25%10.5 Seminar/ Laborator 3 proiecte, 1 raport 75%10.6 Standard minim de performanţă
50% din scorul maxim
Data completării Titular de curs Titular de seminar15.03.2018 Conf. dr. Răschip Mădălina Conf. dr. Răschip Mădălina
Data avizării în departament Director de departament