Institutul de Tehnologie MLR

STRUCTURI DISCRETE
II B. TEHNOLOGIE - I SEMESTRU

Codul cursului Category Ore / Săptămână Credits Maximum Marks

L T P C CIE A VEDEATotal
A4CS03 PCC
3 1 - 4 30 70 100
OBIECTIVELE CURSULUI
Cursul ar trebui să permită studenț ilor să:
1. Pentru a ajuta studenții să înțeleagă structuri matematice discrete și continue
2. A transmite conceptele de bază ale relațiilor și funcțiilor
3. Pentru a facilita studenților aplicarea principiilor Relațiilor de Recurență pentru a calcula generatoare
funcții și rezolvațiile relațiilor de recurență
4. A dobândi cunoștințe în teoria grafurilor

COURSE OUTCOMES:
La sfârș itul cursului, studentul va fi capabil să
1. Aplică cunoștințele despre structuri matematice discrete și continue.
2. Rezolvați diverse probleme privind relațiile și funcțiile.
3. Aplică principiile Relațiilor de Recurență pentru a genera funcții și a rezolva diverse
probleme cu acesta.
4. Rezolvați probleme folosind cunoștințele din teoria grafurilor.
UNITATEA-ILOGICĂ MATEMATICĂ Classes: 11
Statements and notations, Connectives, Well formed formulas, Truth Tables, Tautology, Equivalence
{"implication":"implicație","Normal forms":"Forme normale","Logical Inference":"Inferență logicală","Rules of inference":"Reguli de inferență","Direct Method":"Metoda directă","Direct Method using":"Metoda directă folosind"}
CP (Dovada Condiționată), Consistență, Dovada prin contradicție, Dovedirea automată a teoremelor. Quantificatori,
Quantificatori universali. Predicate: Logica predicativă, Variabile libere și legate.
UNITATEA-IIRELATII Classes: 16
Introducere în teoria mulțimilor, Relații, Proprietăți ale relațiilor binare, Relație de echivalență, Transitivitate
închiderea, Compatibilitatea și relațiile de ordonare parțială, Reticuluri, diagramă Hasse. Funcții: inversă
Function , Composition of functions, Recursive Functions
UNITATEA-III COMBINATORICĂ ELEMENTARĂ Classes: 12
Baza de numărare, Combinații și Permutări, Enumerarea combinațiilor și permutărilor
Enumerarea combinațiilor și permutărilor cu repetiții, Enumerarea permutărilor cu
Repetiții constrânse, coeficienți binomiali, teoremele binomiale și multinomiale, Principiile
Excludere Incluzivă, principiile cuibului de porumbei și aplicațiile acestora.
UNITATEA-IV RELATIE DE RECURENTA Classes: 11
Funcții generatoare, Funcția secvențelor, Calcularea coeficientului funcției generatoare
Relații de recurență, Rezolvarea relațiilor de recurență prin substituție și Funcții generatoare, The
metoda rădăcinilor caracteristice, Soluția Relației de Recurs Inomogene.
UNITATEA VGRAFURI Classes: 10
Concepte de bază, Izomorfism și subgrafuri, Arbori și proprietățile lor, Arbori de acoperire-
DFS, BFS, Arbori Minimali de Conectare
grafuri și circuite Euler, Grafuri Hamiltoniene, numărul cromatic.

TEXT BOOKS:

1. T1. Matematica discretă pentru informaticieni și matematicieni, J.L. Mott, A. Kandel

[Link] PHI
2. Structuri Matematice Discrete cu Aplicații în Știința Calculatoarelor, JP Tremblay
R Manohar
Cărț i de referinț ă:
1. R1. Logică și Matematică Discretă, Grass Man & Trembley, Pearson Education.

[Link]- CSE Reguli Academice ș i Syllabus MLR18 Page 65

 Institutul de Tehnologie MLR

STRUCTURI DE DATE
Anul II Semestrul I

Course Code Categorie Ore / Săptămână Credits Maximum Marks

L T P C CIE VEZI Total

A4CS04 PCC
3 1 - 4 30 70 100

Obiectivele cursului:
1. Transmiteți conceptele de bază ale structurilor de date și algoritmilor.
2. Înțelegeți conceptele listelor legate și aplicațiile lor.
3. Înțelegeți conceptele de bază despre stive, cozi și aplicațiile acestora.
4. Înțelegeți conceptele de bază ale copacilor, graficelor și aplicațiile lor.
5. Permiteți-le să scrie algoritmi pentru sortare, căutare și hashing.
6. Utilizați structuri de date avansate, cum ar fi arborii B, arborii AVL etc., pentru rezolvarea eficientă a problemelor.

