Programa cursului

Pentru studentii sectiei fara frecventa FCIM

1. INTRODUCERE. SISTEME ALGEBRICE.

Mulţimi. Noţiuni generale. Mulţimi vagi (fuzzy). Operaţii cu mulţimi. Demonstrarea echivalenţei cu ajutorul incluziunilor. Vectori şi produs cartezian. Corespondenţe şi funcţii. Relaţii şi proprietăţile lor. Operaţii şi algebre. Proprietăţile operaţiilor. Modele si sisteme algebrice. Algebra relaţiilor. Baze de date relaţionale.

2. ELEMENTE DE LOGICĂ MATEMATICĂ.

Funcţiile algebrei logicii. Tabelul de adevar a functiei logice. Functii logice de 2 variabile: conjunctia, disjunctia, suma modulo doi, implicatia, echivalenta, sageata lui Pearce, semnullui Sheffer. Transformări echivalente şi decompoziţia funcţiilor booleene. Forme canonice. Alte forme de reprezentare a funcţiilor booleene. Sisteme complete de funcţii booleene. Forme disjunctive (conjunctive) normale perfecte Minimizarea funcţiilor booleene (metoda Quine, Quine- McKluskey, Karnaugh). Diagrama temporara.Implimentarea schemelor logice in bazele: ŞI-NU, SAU-NU.Logica enunţurilor. Conectori logici şi formule. Interpretarea formulelor în logica enunţurilor. Forme normale şi consecinţe logice. Aplicaţii ale logicii enunţurilor. Logica de ordinul unu. Noţiuni de bază. Interpretarea formulelor în logica de ordinul unu. Forma normală Prenex. Aplicaţii ale logicii de ordinul unu. Logica continuală şi hibridă. Logica fuzzy. Logica matematică şi inteligenţa artificială.

3. GRAFURI

Noţiuni generale. Definiţia grafului. Număr cociclomatic şi număr ciclomatic. Număr cromatic. Grafuri planare. Arbori. Metode de reprezentare a grafului. Matricea de incidenţă. Matricea de adiacenţă. Lista de adiacenţă şi lista de incidenţă. Algoritmi pe grafuri. Căutare în adâncime. Algoritmul de căutare în lărgime. Noţiune de graf de acoperire. Algoritmul de determinare a grafului de acoperire. Noţiune de drum minim. Algoritmul lui Ford pentru determinarea drumului minim. Algoritmul Bell man – Calaba. Reţele de transport. Noţiuni generale. Algoritmul Ford-Fulkerson de determinare a fluxului maxim.

4. ALGORITMI ŞI MODELE DE ALGORITMI.

Formalizarea noţiunii de algoritm. Maşini Turing. Componenţa şi principiul de funcţionare. Operaţii cu maşini Turing. Maşina Turing universală. Problema opririi. Funcţii recursive ca model algoritmic. Teza lui Church. Maşinile Turing şi funcţiile recursive. Calculabilitate şi rezolvabilitate.

PROBLEMELE PENTRU LUCRAEA DE CONTROL.

PROBLEMA I.

De determinat multimile nevide A, B, C, care simultan satisfac conditiile:

Varianta1. 1) A È B ÈC = {1,2,3,4,5}; 2) A ÇC = {4};3) C \ A= {1,2,3};4) B \A = {1};

5)3Ï A È B;6) B D C= {2,3,5};

Varianta2. 1) A ´{1,2,4}Í{1,2,3,5}´B; 2){1,2,3}´BÍ A ´{1,2,4,5};3)(5,3)Ï A ´B;

4)(1,5)Î A ´B; 5) A DB = {3,4,5};

Varianta3.1) A È B= {1,2,3,4,5};2) A Ç B≠Ø; 3)A \ B= {1,2};4) B \ A= {5}.

Varianta4. 1) A Ç C= {1,2,5}; 2) A D B= {1,5,4,6}; 3) B È C= {1,2,4,5,6}; 4) C \ A= {6};

Varianta5. 1) A È B ÈC = {1,2,3,4,5}; 2) B ÇC = {4};3) C \B = {1,2,3};4) A \B = {1};

5)3Ï A È B;6) A D C= {5,2,3};

Varianta6. 1) C´{1,2,4}Í{1,2,3,5}´B; 2){1,2,3}´BÍC´{1,2,4,5};3)(5,3)ÏC´B;

4)(1,5)ÎC´B; 5)CDB = {3,4,5};

Varianta7. 1) A ÈC = {1,2,3,4,5};2) A ÇC ≠Ø; 3)A \C = {1,2};4)C\ A= {5}

Varianta8. B Ç C= {1,2,5}; 2)BDA = {6,5,4,1}; 3) A È C= {1,2,4,5,6}; 4) C \B = {6};

Varianta9. C È B ÈA = {1,2,3,4,5}; 2) C ÇB = {4};3) B \C = {3,1,2};4) A \C = {1};

5)3Ï A ÈC;6) B DA = {5,2,3};

Varianta0. 1) {1,2,4}´ A ÍC ´{1,2,3,5}; 2){1,2,3}´CÍ A ´{1,2,4,5};3)(5,3)Ï A ´C;

4)(1,5)Î A ´C; 5) A DC = {4,3,4};

PROBLEMA II.

De verificat egalitatile din tabelul 1.

Tab 1.

Nr. variantei	Egalitatea
	(AÈB)´C=(A´C)È(B´C)
	(AÇB)´C=(A´C)Ç(B´C)
	(A\B)\C=A\(BÈC)
	A\(B\C)=(A\B)È(AÇC)
	(A´C)\(B´C)=(A\B)´C
	(A\B)È(AÇC)=A\(B\C)
	(A´C)È(B´C)=(AÈB)´C
	EÈ(F´G)=(EÈF)´(EÈG)
	E´(FÇG)=(E´F)Ç(E´G)
	EÈ(FÇG)=(EÈF)Ç(EÈG)

Дата добавления: 2015-10-26