Effective Polynomial Computation è un'introduzione agli algoritmi dell'algebra informatica. Discute gli algoritmi di base per la manipolazione dei polinomi, inclusi i polinomi di fattorizzazione. Questi algoritmi vengono discussi sia da una prospettiva teorica che pratica. Vengono discussi i casi in cui gli algoritmi teoricamente ottimali sono inappropriati e vengono spiegate le alternative pratiche. Il calcolo polinomiale efficace fornisce gran parte della motivazione matematica degli algoritmi discussi per aiutare il lettore ad apprezzare i meccanismi matematici alla base degli algoritmi e in modo che gli algoritmi non sembrino costruiti in blocco. In preparazione alla discussione sugli algoritmi per i polinomi, il primo terzo di questo libro discute questioni correlate alla teoria elementare dei numeri. Questi risultati vengono utilizzati in algoritmi successivi (ad esempio la discussione sui reticoli e sull'approssimazione diofantea), oppure analoghi degli algoritmi di teoria dei numeri vengono utilizzati per problemi polinomiali (ad esempio l'algoritmo euclideo e i numeri p-adici). Tra le caratteristiche uniche del calcolo dei polinomi effettivi c'è il materiale dettagliato sul massimo comun divisore e sugli algoritmi di fattorizzazione per polinomi multivariati sparsi. Inoltre, vengono discussi sia gli algoritmi deterministici che quelli probabilistici per il test di irriducibilità dei polinomi.
caricamento...