Course Outcomes
La sfârș itul cursului, studentul va putea să:

1. Evaluează algoritmii în termenii complexității de timp și memorie.

2. Formulați soluții noi pentru probleme sau îmbunătățiți codul existent folosind structuri de date și
algoritmi.
3. Implementați structuri de date de bază, cum ar fi tablouri, liste legate, stive și cozi.
4. Rezolvarea problemelor care implică grafuri, arbori și grămezi
5. Apply Algorithms for solving problems like sorting, searching, and hashing.
6. Implementați structuri de date avansate, cum ar fi arbori B, arbori roșu-negru și arbori AVL

UNITATEA-I INTRODUCERE ÎN STRUCTURILE DE DATE Classes: 12

Concepte de bază - Specificaț ia algoritmului - Introducere, Algoritmi recursivi, Abstracț ia datelor
Analiza performanței - complexitatea în timp și complexitatea în spațiu, Notația asimptotică - Big O, Omega și
Notaț ii Theta, Introducere în structuri de date liniare ș i neliniare - Liste legate simplu -
Operațiuni-Inserare, Ștergere, Concatenare liste simplu legate, Liste circulare - Operațiuni pentru
Listele legate circular, Listele legate duble - Operații - Inserare, Ștergere. Reprezentarea unui singur
array-uri bidimensionale, matrice sparse - reprezentări de array și legate.

UNITATEA-IISTIVURI Ș I COZI Clase: 10

Stive - ADT stivă, definiț ie, operaț ii, implementări pe baza de array ș i listă îmbinată în C, aplicaț ii - infix
conversia topostfix, evaluarea expresiei Postfix, implementarea recursiei,
Cozi - ADT-ul Cozii, definiț ie ș i operaț ii, implementări în C, array ș i legate, Circular
cozi - Operațiuni de inserare și ștergere, Dequeue (coada de două capete) ADT, array și legat
implementări în C.

UNITATEA-IIICOPACI Ș I GRAFURI Clase: 14

TreesTerminology, Representation of Trees, Binary tree ADT, Properties of Binary Trees,Binary
Reprezentări arbore - reprezentări prin array și legate, parcurgeri ale arborilor binari, arbori binari cu fir.
Coada Prioritară Maximă - ADT - implementare - Max Heap - Definiție, Inserare într-un Max Heap, Ștergere
dintr-un Max Heap. Grafuri, Introducere, Definiție, Terminologie, GraphADT, Reprezentări Grafice -
Matrice de adiacență, Liste de adiacență, Parcursuri ale grafurilor - DFS și BFS.

UNIT-IV CĂUTARE Ș I SORTARE Clase: 12

Căutare - Căutare liniară, Căutare binară, Hashing static - Introducere, tabele hash, funcț ii hash
Gestionarea depășirii.

Sortare - Sortare prin inserț ie, Sortare prin selecț ie, Sortare prin radix, Sortare rapidă, Sortare prin combinare, Sortare prin heap, Compararea

Regulile academice ș i syllabus-ul [Link]- CSE MLR18 Page 66

 Institutul de Tehnologie MLR

Metode de sortare.

UNITATEA-VARBORE BINARY DE CĂUTARE Classes: 12

Arbori de căutare - Arbori binari de căutare, Definiț ie, Operaț ii - Căutare, Inserare ș i Ș tergere, AVL
Copaci - Definiție și Exemple, Inserare într-un Arbore AVL, B-Arbori, Definiție, B-Arbore de ordin m
operațiuni - Inserare și Căutare, Introducere în Arborii Roșu-Negru și Arborii Splay (Tratare elementară -
doar Definiții și Exemple), Compararea Arborilor de Căutare.
Algoritmul de potrivire a modelului - Algoritmul Knuth-Morris-Pratt, Tries (doar exemple).

Text Books:

Ș tiinț a Presa.
2. Fundamentele structurilor de date în C, ediț ia a 2-a, [Link], [Link] ș i Susan Anderson-Freed
Universi es Press.
Cărț i de referinț ă:

Weiss, Compania de Publicații Addison-Wesley

Referinț e web:

[Link]://[Link]/tutorials/learn-data-structures-algorithms
[Link]://[Link]/fundamentals-of-algorithms/
[Link]://[Link]/introduction-to-algorithms-and-data-structures-in-c/
[Link]://[Link]
Cărț i electronice:

[Link]://[Link]/[Link]
[Link]://[Link]/[Link]
[Link]://[Link]/[Link]

Curs MOOC

[Link]://[Link]/specializations/data-structures-algorithms
[Link]://[Link]/noc16_cs06/preview

[Link]- CSE Regulamente Academice ș i Silabe MLR18 Page 67