Universitatea "Babeş-Bolyai" din Cluj-Napoca

Facultatea de Matematică şi Informatică
FISA DISCIPLINEI

Algoritmică Algorithms
Cod
Semes-
trul
Ore: C+S+L
Credite
Tipul
Sectia
MI001
1
2+2+2
7
obligatorie
Matematică-Informatică
(Mathematics-Computer Science)
MI001
1
2+2+2
7
obligatorie
Matematici Aplicate
(Applied Mathematics)
MI001
1
2+2+2
8
obligatorie
Tehnologie Informatică
(College of Computer Technology)
MI001
1
2+2+2
7
obligatorie
Matematica Economica
(Mathematics Economics)
MI001
1
2+2+2
7
obligatorie
Informatică
(Computer Science)
MI001
1
2+2+2
7
obligatorie
Matematică
(Mathematics)
Cadre didactice indrumatoare Teaching Staff in Charge
Prof. Dr. FRENŢIU Militon, mfrentiu@cs.ubbcluj.ro
Lect. IONESCU Clara, clara@cs.ubbcluj.ro
Lect. Dr. PREJMEREAN Vasile, per@cs.ubbcluj.ro
Obiective Aims
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.
1. To understand what an algorithm is. To learn PSEUDOCOD as a language for designing algorithms.
2. To gain skils of designing algorithms.
3. To write algorithms for some classes of problems: operations on vectors, matrices, and polynoms; solving linear equations and systems; sorting and searching.
4. To learn Pascal, and to get used to Pascal programming, running, testing, and debugging programs.
5. To acquire and improve the programming style.
Continut
1. Algoritmi si descrierea lor. Notiunea de algoritm, Exemple; Limbaje de descriere a algoritmilor; Limbajul Pseudocod. Subalgoritmi.
2. Clase de algoritmi. Algoritmi pentru generarea unor siruri si matrice; Algoritmi din combinatorica (generari de permutari, combinari, etc); Algoritmi iterativi pentru rezolvarea ecuatiilor si sistemelor; Algoritmi pentru calculul matricial; Algoritmi de cautare; Algoritmi de sortare (interna si externa). Algoritmi de interclasare.
3. Programe Pascal simple. Structura unui program Pascal. constante, variabile, tipuri simple de date, expresii. Declaratii Pascal. Instructiunile limbajului Pascal. Subprograme Pascal. Sintaxa si semantica; Variabile locale si globale; Recursivitate.
4. Verificarea algoritmilor (faze in viata unui program; testare si depanare; demonstrarea corectitudinii; validarea programelor; complexitate).
5. Corectitudinea programelor. Metoda lui Floyd de demonstrare a corectitudinii. Obtinerea programelor corecte din specificatii. Reguli de programare.
5. Metode de proiectare a algoritmilor: Programarea descendenta (top-down, stepwise refinement, divide et impera); Programarea modulara; Programarea structurata; Obtinerea algoritmilor din specificatii; Metode speciale de rezolvare a problemelor. Backtracking.
Bibliografie
1. M.Frentiu si altii, Manualul incepatorului in Programarea Pascal, Ed. Microinformatica, Cluj-Napoca, 1995, 252 pagini, ISBN 973-9215-04-1.
2. Frentiu, M., I.Lazar, Bazele programarii. Proiectarea algoritmilor, 2000, 184 pagini, Ed.Univ. Petru Maior, Targu-Mures.
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.
5. M.Frentiu si B.Parv, Elaborarea programelor. Metode si tehnici moderne, Ed.Promedia, Cluj-Napoca, 1994, 217 pag.
6. Kasa Z., Ismerkedes az informatikaval, Editura Dacia, 1983.
7. Kasa, Z., Algoritmusok tervezese, Ed. Studium, Cluj, 1994.
8. Knuth, D., Tratat de programarea calculatoarelor, Ed. Tehnica (Algoritmi fundamentali; Cautare si sortare)
9. Livovschi, L., H.Georgescu, Sinteza si analiza algoritmilor, Editura St. si Enciclopedica, Bucuresti, 1986.
10. Vaduva, I., Baltac, V., V.Florescu, I.Floricica, M.Jitaru, Ingineria programarii, Editura Academiei RSR, Bucuresti, 1985.
Evaluare Assessment
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. 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 = (E+P+L+D)/4.
Knowledge evaluation will take into account both the theoretical and the practical knowledge, and also, the abilities to use the computer for solving concrete problems. The laboratory activity consists of designing programs (as homework which is controlled by the assistants) and running them. Attention will be given to the way the students design, implement, and document their programs. At the end of term the activity is followed by an exam consisting of two parts: a written exam, and a practical one. The first one must verify the theoretical knowledge and the capacity to design and implement correct Pascal programs, and a first grade (E)is given for this. The practical examination consists in designing, testing and debugging a Pascal program, for which a second grade (P) is given.
The laboratory actiovity of students will be graded by a third mark (L), and the documentation written during the term will received the fourth grade (D). The final mark is the average of these four gradess, but only if they are at least 5, otherwise the exam is not given. Therefore, final grade = (E+P+L+D)/4.