Home
Home
Connect

McGraw-Hill Education (Italy) srl

ITALIA Indian Flag
Strumenti Tools Print Larger font Smaller font Bookmark this page
 
Share/Bookmark

DISCIPLINE
Economia ed Economia aziendale
Informatica
Ingegneria e architettura
Medicina
Scienze infermieristiche e professioni sanitarie
Scienze matematiche, fisiche, chimiche e biologiche
Scienze umane e sociali
Monografie
Pubblicazioni dalle aziende
Dalla macchina di Turing a P/NP

Di: Daniele Mundici

Formato digitale

Dalla macchina di Turing a P/NP


ISBN: 9788838674020,
Prezzo: € 19,00
Pubblicazione: ottobre 2013
Pagine: 136
Metti nel carrello




Mi piace questo libro

Indice dettagliato (formato PDF)
Presentazione/prefazione (formato PDF)
Visualizza titoli simili:
Categoria: Monografie
Collana: Monografie

Descrizione | IndiceGli autori |

DESCRIZIONE

In questo libro risponderemo alle seguenti domande:
(i) Che cos'è un passo di calcolo?
(ii) Quali algoritmi richiedono un numero abbordabile di passi di calcolo?
(iii) Che applicazioni concrete possono avere problemi che talora richiedono un numero proibitivo di passi di calcolo già per esempi facilissimi da enunciare?

Dal 1936 i costi delle procedure meccaniche di calcolo si misurano contando i passi delle macchine di Turing. Costruiremo la macchina di Turing "universale", capace di effettuare tutte le procedure meccaniche di calcolo concepibili no a oggi. Tale macchina, pur essendo un oggetto puramente matematico come il numero π si è progressivamente materializzata nel computer. Approfondiremo la distinzione tra procedure abbordabili, come quelle che regolano l'addizione e la moltiplicazione, e procedure di calcolo il cui costo è proibitivo. Individueremo una classe di problemi la cui complessità oggi non ci è nota, e che sono velocemente traducibili l'uno nell'altro. Il prototipo di questi problemi, denominato sat, chiede di decidere se una formula della logica di Boole sia soddisfacibile. Il problema P/NP chiede se SAT possa essere risolto da una macchina di Turing che utilizza un numero di passi polinomiale rispetto alla lunghezza della formula in input. Se tale macchina esistesse, molti problemi importanti nell'industria e nella vita quotidiana sarebbero risolvibili a costi drasticamente ridotti rispetto ai costi attuali.Come vedremo analizzando l'algoritmo di Euclide, l'ignoranza di algoritmi veloci per il problema SAT ha un'applicazione utile nella crittografia a chiave pubblica.

INDICE

Parte A La Turing-calcolabilità
1.La macchina di Turing
2.Composizione, ricorsione, minimizzazione
3.La macchina universale
4.Prima appendice: le funzioni primitive ricorsive
Parte B Logica, P e NP
5.La logica delle CNF-formule
6.Alfabeti, problemi, riduzioni, la classe P
7.NP
8.Logica e NP-completezza
9.Altri problemi NP-completi
Parte C La crittografia a chiave pubblica
10.Crittografia, P e NP
11.Seconda appendice: l'algoritmo di Euclide e polytime
12.Osservazioni finali
Indice analitico

GLI AUTORI

Daniele Mundici

Daniele Mundici è laureato in Fisica. Dal 2002, professore di Logica Matematica presso il Dipartimento di Matematica e Informatica dell'Università degli Studi di Firenze. Precedentemente, professore di Algoritmi e Calcolabilità presso il Dipartimento di Scienze dell'Informazione dell'Universit`a degli Studi di Milano.
Membro dell'Accademia Internazionale di Filosofia delle Scienze (Bruxelles), e Membro Corrispondente dell'Accademia Nazionale delle Scienze Esatte, Fisiche e Naturali (Buenos Aires).
Presidente dell'Associazione Italiana di Logica e Applicazioni (AILA) e della Kurt Godel Society (KGS) di Vienna (1993-1996). Segretario del Gruppo Nazionale di Geometria, Algebra e Applicazioni dell'Istituto Nazionale di Alta Matematica, Roma (1998-2013).
Managing Editor di molte pubblicazioni internazionali di Logica, Algebra, Matematica Applicata e Informatica. Autore di quattro libri di Logica classica e non classica, e di oltre centocinquanta lavori scientifici di Matematica e Informatica.

Top

Chi siamo | Condizioni di utilizzo | Informativa sulla privacy | Normativa sul diritto d’autore| Modello di organizzazione, gestione e controllo | Contattaci | Assistenza | Come ordinare | Mappa del sito

Copyright © 2002 -2017 McGraw-Hill Education (Italy) srl
Via Ripamonti 89, 20139 Milano, Italia - Telefono +39 02/5357181 - Fax +39 02/5397633
Cap. Soc. Euro 10.000 Int. vers. | Codice Fiscale e P. IVA 07805780967 - Iscritta presso la C.C.I.A.A. di Milano numero di iscrizione 07805780967 | R.E.A. 1982936