Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licență

FISA DISCIPLINEI

Codul
Denumirea disciplinei
MID0040 Programarea calculatoarelor si limbaje de programare
Specializarea
Semestrul
Ore: C+S+L
Categoria
Statutul
Ingineria informatiei
1
2+2+2
fundamentala
obligatorie
Titularii de disciplina
Asist. VESCAN Andreea,  avescancs.ubbcluj.ro
Lect. GURAN Adriana Mihaela,  adrianacs.ubbcluj.ro
Lect. Dr. IONESCU Clara,  claracs.ubbcluj.ro
Obiective
1. Intelegerea notiunii de algoritm si invatarea limbajului Pseudocod pentru descrierea algoritmilor;
2. Formarea deprinderilor de proiectare a algoritmilor;
3. Cunoasterea unor algoritmi pentru unele clase de probleme: operatii cu vectori, matrice, polinoame, rezolvari de ecuatii si sisteme liniare, cautare, interclasare si sortare;
4. Formarea deprinderilor de concepere, executie, testare si punere la punct a programelor Pascal cu structurile de date simple;
5. Formarea unui stil de programare.
Continutul
1. Algoritmi si descrierea lor
- Notiunea de algoritm
- Variabila, tip, specificare
- scheme logice
- limbajul Pseudocod: Structura liniara, Structura alternativa, Structura repetitiva

2. Subalgoritmi (Pseudocod)
- notiunea de subalgoritm
- parametrii formali
- definirea unui subalgoritm (functie si procedura)
- apelul unui subalgoritm
- importanta subalgoritmilor în programare

3. Codificarea algoritmilor Pseudocod în Pascal
- Elemente de baza ale limbajului Pascal
- Declaratii si Instructiuni
- Structura unui program Pascal
- Codificare

4. Faze in viata unui program
- Faze în realizarea unui program: specificare, proiectare, codificare, testare, documentare, verificare
- intretinerea programelor: corectiva, adaptiva, perfectiva
- Testarea programelor: Metoda cutiei negre, Metoda cutiei transparente

5. Corectitudinea algoritmilor
- stare în executia unui program;
- calcul efectuat de un algoritm;
- rezultatul calculului efectuat de un algoritm;
- partial corectitudine;
- terminare;
- (total) corectitudine;
- metoda lui Floyd de demonstrare a corectitudinii

6. Dezvoltarea corecta a algoritmilor din specificatii
- algoritm abstract
- ideea de rafinare
- reguli de rafinare
- exemple

7. Metode generale de elaborare a algoritmilor
- programare modulara
- programare structurata
- teorema lui Bohm-Jacopini
- importanta claritatii în programare
- elemente de claritate: indentare, spatiere, denumiri,...
- stil în programare

8. Metoda top-down si Rafinarea în pasi succesivi
- metoda top-down
- metoda bottom-up
- rafinarea în pasi succesivi

9. Recursivitate
- Notiunea de Recursivitate
- Recursivitate directa si indirecta
- Exemple

10. Tipuri Abstracte de Date
- specificarea unui TAD
- Unit Pascal
- Implementarea unui TAD în Pascal
- Folosirea unui TAD în programare

11. Metoda Divide et Impera
- Prezentare generala
- Descrierea subalgoritmului
- exemple

12. Metoda Backtracking
- Prezentarea generala a metodei Backtracking
- Algoritm (subalgoritm) Backtracking
- Extinderi ale metodei Backtracking
- exemple

13. Metoda Greedy
- Prezentarea generala a metodei greedy
- Algoritmul Greedy
- exemple si contraexemple
- euristica Greedy

14. Alte metode
- Metoda programarii dinamice
- Metoda Branch and Bound
- exemple
- Metode euristice

15. Complexitatea algoritmilor
- definitia complexitatii
- complexitatea ca timp de executie
- complexitatea ca memorie suplimentara necesara
- analiza empirica si analiza asimptotica
- notatia asimptotica: o-mare, o-mic, omega-mare, omega-mic, theta
- proprietati
- ordine de marime particulare
- compararea algoritmilor din punctul de vedere al eficientei
- complexitatea structurala

16. Algoritmi de cautare si complexitatea lor
- Specificarea problemei de cautare
- Metode de cautare: parcurgere secventiala, cautare binara
- Complexitatea algoritmilor de cautare

17. Algoritmi de sortare si complexitatea lor
- Specificarea problemei de sortare
- Metode de sortare
- Metoda bulelor (BubbleSort)
- Sortare bazata pe selectarea minimului/maximului (SelectSort)
- Sortare prin inserare (InsertSort)
- Sortare rapida (QuickSort)
- Sortare prin interclasare (MergeSort)
- Complexitatea algoritmilor de sortare
Bibliografie
1. Frentiu, M., H.F. Pop, Fundamentals of Programming, Cluj University Press, 2006, 220 pagini
2. M.Frentiu si altii, Manualul incepatorului in Programarea Pascal, Ed. Microinformatica, Cluj-Napoca, 1995, 252 pagini, ISBN 973-9215-04-1
3. M.Frentiu si altii, Programare Pascal. Programe ilustrative, probleme propuse, pentru elevi si studenti, Ed. Promedia, 1995, 229 pagini, ISBN 973-96862-1-4.
4. M.Frentiu, V.Prejmereanu, Algoritmica si programare, Lito. Univ. Babes-Bolyai, Cluj-Napoca, 1995, 261 pagini.
5. Frentiu, M., I.Lazar, S.Motogna si V.Prejmereanu, vol.I - Elaborarea algoritmilor, 1997, 188 pagini; vol.II - Programare Pascal, 392 pagini; Ed.Universitatii Babes-Bolyai, Cluj-Napoca.
6. M.Frentiu si B.Parv, Elaborarea programelor. Metode si tehnici moderne, Ed.Promedia, Cluj-Napoca, 1994, 217 pag.
7. Kasa Z., Ismerkedes az informatikaval, Editura Dacia, 1983.
8. Kasa, Z., Algoritmusok tervezese, Ed. Studium, Cluj, 1994.
9. Knuth, D., Tratat de programarea calculatoarelor, Ed. Tehnica (Algoritmi fundamentali; Cautare si sortare)
10. Livovschi, L., H.Georgescu, Sinteza si analiza algoritmilor, Editura St. si Enciclopedica, Bucuresti, 1986.
11. Vaduva, I., Baltac, V., V.Florescu, I.Floricica, M.Jitaru, Ingineria programarii, Editura Academiei RSR, Bucuresti, 1985.
Evaluare
La sfarsitul semestrului activitatea se incheie cu examen scris (nota E) si o proba practica la laborator (nota P). Subiectele de examen vor consta din intrebari teoretice din toata materia predata si probleme, dintre cele tratate la curs, seminar si laborator. Studentii vor da o lucrare de control la seminar (prezenta obligatorie). Activitatea de seminar se incheie cu o apreciere a activitatii din timpul anului (nota C, aceasta nota tinand seama de nota de la lucrare si de activitatea de la seminar a studentului). Activitatea de laborator se incheie cu o apreciere a activitatii din timpul anului (nota L), iar documentatiile elaborate pentru lucrarile de laborator vor primi o nota D. Nota finala se calculeaza dupa formula de mai jos, cu conditia ca toate notele sa fie cel putin 5, in caz contrar nu se promoveaza examenul.

Nota finala = 50%E + 15%P + 15%C + 10%L + 10%D.
http://www.cs.ubbcluj.ro/~avescan/
Sectiunea Teaching
Legaturi: Syllabus-urile tuturor disciplinelor
Versiunea in limba engleza a acestei discipline
Versiunea in format rtf a acestei discipline