Mthodes matricielles - Introduction la complexit algbrique [Paperback]

Ce livre est une introduction ? la th?orie de la complexit? alg?brique bas?e sur un panorama des m?thodes algorithmiques en alg?bre lin?aire exacte. Il donne en particulier les principaux algorithmes pour le calcul du polyn?me caract?ristique. Ce livre se remarque par l'?tendue des sujets trait?s tout en restant tr?s lisible.

Ce livre est une introduction ? la th?orie de la complexit? alg?brique bas?e sur un panorama des m?thodes algorithmiques en alg?bre lin?aire exacte. Il donne en particulier les principaux algorithmes pour le calcul du polyn?me caract?ristique. Il donne aussi une discussion d?taill?e des m?thodes de multiplication rapide des polyn?mes et des matrices, sans pour autant r?clamer de pr?requis th?oriques de haut niveau. Tout en ?tant centr? sur les probl?mes de complexit? alg?brique, il aborde aussi la complexit? binaire. Une place importante est accord?e au parall?lisme. Le livre se termine par une introduction raisonn?e ? l'importante th?orie de Valiant concernant un analogue alg?brique de la conjecture P = NP. Ce livre se remarque par l'?tendue des sujets trait?s tout en restant tr?s lisible.

Avant-Propos.- Rappels d'alg?bre lin?aire.- Algorithmes de base en alg?bre lin?aire.- Circuits arithm?tiques.- Notions de complexit?.- Diviser pour gagner.- Multiplication rapide des polyn?mes.- Multiplication rapide des matrices.- Alg?bre lin?aire s?quentielle rapide.- Parall?lisations de la m?thode de Leverrier.- Polyn?me caract?ristique sur un anneau arbitraire.- R?sultats exp?rimentaux.- Le d?terminant et les expressions arithm?tiques.- Le permanent et la conjecture P = NP.- Annexe : codes Maple.- Tables, Bibliographie, Index.

Ce livre est une introduction ? la th?orie de la complexit? alg?brique bas?e sur un panorama des m?thodes algorithmiques en alg?bre lin?aire exacte. Il donne en particulier les principaux algorithmes pour le calcul du polyn?me caract?ristique. Il donne aussi une discussion d?taillch