Avis des lecteurs
Il n'y a actuellement aucun avis de lecteur. La note est basée sur 2 votes.
Titre original :
A Mathematical Primer on Computability
Contenu du livre :
Ce livre constitue une introduction complète à la théorie de la calculabilité pour les étudiants avancés de premier cycle ou les étudiants de premier cycle en mathématiques et en informatique. Le matériel technique est illustré par de nombreux exemples, des problèmes avec des solutions entièrement travaillées ainsi qu'une série d'exercices proposés.
La première partie est centrée sur les notions et les résultats fondamentaux de la calculabilité, en commençant par les concepts piliers de modèle de calcul (un langage de programmation abstrait de haut niveau), de fonction calculable, d'ensemble décidable et listable, de fonction universelle propre, de problème de décision et de technique de réduction pour le transfert des propriétés de décidabilité et de listabilité. Les résultats essentiels, à savoir le théorème de Rice, le théorème de Rice-Shapiro, le théorème de Rice-Shapiro-McNaughton-Myhill ainsi que le théorème de Rogers et le théorème de récursion sont présentés et illustrés. La réductibilité plusieurs à un et les degrés plusieurs à un sont étudiés. Une brève introduction au calcul avec des oracles est également incluse. Les opérateurs calculables et non calculables sont introduits, ainsi que les opérateurs monotones et finitaires. La relation entre eux est discutée, en particulier via le théorème de Myhill-Shepherdson. Le théorème du moindre point fixe de Kleene est également présenté. Enfin, la partie I se termine par une brève présentation du modèle informatique de Turing, de la réductibilité de Turing et des degrés de Turing.
La deuxième partie du livre se concentre sur les applications de la calculabilité dans plusieurs domaines, notamment en logique (indécidabilité de l'arithmétique, satisfiabilité en logique propositionnelle, décidabilité en logique modale), en géométrie euclidienne, en graphes et en complexité de Kolmogorov. Néanmoins, aucune connaissance préalable de ces sujets n'est requise. Les détails essentiels pour comprendre les applications sont fournis.
Autres informations sur le livre :
| ISBN : | 9781848902961 |
| Auteur : | |
| Éditeur : | |
| Langue : | anglais |
| Reliure : | Broché |
Achat:
Actuellement disponible, en stock.
