Universitatea "Babes-Bolyai" Cluj-Napoca
Facultatea de Matematica si Informatica
FISA DISCIPLINEI
| Fundamentele programarii |
trul |
||||
| Cadre didactice indrumatoare |
Prof. Dr. POP Horia Florin, hfpop cs.ubbcluj.roConf. Dr. SERBAN Gabriela, gabis cs.ubbcluj.roLect. Dr. PREJMEREAN Vasile, per cs.ubbcluj.roLect. Dr. IONESCU Clara, clara cs.ubbcluj.roLect. Dr. LUPSA Dana, davram cs.ubbcluj.roAsist. TARTA Adriana Mihaela, adriana cs.ubbcluj.roAsist. MIHIS Andreea Diana, mihis cs.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. |
| Continut |
|
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 o problema, dintre cele tratate la curs, seminar si laborator. Studentii vor da o lucrare de control la seminar (nota C). 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 este media aritmetica a celor patru note mentionate mai sus, cu conditia ca toate notele sa fie cel putin 5, in caz contrar nu se promoveaza examenul.
Deci nota finala = 50%E + 15%P + 15%C + 10%L + 10%D. |
| Legaturi: | Syllabus-urile tuturor disciplinelor Versiunea in limba engleza a acestei discipline Versiunea in format rtf a acestei discipline |