//img.uscri.be/pth/b096af1b12319ba88cda73c3152fa927641c7ebb
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Algebraic Characterization of Computable and Complexity Theoretic Analysis

De
30 pages
Algebraic Characterization of Computable and Complexity-Theoretic Analysis Walid Gomaa INRIA Nancy Grand-Est Research Centre CARTE team January 12, 2009 Walid Gomaa Algebraic Char. of Comp. and Complexity-Theoretic Analysis

  • finite binary representation

  • problem-oriented approach

  • real numbers

  • ?x ?n ?

  • investigates real

  • cauchy sequence


Voir plus Voir moins
AlgebraicCharacterizationofComputableandComplexity-TheoreticAnalysisWalidGomaaINRIANancyGrand-EstResearchCentreCARTEteamJanuary12,2009aWildGoamalAgebraciCha.rofCopm.andCopmelxtiy-hTeoretcinAaylsis
.IeRlaoCmupatitnoTwoindependentapproaches:RecursiveAnalysis&NumericalAnalysisRecursiveanalysisinvestigatesrealcomputationusingclassicalrecursiontheoryanditstechnologiesNumericalanalysisisanalgorithmicproblem-orientedapproachComparewithclassicalrecursiontheoryvs.analysisanddesignofalgorithmsRecursiveanalysisisthefocusofthispresentation.ItwasintroducedbyTuring[1936],Grzegorczyk[1955],andLacombe[1955].aWildGoamalAgebraciCha.rofCopm.andCopmelxtiy-hTeoretcinAaylsis
eRrpseneatitnofoeRlauNmebrGivenx,severalrepresentations:sBinaryexpansion:BExN→{0,1}Leftcut:LCx={rQr<x}CauchySequence:CFNxQRecursively-wisetheyareequivalentHowever,theydifferonthesub-recursiveaswellasthecomplexity-theoreticlevelaWildGoamalAgebraciCha.rofCopm.andCopmelxtiy-hTeoretcinAaylsis