MIF0001 | Bazele matematice ale calculatoarelor |
Titularii de disciplina |
Lect. Dr. LUPEA Mihaiela, lupeacs.ubbcluj.ro Conf. Dr. ROBU Judit, robucs.ubbcluj.ro Lect. EGRI Edith, egrieditcs.ubbcluj.ro |
Obiective |
Scopul acestui curs este prezentarea bazelor logice ale informaticii: logica propoziţiilor şi logica predicatelor, algebre şi funcţii booleene. Sunt abordate aplicaţii ale logicii în informatică: modelarea rationamentului, demonstrarea automata in aceste sisteme logice, programarea logică, circuite secvenţiale şi combinaţionale. Sunt de asemenea introduse noţiuni de codificarea şi reprezentarea informaţiei în calculator. |
Continutul |
1. Sisteme de numeraţie. Codificarea informaţiei. Reprezentarea interna a numerelor.
- Definiţii, reprezentare şi operaţii (algoritmi de comparare, adunare, înmulţire, împărţire) cu numere într-o bază dată. - Conversiile numerelor întregi şi raţionale între baze de numeraţie folosind metodele: calculul în baza sursă, calculul în baza destinaţie, utilizarea unei baze intermediare. - Exemple pentru bazele particulare: 2,3,4,6,8,16. - Reprezentarea numerelor întregi fără semn, operaţii, noţiunea de depăşire, algoritmi de înmulţire şi împărţire. - Reprezentarea numerelor întregi cu semn folosind codurile: direct, invers şi complementar, operaţii, depăşire. - Reprezentarea numerelor subunitare cu semn, codurile: direct, invers, complementar. - Reprezentarea numerelor reale: virgulă fixă, virgula mobilă (cu mantisa subunitară, cu mantisa supraunitară, simpla precizie si dubla precizie). 2. Logica propoziţiilor si logica predicatelor de ordinul I - Sintaxa, sistemul formal (axiomatic, deductiv) al logicii propoziţiilor/predicatelor, deducţie, teoremă. - Semantica: interpretarea unei formule, model, formulă consistentă (realizabilă), formulă inconsistentă (contradictorie), tautologie, relaţia de consecinţă logică, echivalenţe logice(legile: DeMorgan, absorbţia, comutativitatea, asociativitatea, distributivitatea, idempotenţa). - Forme normale în logica propozitiilor(conjunctivă şi disjunctivă) şi în logica predicatelor(prenexă, Skolem, clauzală). - Proprietăţi ale logicii propoziţiilor/predicatelor: necontradicţia, coerenţa, decidabilitatea/semidecidabilitatea. - Metode de demonstrare a teoremelor în aceste sisteme logice. 3. Algebre booleene, funcţii booleene şi circuite logice. - Algebre booleene: definiţii, proprietăţi, principiul dualităţii. - Funcţii booleene, formele canonice echivalente. - Simplificarea funcţiilor booleene • definiţii: monoame maximale, monoame centrale, factorizare; • metoda diagramelor Veitch-Karnaugh pentru funcţii cu 2-3 variabile; • metoda analitică a lui Mc.Quine • metoda algebrică a lui Moisil. - Circuite logice • definiţii, reprezentarea circuitelor poartă de bază (“and”, “or”, “not”) şi a circuitelor poartă derivate (“xor”, “nand”, “nor”); • exemple de circuite logice existente în partea hard a calculatorului: |
Bibliografie |
1. M. Ben-Ari: Mathematical Logic for Computer Science, Ed. Springer, 2001.
2. C.L. Chang, R.C.T. Lee: Symbolic Logic and Mechanical Theorem Proving, Academic Press, 1973. 3. M. Clarke: Logic for Computer Science, Ed. Eddison-Wesley 1990. 4. J.P. Delahaye: Outils logiques pour l@intelligence artificielle, Ed. Eyrolls, 1986. 5. M. Fitting: First-order logic and Automated Theorem Proving, Ed. Springer Verlag, 1990. 6. M. Lupea, A. Mihis: Logici clasice si circuite logice. Teorie şi exemple, Ed. Albastra, Cluj-Napoca, 2009. 7. Mihaela Malita, Mircea Malita: Bazele Inteligentei Artificiale, Vol. I, Logici propozitionale, Ed. Tehnica, Bucuresti, 1987. 8. L.C. Paulson: Logic and Proof, Univ. Cambridge, 2000, on-line course. 9. M. Possega: Deduction Systems, Inst. of Informatics, 2002, on-line course. 10.D.Tatar: Bazele matematice ale calculatoarelor, edition 1999- library. |
Evaluare |
- Examinarea constă într-o lucrare scrisă cu subiecte din toată materia, nota obţinută
având o pondere de 70% în nota finală. - 30% din nota finală este nota pentru activitatea la seminarii (raspunsuri, prezentari individuale, teste). Observatie: Prezenţa la seminarii este obligatorie în proporţie de 70%. |
Legaturi: | Syllabus-urile tuturor disciplinelor Versiunea in limba engleza a acestei discipline Versiunea in format rtf a acestei discipline |