Descriere
Sumar
Despre autori
Ediția a doua revăzută și adăugită.
Lucrarea este concepută ca suport de curs pentru studenții informaticieni. Predat de autor la School of Electrical Engineering and Computer Science, University of Central Florida, acesta prezintă elemente de bază necesare înțelegerii unor capitole fundamentale de informatică, împreună cu aplicații concrete în domenii precum: teoria codurilor și compresia datelor, teoria codurilor detectoare și corectoare de erori, criptografie și securitatea informației, semantica limbajelor de programare, analiza programelor, teoria tipurilor de date.
Prefață;
Prefață la ediția a II-a;
1. Concepte fundamentale:
1.1 Mulțimi;
1.1.1 Ce este o mulțime?;
1.1.2 Operații cu mulțimi;
1.1.3 Axioma infinitului. Numere naturale:
1.1.3.1 Axioma infinitului;
1.1.3.2 Numere naturale;
1.1.3.3 Ordonare și inducție;
1.1.3.4 Mulțimi finite și infinite;
1.1.3.5 Recursie;
1.2 Relații și funcții:
1.2.1 Relații;
1.2.2 Relații de echivalență;
1.2.3 Funcții și operații;
1.2.4 Familii indexate de mulțimi;
1.2.5 Axioma alegerii;
1.2.6 Relații de ordine;
1.3 Închideri:
1.3.1 Închideri. Inducție structurală;
1.3.2 Închideri ale unei relații binare;
1.3.3 Definiții inductive/recursive;
1.4 Sisteme relaționale și algebre universale:
1.4.1 Sisteme relaționale;
1.4.2 Mulțimi parțial ordonate;
1.4.2.1 Concepte de bază;
1.4.2.2 Dualitate;
1.4.2.3 Proprietăți de bază ale supremumului și infimumului;
1.4.2.4 Construcții de mpo;
1.4.3 Latici:
1.4.3.1 Laticea ca mulțime parțial ordonată;
1.4.3.2 Laticea ca structură algebrica;
1.4.3.3 Latici distributive și modulare;
1.4.4 Algebre universale dintr-un punct de vedere elementar:
1.4.4.1 Algebre;
1.4.4.2 Subalgebre. Ordin;
1.4.4.3 Homomorsme și congruențe;
1.4.5 Algebre booleene;
1.5 Numere ordinale și cardinale:
1.5.1 Mulțimi bine ordonate;
1.5.2 Numere ordinale;
1.5.3 Axioma înlocuirii. Inducție și recursie pe ordinali;
1.5.4 Principiul bunei ordonări și alte propoziții echivalente;
Axiomei alegerii;
1.5.5 Numere cardinale;
2. Elemente de teoria numerelor:
2.1 Divizibilitate. Numere prime;
2.2 Cel mai mare divizor comun;
2.3 Congruențe;
2.4 Funcția lui Euler;
2.5 Ecuații congruențiale;
2.6 Teorema chineză a resturilor;
2.7 Reziduozitate pătratică:
2.7.1 Congruențe pătratice;
2.7.2 Reziduuri pătratice și simbolul Legendre;
2.7.3 Simbolul Jacobi;
2.8 Complexitatea operațiilor:
2.8.1 Ordine de mărime;
2.8.2 Timpul de execuție al unui algoritm;
3. Semigrupuri și monoizi:
3.1 Definiții și exemple;
3.2 Relațiile lui Green;
3.3 Clase remarcabile de semigrupuri și monoizi:
3.3.1 Monoizi de cuvinte;
3.3.2 Semigrupuri de transformări;
3.3.3 Semigrupuri și monoizi ciclici;
3.3.4 Semigrupuri regulate și inverse;
3.4 Semigrupuri și monoizi liberi:
3.4.1 Definiții. Exemple. Proprietăți de bază;
3.4.2 Rezultate de caracterizare;
3.4.3 Submonoizi liberi;
3.5 Aplicații: coduri de lungime variabilă:
3.5.1 Definiții. Exemple. Proprietăți de bază;
3.5.2 Rezultate de caracterizare;
3.5.3 Măsura unui cod;
3.5.4 Coduri Huffman;
3.5.5 Entropie. Limita compresiei;
4. Grupuri:
4.1 Definiții. Exemple. Proprietăți de bază;
4.2 Subgrupuri. Teorema lui Lagrange;
4.3 Subgrupuri normale;
4.4 Grupuri ciclice;
4.5 Grupul Z*;
4.6 Problema logaritmului discret;
4.7 Aplicații: criptografie cu chei publice:
4.7.1 Introducere în criptografie;
4.7.2 Criptosistemul RSA:
4.7.2.1 Descrierea criptosistemului;
4.7.2.2 Criptanaliza RSA;
4.7.3 Semnături digitale:
4.7.3.1 Introducere;
4.7.3.2 Semnătura ElGamal;
4.7.3.3 Semnătura DSS;
5. Inele și corpuri:
5.1 Definiții. Exemple. Proprietăți de bază;
5.2 Homomorfisme, subinele și ideale;
5.3 Caracteristica unui inel;
5.4 Inele de polinoame:
5.4.1 Polinoame. Proprietăți de bază;
5.4.2 Extensii, elemente algebrice, descompuneri;
5.5 Corpuri finite;
5.6 Aplicații: criptosistemul Rijndael;
6. Spații vectoriale:
6.1 Definiții. Exemple. Proprietăți de bază;
6.2 Bază și dimensiune;
6.3 Funcții liniare;
6.4 Sume directe și spații vectoriale cât;
6.5 Produs scalar. Ortogonalitate. Spațiu dual;
6.6 Aplicații: coduri detectoare și corectoare de erori;
6.6.1 Introducere:
6.6.1.1 Transmiterea informației prin canale cu zgomot;
6.6.1.2 Detecția și corecția erorilor; 372
6.6.1.3 Determinarea cuvântului cod transmis;
6.6.1.4 Coduri detectoare și corectoare de erori; 377
6.6.1.5 Problema fundamentală a teoriei codurilor bloc;
6.6.2 Coduri liniare:
6.6.2.1 Definiții. Exemple. Proprietăți de bază ;
6.6.2.2 Decodicare Slepian și sindrom;
7. Teoria mulțimilor parțial ordonate:
7.1 Completitudine:
7.1.1 Completitudine prin submulțimi. Latici complete;
7.1.2 Completitudine prin mulțimi dirijate; 397
7.1.3 Completitudine prin lanțuri;
7.2 Teoria de punct fix a mulțimilor parțial ordonate:
7.2.1 Funcții continue;
7.2.2 Puncte fixe;
7.2.3 Inducție de punct fix;
7.3 Aplicații: semantica și analiza programelor:
7.3.1 Semantica programelor:
7.3.1.1 -notație;
7.3.1.2 Programe recursive;
7.3.1.3 Semantica denotaționala a programelor recursive;
7.3.1.4 Programe structurate;
7.3.1.5 Semantica denotaționala a programelor structurate;
7.3.2 Analiza și verificarea programelor:
7.3.2.1 Analiza programelor; 450
7.3.2.2 Verificarea programelor;
8. Algebre universale:
8.1 Structuri sortate;
8.2 Signaturi și algebre;
8.3 Subalgebre. Inducție structurală; 474
8.4 Congruențe și algebre cât:
8.4.1 Definiții. Exemple. Proprietăți de bază;
8.4.2 Congruențe principale;
8.5 Homomorsme de algebre:
8.5.1 Definiții Exemple Proprietăți de bază;
8.5.2 Structura algebrica a mulțimilor End(A) și Aut(A) ;
8.5.3 Homomorsme și congruențe;
8.5.4 Teoreme de izomorsm;
8.6 Produse de algebre:
8.6.1 Produse directe de algebre;
8.6.2 Algebre decompozabile;
8.6.3 Produse subdirecte de algebre;
8.7 Algebre libere:
8.7.1 Algebre de termi
8.7.2 Algebre libere. Definiții și proprietăți de bază;
8.7.3 Teorema lui Birkho de existența a algebrelor libere;
8.8 Logică ecuațională:
8.8.1 Ecuații și modele;
8.8.2 Deducție ecuațională;
8.8.3 Axiomatizare;
8.9 Aplicații: semantica limbajelor de programare și specificare
algebrică a tipurilor abstracte de date:
8.9.1 Semantica limbajelor de programare:
8.9.1.1 Signatura asociată unei gramatici
independente de context;
8.9.1.2 Semantica programelor structurate;
8.9.1.3 Traduceri de programe și compilare;
8.9.2 Specificarea algebrică a tipurilor abstracte de date:
8.9.2.1 Introducere;
8.9.2.2 Specificații inițiale ale tipurilor abstracte de date;
8.9.2.3 Tratarea excepțiilor;
Bibliografie;
Lista figurilor;
Index
Ferucio Laurențiu Țiplea (n. 1962, Bârlad) este profesor universitar doctor la Facultatea de Informatică a Universității „Alexandru Ioan Cuza” din Iași. Domeniile de cercetare în care activează sunt: modelare și verificare formală (bazată pe elemente de algebră, logică și rețele Petri), complexitatea calculului, criptografie și securitatea informației. În fiecare din aceste domenii a publicat articole de cercetare în reviste de circulație internațională și a comunicat lucrări la conferințe internaționale. A conferențiat ca profesor invitat la universități din Germania, Franța, Ungaria, Statele Unite ale Americii, Japonia și Grecia și a beneficiat de granturi și burse oferite de DAAD, Academia Germană, Monbusho și Fulbright. Din ianuarie 2004 până în aprilie 2006, a activat ca Visiting Professor la University of Central Florida, School of Electrical Engineering and Computer Science, unde a predat cursul COT3100H: Honors Introduction to Discrete Structures, bazat pe prima ediție a prezentei cărți. Pentru mai multe detalii pe linie didactică și de cercetare, poate fi consultată secțiunea referitoare la autorul cărții de pe pagina web a Faculții de Informatică a UAIC.
