Image (2)

TEORIA CODĂRII ŞI STOCĂRII INFORMAŢIEI

FISA DISCIPLINEI

 

  • Denumirea programului de master:
  • TEORIA CODARII SI STOCARII INFORMATIEI

Tipul programului de master: complementar, 4 semestre

 

  1. DATE DE IDENTIFICARE

Titlul Disciplinei: Aplicatii ale matematicilor discrete in stiinta calculatoarelor

Titular/i de disciplină: Prof. dr. Mircea Olteanu, Departamentul de Metode si Modele Matematice, Facultatea de Stiinte Aplicate, UPB

Tipul: pregatire de specialitate

Numar ore curs: 2

Numar ore aplicatii: 2

Numarul de puncte de credit: 4

Semestrul: 3

Pachetul: aria curiculara (comuna sau de specialitate)

Preconditii: parcurgerea si/sau promovarea urmatoarelor discipline: Cursurile de matematici din anii 1 , 2. si 3

  1. OBIECTIVELE DISCIPLINEI

     Scopul cursului este de a-i obisnui pe studenti cu gandirea algoritmica si de a le dezvolta abilitati matematice esentiale in stiinta calculatoarelor si ingineria electrica. Studentii sunt pregatiti sa abordeze cursurile viitoare de programare, baze de date, aplicatii software, analiza retelelor si internet. In final, studentii vor fi capabili sa: aplice notiunile si rezultatele de baza din teoria multimilor, relatii, functii si sisteme dinamice discrete; sa aplice notiunile fundamentale din teoria grafurilor; sa inteleaga principiile logicii Booleene, sa aplice formele canonice ale functiilor Booleene in teoria circuitelor digitale si sa resolve ecuatii si inecuatii Booleene; sa aplice inductia matematica la studiul structurilor definite recursiv; sa determine limbajul acceptat de un automat finit; sa aplice echivalenta dintre automatele deterministe cu cele nedeterministe pentru a proiecta un automat finit determinist cu un limbaj acceptat dat;

In cadrul orelor de laborator se vor concepe algoritmi si aplicatii software pentru rezolvarea problemelor studiate la curs.

  • pentru curs ( 10 - 15 randuri )
  • pentru aplicatii ( 5 - 10 randuri )
  1. COMPETENTE SPECIFICE (din spectrul de competente al programului de studii)
  2. CONTINUTUL TEMATIC (SYLLABUS) ( 1 pagină )

CURS

  1. Multimi, relatii si functii (8 ore)
  • Notiuni de teoria multimilor
  • Relatii (reflexivitate, simetrie, antisimetrie, tranzitivitate
  • Functii
  • Cardinali, numarabilitate
  • Inductie si recursivitate
  • Notiuni elementare de teoria sistemelor dinamie discrete (orbite, puncte periodice, functia logistica f(x)=λx(1-x) ).
  1. Algebre Booleene (6 ore)
  • Calcul Boolean (definitii, proprietati, principiul dualitatii, ordine, legile lui De Morgan, algebra Booleene finite)
  • Functii Booleene (forme canonice, functii simple, imaginea unei functii Booleene).
  • Ecuatii si inecuatii Booleene (ecuatii cu una sa mai multe necunoscute, conditii de consistenta, metoda eliminarilor successive)
  1. Notiuni de teoria grafurilor   (6 ore)
  • Grafuri orientate (echivalenta, drumuri, drum minimal, drum Hamiltonian, matricea adiacenta)
  • Grafuri neorientate (cicli, componente conexe , numar ciclomatic).
  1. Alfabet, limbaje,   automate finite, masini Turing (8 ore)
  • Alfabet si limbaje (definitii, operatii cu cuvinte, operatii cu limbaje: concatenare, Kleene-star, expresii regulate).
  • Automate finite deterministe si nedeterministe (definitii, reprezentarea prin grafuri, evolutii deterministe si nedeterministe, limbajul acceptat, automate echivalente).
  • Echivalenta dintre automatele finite deterministe si cele nedeterministe (algoritmul de constructie al unui automat determinist echivalent cu unul nedeterminist dat, aplicatie la proiectarea automatelor deterministe avand un limbaj acceptat dat).

Masini Turing: definitii, proprietati si exemple.

APLICATII

Exercitii legate de notiunile de la curs (in conformitate cu continutul fiecarui capitol)

Algoritmi si aplicatii soft: recursivitate, sisteme dinamice discrete, functii si ecuatii Booleene, grafuri, proiectarea automatelor.

  1. EVALUAREA
  2. Activitatile evaluate si ponderea
    In timpul semestrului studentii vor prezenta 2 aplicatii sofware pentru rezolvarea unor probleme din teoria grafurilor, functii Booleene, automate deterministe.
    La examenul final se vor verifica insusirea notiunilor de baza si felul in care studentii le aplica in exercitii.

 

  1. Cerintele minimale pentru promovare
    • predarea temelor de casa.
    • promovarea laboratorului;
    • obţinerea a 50 % din punctajul total;

 

  1. Calculul notei finale

Prin rotunjirea punctajului final.

  1. REPERE METODOLOGICE (modul de prezentare, materiale, etc.)

Lectiile de curs vor fi expuneri la tabla ale notiunilor si rezultatelor teoretice. Unele vor fi insotite de proiectii video. Studentii au la dispozitie curs tiparit si lectii in forma electronica.

  1. BIBLIOGRAFIA
  2. Arbib, J. Kfoury, R.N. Moll “A basis for theoretical computer science”, Springer Verlag, 1981.

           W.S. Brainerd, I.H. Landweber “Theory of computation”, Wiley Int., 1974

Lewis, Harry R, C. Papadimitriou “Elements of the theory of computation”, Prentice Hall, Eng. Cliffs, N.J. 1981.

H-O Peitgen H. Jurgens, D. Saupe “Chaos and Fractals-new frontiers of science” Springer Verlag, 1992.

  1. Rudeanu "Fundamentals of Boolean functions and equations", North-Holland, London, New York, 1974.

Yu. A Schreider “ Equality, Resemblance and Order”, Mir Publisher, 1974

W.A. Wulf, Mary Shaw, P.N. Hilfinger, I. Flon “Fundamental Structures of Computer Science”, Addison Wesley, 1981

  1. Stanasila , E. Bistriceanu:” Matematica Discreta”, Matrix Rom , 1996.
  2. Olteanu “Lectures on Boolean Functions and Equations”, Ed Printech, 2000.
  3. Olteanu “An Introduction to Relations, Graphs and Finite Automata”, Ed.Printech  

2004.

 

   SEF DE CATEDRA                                                          TITULAR DE DISCIPLINA

Prof. dr. Mircea Olteanu                                                   Prof. dr. Mircea Olteanu