FMSE
Formal
Methods in
Software Engineering
Pages CS1211 Proiectarea algoritmilor (anul I) Anonymous  Login

CS1211 Proiectarea algoritmilor (anul I)

Incepand cu anul universitar 2014-2015, cursul are un nou sit: http://sites.google.com/site/fiicoursepa/

Informatiile de mai jos au fost valabile pentru anul universitar 2013-2014.

Organizare

Curs 1 Limbaj algoritmic executabil

  • model de memorie
  • instructiuni (sintaxa, semantica operationala - informal, formal)
  • algorimi nedeterministi

Seminar: algoritmi pentru operatii aritmetice (ex. http://www.dei.unipd.it/~geppo/DA2/DOCS/arithmetic.pdf)

Bibliografie suplimentara: versiunea pdf a limbajului alk (se poate obtine cu versiunea online a lui K, https://fmse.info.uaic.ro/tools/K/?tree=/alk-semantics/alk.k, "kompiland" cu optiunea "--backend pdf").

Prezentare

Curs 2 Problema rezolvata de un algoritm

  • formalizarea notiunii de problema
  • problema rezolvabila
  • problema de decizie
  • probleme nedecidabile, problema opririi
  • Complexitatea in cazul cel mai nefavorabil

Seminar: corectitudinea si calculul complexitatii pentru algoritmii de la seminarul precedent.

Bibliografie suplimentara: sectiunile 1.2, 1.3 din [LC2008]

Prezentare

Curs 3 Complexitatea problemelor

  • complexitatea in cazul cel mai nefavorabil a problemelor
  • complexitatea problemei de sortare
  • complexitatea problemei de cautare
  • reducerea

Seminar: complexitatea alg. de sortare prin numarare (problema steagului olandez), sortare prin distribuire, exemple de reducere de probleme

Prezentare

Bibliografie suplimentara: sectiunile 4.1, 5.1, 5.2 din [LC2008]

Curs 4,5 Algoritmi din geometria computationala

  • algoritmi de cautare/localizare
  • determinarea infasuratorii convexe
  • diagrama Voronoi

Seminar: alte exemple de alg. din geometria computationala

Bibliografie suplimentara:

J. Chen. Comptattional Geomtery: Methods and Applications. 1996, pdf

Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars. Computational Geometry -Algorithms and Applications.
Third Edition. Springer, 2008, pdf

L. Guibas.  Basic Algorithms and Combinatorics in Computational Geometry notes. Computer Science Department at Stanford University

Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. Springer-Verlag.

The CGAL (Computational Geometry Algorithms Library) web pages.

Prezentare 1

Prezentare 2

Curs 6  Complexitatea medie

  • algorimii ca variabile aleatorii
  • definitia complexitatii medie
  • complexitatea medie Quicksort
  • complexitatea medie a lui Bucketsort

Seminar: alte exemple de calcul a complexitatii medii

Prezentare

Curs 7,8 Algoritmi de cautare peste siruri

  • Boyer-Moore
  • Knuth-Morris-Prat
  • Aho-Corasick
  • Expresii regulate + automate

Seminar: exemplificarea algoritmilor pe diferite instante, aspecte privind implementarea

Prezentare 1 bm-ex.pptx bm-bad-character-shift-rule.pptx kmp-ideea.pptx Prezentare 2

Curs 9 Algoritmi greedy

  • prezentarea generala a paradigmei
  • doua studii de caz: problema rucsacului [0,1], arbori Huffman, arbori partiali de cost minim

Seminar: alte exemple de algoritmi greedy 

Despre paradigme  Prezentare algoritmi greedy

Curs 10 Programare dinamica

  • prezentarea generala a paradigmei
  • 2 studii de caz: problema rucsacului 0/1, distanta de editare dintre siruri

Seminar: probleme rezolvate prin programare dinamica

Prezentare  dist-sir-ex.pptx

Curs 11 Probleme NP complete

  • definitie, exemple, metode de demonstrare a NP-completitudinii

Seminar: alte exemple de probleme NP complete, de monstrarea ca sunt NP complete

Prezentare

Curs 12 Rezolvarea exacta a problemelor NP-complete

  • bactracking, brach-and-bound

Seminar: Exemple de probleme NP complete rezolvate prin backtracking

Prezentare

Curs 13 Algoritmi de aproximare

  • definitie, scheme de aproximare polinomiala
  • studii de caz: acoperirea de multimi, submultimea de suma data, comisul voiajor

Seminar: exemple de scheme de aproximare care nu s-au facut la curs

Prezentare

Testul partial

Data: 11.04.2014, Ora: 8:00 semian A, 9:30 semian B. Sali: C112, C2, C309

De invatat: Primele 6 cursuri. Algoritmii prezentati la curs trebuie intelesi bine pentru a cum pot fi aplicati pe instante de probleme. De stiut bine toate conceptele invatate la curs (complexitate algoritmi, complexitate probleme, problema rezolvata de un algoritm, reducerea de probleme). Nu este permisa consultarea bibliografiei in timpul testului. Verificarea autenticitatii numelui se face prin prezentarea carnetului de student la predarea testului. Algorimii vor fi descrisi in limbajul Alk. Se adimit extensii cu sintaxa inspirata din C++ (de exemplu, for, do-while, repeat-until). Pentru structurile de date utilizate se va preciza operatiile (fara implementare daca nu se cere explicit) si costurile timp si spatiu ale acestora.

S-au afisat rezultatele de la testul 1. Mai multe detalii si raspunsuri la eventualele intrebari la curs.

S-au afisat si raspunsurile de la subiectul A, pentru a avea ca model de raspuns si a compara. Deoarece subiectul B are o structura asemanatoare, raspunsurile la acest subiect nu se mai afiseaza.  

Testul din 09.06

De invatat. Cursurile 7-13. Raman valabile observatiile de la testul partial.

S-au afisat rezultatele la testul 2, baremul pentru subiectul A si baremul pentru subiectul B. Eventualele cereri de recorectare pot fi trimise numai de studentii care au participat la minim 7 cursuri pana marti 10.06.2014, ora 17:00. Tot pana atunci pot fi trimise si alte observatii, daca e cazul.

11.06.2014: In urma centralizarii punctejlor de la seminar si teste curs, au fost revizuite inca o data toate testele celor nu aveau punctaj de promovare dar erau aproape de limita (inclusiv a celora carora le-am raspuns prin email pe 10.6). Fisierul cu rezultate a fost actualizat, asa ca e bine de verificat situatia finala.

Notele finale vor fi trecute drect in SIMS si vor putea fi consultate cu eSIMS in maxim 1-2 zile (depinde de gradul de incarcare a colegilor de la secretariat). Eventualele observatii majore (de exemplu, privind stara promovat/nepromovat) vor fi semnalate prin email. 

Sesinea de restante

Testul scris din sesiunea de restante va include subiecte din toata materia.

Au fost afisate punctajele de la testul scris din 19.06 si baremul de corectare. Inainte de a trimite eventualele observatii (pana pe 20.06 ora 13), consultati raspunsurile din barem si cititi cu atentie cursurile din care au fost subiectele pentru a compara raspunsul dat cu cel corect.

 

Bibliografie

  • [LC2008]      Dorel Lucanu, Mitica Craus. Proiectarea algoritmilor. Polirom, 2008.
  • [CLR1990]   T.H. Cormen, C.E. Leiserson, R.L. Rivest: Introduction to Algorithms, MIT Press, 1990.
  • [CLR2000] T.H. Cormen, C.E. Leiserson, R.L. Rivest: Introducere in Algoritmi,Computer Libris Agora, 2000.
  • [PS1985] F.P. Preparata, M.I. Shamos. Computational geometry, An Introduction. Springer, 1985

 

NEWS
New publication : Model checking recursive programs interacting via ... - 01 feb 2015

Almost all modern imperative programming languages include operations for dynamically manipulating the heap, for example by allocating and deallocating objects, and by updating reference fields. In the presence of recursive ... (more)


New publication : K-Java: A Complete Semantics of Java - 10 sep 2014

This paper presents K-Java, a complete executable formal semantics of Java 1.4.
K-Java was extensively tested with a test suite developed alongside the project, following the Test Driven Development methodology.
more)


New publication : K-Java: A Complete Semantics of Java - 09 jul 2014

This paper presents K-Java, a complete executable formal semantics of Java 1.4.
K-Java was extensively tested with a test suite developed alongside the project, following the Test Driven Development methodology.
more)


New publication : Engineering Hoare Logic-based Program Verification in ... - 30 oct 2013

We propose a language-independent symbolic execution framework for languages endowed with a formal operational semantics based on term rewriting. Starting from a given definition of a language, a new language ... (more)


New talk: PAS 2013 - 20 oct 2013

Dorel lucanu will give a talk at PAS 2013.

(more)

     Archive

@FMSE 2010-2011