Computability and Complexity Theory [Romanian]

0
84

Original in English by Alan Selman

Teoria de complexitate şi calculabilitate

Steven Homer si Alan L. Selman

Springer Verlag New York, 2001

ISBN 978-1461406815

Acest volum introduce materiale care reprezintă cunoştinţele de bază în teoria de calcul. Cartea este de sinestătătoare, cu un capitol preliminar care descrie concepte cheie matematice şi notaţiile şi capitolele următoare trecътв de la aspectele calitative ale teoriei clasice de сalculabilitate la aspectele cantitative ale teoriei complexităţii. Capitole dedicate impreciziei, NP- complete, şi a calculabilității relative finisează cartea, și ele se axează pe limitările de calculabilitate şi distincţii între problemele fezabile şi cele ce e greu de rezolvat.

Subiecte şi caracteristici:

* Materiale concise și concentrate acoperă conceptele cele mai fundamentale şi rezultate în domeniul teoriei complexităţii moderne, inclusiv teoria NP-complet, NP-duritate, ierarhia polinomială si probleme complete pentru alte clase de complexitate.

* Conţine informaţii care, altfel, există doar în literatura de cercetare şi le prezintă într-un mod unificat, simplificat, de exemplu, despre completarea complexității claselor, probleme de căutare, şi probleme intermediare în NP.

* Oferă informaţii-cheie matematice, inclusiv punctele de logică şi teoria numerelor şi algebră.

* Suportat prin numeroase exerciţii şi probleme suplimentare pentru scopuri de consolidare şi de auto-studiere.

Cu accesibilitatea şi organizaţia sa bine concepută, acest text / referinţă este o resursă excelentă şi ghid pentru cei care caută să dezvolte o baza solida în teoria de calcul.  Absolvenţi începători, studenţi avansați şi profesionişti implicaţi în informatică teoretică, teoria complexităţii, şi calculabilitate vor găsi această carte un instrument esenţial şi practic pentru învăţamînt.

Cuprins

1. PRELIMINARII

  • Cuvintele şi limbi
  • Reprezentare K-adic
  • Funcţii parţiale
  • Grafice
  • Logicică propozițională
  • Cardinalitatea
  • Algebra elementară

2. INTRODUCERE ÎN CALCULABILITATE

  • Mașini lui Turing
  • Conceptil mașinilor lui Turing
  • Variaţiile de Masini lui Turing
  • Biserica Tezei/li>
  • RAM-uri

3. IMPRECIZIE

  • Problemele deciziei
  • Probleme indecidabile
  • Funcţii împerecheate
  • Seturi computabile și enumerable
  • Problema de stoparea, reduceri şi seturi complete
  • Teorema s-m-n
  • Teorema recursivității
  • Teorema lui Rice
  • Reducerile lui Turing şi Mașini Oracle lui Turing
  • Teorema recursivității, continuare
  • Referinţe
  • Probleme suplimentare pentru temă de acasă

4. NTRODUCERE ÎN TEORIA DE COMPLEXITATE

  • Clasele de complexitate şi măsurările de complexitate
  • Cerinţe preliminare

5. REZULTATELE DE BAZĂ ALE TEORIEI COMPLEXITATE

  • Copresie lineară și accelerare
  • Funcţii construibile
  • Bandă de reducere
  • Relaţii de incluziune
    • Relațiile dintre clasele standard
  • Separarea rezultatelor
  • Relațiile dintre clasele standard – continuare
    • Completări ale claselor de complexitate: Teorema lui Immerman-Szelepcsenyi
  • Probleme suplimentare la temele de acasă

6. NONDETERMINISM ŞI NP-COMPLECTITATE

  • Caracterizarea de NP
  • Clasa P
  • Enumerări
  • NP-complectități
  • Teorema lui Cook-Levin
  • Mai multe probleme cu NP-complectități
  • Probleme suplimentare la temele de acasă

7. CALCULABILITATE RELATIVĂ

  • NP-duritate
  • Căutarea probleme
  • Structura de NP
    • Numărul compozit si izomorfismul graficelor
    • reflecţie
  • Ierarhia polinomială
  • Probleme complete pentru altele clase de complexitatea
    • PSPACE
    • Timp exponențial
    • Timpul polinomial și spațiul logaritmic
    • O notă cu privire la problemele care pot apărea în mod demonstrabil
  • Probleme suplimentare pentru temă de acasă

Front matter with Preface and Table of Contents

[postscript]
[PDF]

Link-uri importante:

LEAVE A REPLY

Please enter your comment!
Please enter your name here