Descripción
Els límits de la computació: indecidibilitat i NP-completesa
Resumen del libro
Aquest llibre ofereix una introducció clara i rigorosa a les teories de la calculabilitat i la complexitat computacional, pensada per a estudiants d'enginyeria informàtica. A partir de la necessitat d'un model formal de computació, l'obra explora quins problemes poden ser resolts per un ordinador i quins no, tot introduint conceptes fonamentals com la indecidibilitat i la NP-completesa. Es tracta d'un text didàctic que combina fonaments teòrics amb exemples pràctics per entendre els límits inherents a la computació.
¿De qué trata?
El llibre aborda les fronteres teòriques de la informàtica, centrant-se en dues qüestions fonamentals: què es pot calcular i amb quina eficiència. Primer, s'introdueix un model formal de computació (com la màquina de Turing) per establir les bases de la calculabilitat. A partir d'aquí, s'exploren problemes indecidibles, és a dir, aquells per als quals no existeix cap algorisme que els pugui resoldre en tots els casos. En segon lloc, s'endinsa en la teoria de la complexitat, analitzant la classe de problemes NP-complets i la seva rellevància pràctica. L'obra utilitza un enfocament pedagògic, amb exemples il·lustratius i una progressió lògica que facilita la comprensió de conceptes abstractes.
Temas principales
- Models formals de computació: màquines de Turing i funcions recursives.
- Indecidibilitat: problemes que no tenen solució algorítmica (com el problema de la parada).
- Classes de complexitat: P, NP, NP-complet i NP-hard.
- Reduccions entre problemes i demostracions de NP-completesa.
- Implicacions pràctiques dels límits computacionals en enginyeria informàtica.
¿Para quién está recomendado?
Està recomanat per a estudiants universitaris de primer cicle d'enginyeria informàtica, ciències de la computació o matemàtiques aplicades que vulguin comprendre els fonaments teòrics de la computació. També és útil per a professionals del sector que desitgin aprofundir en les limitacions dels algorismes i la naturalesa dels problemes computacionals difícils.
Qué aporta este libro
- Proporciona una base sòlida per entendre què es pot i què no es pot resoldre amb un ordinador.
- Clarifica conceptes abstractes com la indecidibilitat i la NP-completesa mitjançant exemples pràctics.
- Desenvolupa habilitats per identificar problemes computacionalment difícils en contextos reals.
- Ofereix una perspectiva teòrica essencial per a futurs estudis avançats en algorismia i intel·ligència artificial.
- Facilita l'aprenentatge autònom gràcies a la seva estructura didàctica i progressiva.
Ficha técnica
- Autor: SERNA IGLESIAS, Mª JOSE; ALVAREZ FAURA, C
- Editorial: Universitat Politecnica de Catalunya. Iniciativa D
- Idioma: Català
- Tema: Conceptes de programació. Aprenentatge de la programació
- Colección: Aula Politécnica
- Encuadernación: Bolsillo
- Fecha de edición: No disponible
- Número de páginas: 266
- Dimensiones: No disponible
- Peso: 1005 g
Valoración editorial
Aquest llibre és una eina fonamental per a qualsevol estudiant d'informàtica que vulgui comprendre els límits teòrics de la computació. La seva claredat expositiva i l'enfocament pedagògic el converteixen en un recurs valuós per abordar conceptes complexos com la indecidibilitat i la NP-completesa. Tot i que està pensat per a un públic acadèmic, la seva estructura progressiva el fa accessible fins i tot per a aquells que s'inicien en la matèria. Una obra de referència per a qui busca anar més enllà de la programació pràctica i endinsar-se en els fonaments de la ciència computacional.