Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
FISA DISCIPLINEI
| MID0001 | Fundamentele programării |
| Titularii de disciplina |
Prof. Dr. PÂRV Bazil, bparv cs.ubbcluj.roLect. Dr. VESCAN Andreea, avescan cs.ubbcluj.roLect. Dr. PREJMEREAN Vasile, per cs.ubbcluj.roAsist. Dr. CZIBULA Istvan Lect. Dr. IONESCU Clara, clara cs.ubbcluj.roLect. Dr. TRÎMBITAS Gabriela, gabitr cs.ubbcluj.roLect. Dr. GURAN Adriana Mihaela, adriana cs.ubbcluj.roLect. Dr. OLAH-GAL Robert, robert.olah-gal 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. |
| Célkitűzések |
|
1. Az algoritmus fogalmának megértése, az algoritmusok ábrázolási módozatainak elsajátítása 2. Az algoritmusok tervezéséhez szükséges készségek kialakítása, a fegyelmezett, logikus és algoritmikus gondolkozás kialakítása 3. A strukturált programozás, a moduláris programtervezés, valamint a top-down és bottom-up programtervezés alapszabályainak megismerése és elsajátítása 4. Adott feladatosztályokhoz tartozó feladatok megoldási algoritmusainak és a szükséges adatszerkezeteknek megismerése és elsajátítása: számok, karakterláncok feldolgozása, sorozatok, kétdimenziós tömbök, keresés, összefésülés, rendezés stb. 5. A megtervezett algoritmusok implementálása egyszeru Pascal programok segítségével 6. A legfontosabb programozási módszerek (visszalépéses keresés, oszd meg és uralkodj, mohó algoritmusok) elsajátítása és a megfelelo feladatmegoldási készség kialakítása 7. Helyes, átlátható programozási stílus kialakítása, a dokumentálás alapszabályainak megismerése |
| Aims |
|
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. |
| Continutul |
|
1. Algoritmi si descrierea lor 2. Subalgoritmi (Pseudocod) 3. Codificarea algoritmilor 4. Faze in viata unui program 5. Corectitudinea algoritmilor 6. Dezvoltarea corecta a algoritmilor din specificatii 7. Metode generale de elaborare a algoritmilor 8. Metoda Top-Down Bottom-Up si Rafinarea în pasi succesivi; Recursivitate. 9. Tipuri Abstracte de Date. 10. Metoda Greedy, Metoda Divide et Impera 11. Metoda Backtracking, Metoda programarii dinamice 12. Metoda Branch and Bound, Metode euristice 13. Complexitatea algoritmilor, Algoritmi de cautare si complexitatea lor. 14. Algoritmi de sortare si complexitatea lor: BubbleSort, SelectSort, InsertionSort, QuickSort, MergeSort. |
| Tartalom |
|
1. eloadás, szeminárium és labor: (Az alábbi oldalszámok Ionescu Klára, Bevezetés az algoritmikába címu jegyzetébol valók.) A számítógépes feladatmegoldás lépései 1.1. A programozói tevékenység 13 1.2. A feladatmegoldás lépései számítógépes környezetben 14 1.3. Alkalmazások minoségi szempontjai 16 Az algoritmusok ábrázolása 17 2.1. Algoritmusok 17 2.1.1. Az algoritmus fogalma 17 2.1.2. Az algoritmusok leírásánál használt elemek 19 2.2. Algoritmusok ábrázolása folyamatábrák és pszeudokód nyelvek segítségével 24 2. eloadás, szeminárium és labor: 2.3. A strukturált programozás alapelvei 27 2.3.1. Lineáris struktúrák 28 2.3.2. Elágazási struktúrák 28 2.3.3. Ismétlo struktúrák 29 2.3.4. Az alapstruktúrák jelölése pszeudokódban 33 2.3.5. Egyszeru alapszabályok 37 2.4. A feladatok számítógépes megoldásához fuzodo általános kérdések 38 2.4.1. Algoritmusok helyessége 39 2.4.2. Az algoritmus végrehajtásához szükséges ido 42 2.4.3. Az algoritmus által feldolgozott adatok számára szükséges memória mérete 47 2.4.4. Algoritmusok egyszerusége 47 2.4.5. Algoritmusok optimalitása 47 2.4.6. Algoritmusok létezése 49 2.5. Szemináriumon és laboron: feladatok (felcserélés, maximumérték, elnökválasztás stb.) 49 3. eloadás, szeminárium és labor: Lépések finomítása 57 3.1. Bevezetés 57 3.2. Megoldott feladatok: Eukleidész algoritmusa, prímszámok, Fibonacci-számok, háromszög, fordított szám, törzstényezok, konverzió, gyors hatványozás 57 3.3. Szemináriumon és laboron: kituzött feladatok 79 3.-4. eloadás, szeminárium és labor: Programozási tételek 83 4.1. Bevezetés 83 4.2. Egyszeru programozási tételek 83 4.2.1. Összeg és szorzat 83 4.2.2. Döntés 86 4.2.3. Kiválasztás 89 4.2.4. Szekvenciális (lineáris) keresés 90 4.2.5. Megszámlálás 94 4.2.6. Minimum- és maximumkiválasztás 95 4.2.7. Kiválogatás 98 4.3. Összetett programozási tételek 100 4.3.1. Szétválogatás 100 4.3.2. Sorozat halmazzá alakítása 104 4.3.3. Keresztmetszet 105 4.3.4. Egyesítés 107 4.3.5. Összefésülés 108 4.4. Szemináriumon és laboron: kituzött feladatok 111 5. eloadás, szeminárium és labor: Alprogramok 127 5.1. Bevezetés 127 5.2. Algoritmusok és programok fejlesztési módozatai 129 5.2.1. A top-down típusú (fentrol lefele) programozás 129 5.2.2. A bottom-up (lentrol felfele) programozás 129 5.2.3. Moduláris algoritmustervezés 130 5.3. A moduláris programozás alapszabályai 134 5.3.1. Moduláris dekompozíció 134 5.3.2. Moduláris kompozíció 135 5.3.3. Modulok tulajdonságai 135 5.3.4. A modularitás alapelvei 135 5.4. Algoritmusok tesztelése 136 5.4.1. A fekete doboz módszere 136 5.4.2. Az átlátszó doboz módszere 137 5.5. Megoldott feladatok: polinom értéke, polinomok összege és szorzata, determináns 138 5.6. Szemináriumon és laboron: kituzött feladatok 144 6. eloadás, szeminárium és labor: Rendezési algoritmusok 151 6.1. Bevezetés 151 6.2. Összehasonlításos rendezési módszerek 151 6.2.1. Buborékrendezés (Bubble-sort) 151 6.2.2. Egyszeru felcseréléses rendezés 155 6.2.3. Válogatásos rendezés 155 6.2.4. Minimum/maximum kiválasztásra épülo rendezés 157 6.2.5. Beszúró rendezés 157 6.3. Rendezések lineáris idoben 158 6.3.1. Leszámláló rendezés (ládarendezés, Binsort) 159 6.3.2. Számjegyes rendezés (Radix-sort) 159 6.4. Szemináriumon és laboron: részleges vizsga az eddig tanultakból (írásbeli és számítógépen) 7. eloadás, szeminárium és labor: Rekurzió 163 7.1. Bevezetés 163 7.2. Közvetlen rekurzió 165 7.3. Megoldott feladatok: egy szó betuinek megfordítása, szavak sorrendjének megfordítása, faktoriális, legnagyobb közös osztó, számjegyösszeg, Descartes-szorzat, k elemu részhalmazok, konverzió, Fibonacci-sorozat, a {0, 1, 2} halmaz elemeivel generált sorozatok, az {1, 2, ..., n} halmaz valamennyi részhalmaza, partíciók, halmazpartíciók, kamatos kamat 168 7.4. Szemináriumon és laboron: kituzött feladatok 185 8-9-10. eloadás, szeminárium és labor: A visszalépéses keresés módszere (backtracking) 187 8.1. Bevezetés 187 8.2. A visszalépéses keresés általános bemutatása 188 8.2.1. Iteratív algoritmus 189 8.2.2. Rekurzív algoritmus 190 8.2.3. Megoldott feladatok: 8 királyno a sakktáblán, variációk, zárójelek, legrövidebb utak, játékok, szürjektív függvények 192 8.3. A visszalépéses keresés bovítése 204 8.3.1. Megoldott feladatok: S pénzösszeg kifizetése, összegkifizetés, minimum számú bankjeggyel 206 8.4. Visszalépéses keresés a síkban 210 8.4.1. Megoldott feladatok, labirintus, fénykép, legnagyobb méretu tárgyak 210 8.5. Szemináriumon és laboron: kituzött feladatok 216 11-12. eloadás, szeminárium és labor: Az oszd meg és uralkodj módszer (divide et impera) 223 9.1. Bevezetés 223 9.2. Az oszd meg és uralkodj módszer általános bemutatása 223 9.3. Megoldott feladatok: szorzat, minimumszámolás, hatványozás, bináris keresés, összefésülésen alapuló rendezés, gyorsrendezés, Hanoi tornyok, úszómedence 224 9.4. Szemináriumon és laboron: kituzött feladatok 245 13-14. eloadás, szeminárium és labor: Mohó algoritmusok (greedy módszer) 249 10.1. Bevezetés 249 10.2. A mohó algoritmus általános bemutatása 250 10.3. Megoldott feladatok: összeg, az átlagos várakozási ido minimalizálása, buszmegállók, autó bérbeadása, hátizsák, minimális feszítofák (Kruskal és Prim), minimális hosszúságú utak (Dijkstra algoritmusa) 252 10.4. Heurisztikus mohó algoritmusok 276 10.4.1. Megoldott feladatok: utazóügynök, gráfszínezés, összegkifizetés legkevesebb számú bankjeggyel 276 10.5. Szemináriumon és laboron: kituzött feladatok 282 |
| Content |
|
Schedule of courses Week 1: Algorithms and their description [1, ch. 1] Week 2: Subalgorithms (Pseudocode) [1, ch. 1] Week 3: Simple Pascal programs [1, ch. 1] Week 4: Steps in the life of a program. Consequences. Programs testing [1, ch. 3] Week 5: General methods to elaborate algorithms: top-down, stepwise refinement, modular programming, structured programming. Important rules in programming. Style [1, ch. 4] Week 6: Abstract data types (part I) [1, ch. 5] Week 7: Abstract data types (part II) [1, ch. 5] Week 8: Algorithms complexity [1, ch. 7] Week 9: Recursion. Backtracking [1, ch. 6], [3, ch. 3, 4] Week 10: Division method. Greedy method. [1, ch. 6] Week 11:. Dynamic programming. Branch and Bound [1, ch. 6] Week 12: Search algorithms and their complexity [1, ch. 7] Week 13: Sort algorithms and their complexity [1, ch. 7] Week 14: Algorithms correctness. Correct algorithm development from specifications [1, ch. 2] Schedule of seminars Week 1: Subalgorithms (Pseudocode) Week 2: Subalgorithms (Pseudocode) Week 3: Coding Pseudocode algorithms in Pascal Week 4: Pascal programs with subprograms Week 5: Pascal programs with subprograms Week 6: Top-down design Week 7: Graded paper (include correct development of algorithms from specifications and writing simple subalgorithms) Week 8: Specification, design, implementation and use of abstract data types Week 9: Specification, design, implementation and use of abstract data types Week 10: Algorithms complexity Week 11: Recursion. Backtracking. Complexities Week 12: Programming techniques. Complexities Week 13: Preparation for the practical test Week 14: Preparation for the written exam Schedule of labs The week number indicates when the lab theme has been given; the lab documents are due one week later and the lab programs are due two weeks later. Week 1: Algorithms and their description Week 2: Subalgorithms (Pseudocode) Week 3: Coding Pseudocode algorithms in Pascal Week 4: General methods to create algorithms Week 5, 6: Top-down method and Stepwise refinement Week 7: Testing. Text files. Week 8, 9: Abstract data types Week 10: Backtracking method Week 11: Algorithms complexity Week 12, 13: Lab delivery time (see note above) Week 14: Practical test |
| 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. |
| 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. Webpage: http://www.cs.ubbcluj.ro/~per/Fp.html |
| Felmérés |
|
1. A házi feladatokat minden hallgatónak egyénileg oldja meg, kérésre el kell tudja magyarázni, módosítani. A házi feladatokra minden hallgató kap két érdemjegyet: egyet a részleges vizsga elott és egyet a félév végén (H1, H2). 2. A szemináriumi aktív részvételért „bónusz“ pontokat lehet szerezni. 3. A 7. eloadás után részleges vizsga (írásbeli (Í) és géptermi (L)) lesz. A részleges vizsga jegye RV = [(Í + L + H1)/3]. 4. A szesszióban írásbeli és géptermi vizsga lesz. A téli szesszió jegye (TV) = [(Í + L + H2)/3]. A végleges vizsga jegye: VV = [(RV + TV)/2]. 5. Átlagok csak átmeno érdemjegyek esetében számolandók. 6. Értékelési kritériumok: a feladatok megoldásainak a tanított mintákkal azonos minoségueknek kell lenniük (hatékonyság, felhasznált memória, stílus, átláthatóság, paraméterezés, dokumentáltság stb.). |
| Assessment |
|
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 students will take a graded paper (G) at the seminar. The laboratory activity 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 = 50%E + 15%P + 15%G + 10%L + 10%D. Further information regarding the evaluation process and the course requirements can be found following the URL: http://www.cs.ubbcluj.ro/~adriana/Teaching.html or in the local network following the path \\Win\labor\Engleza\An1\FP\Requirements |