Quelques remarques sur la complexité des algorithmes

G. Werner

ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique (1970)

  • Volume: 4, Issue: R2, page 33-50
  • ISSN: 0764-583X

How to cite

top

Werner, G.. "Quelques remarques sur la complexité des algorithmes." ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique 4.R2 (1970): 33-50. <http://eudml.org/doc/193141>.

@article{Werner1970,
author = {Werner, G.},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique},
language = {fre},
number = {R2},
pages = {33-50},
publisher = {Dunod},
title = {Quelques remarques sur la complexité des algorithmes},
url = {http://eudml.org/doc/193141},
volume = {4},
year = {1970},
}

TY - JOUR
AU - Werner, G.
TI - Quelques remarques sur la complexité des algorithmes
JO - ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique
PY - 1970
PB - Dunod
VL - 4
IS - R2
SP - 33
EP - 50
LA - fre
UR - http://eudml.org/doc/193141
ER -

References

top
  1. [1] J. HARTMANIS, R. E. STEARNS. « On the Computational Complexity of Algorithms » Trans. Amer. Math. Soc., 117, pp. 285-306 (1965). Zbl0131.15404MR170805
  2. [2] P. M. LEWIS II, R. E. STEARNS et HARTMANIS J. « Memory bounds for the recognition of context-free and context-sensitive languages », 1965,IEEE Conference Reord on Switching Circuit Theory and Logical Design, pp. 191-202, IEEE, New York (1965). Zbl0272.68054
  3. [3] J. HARTMANIS, « Tape-Reversal Bounded Turing Machine Computations », Journal of Computer and System Sciences 2, Nr 2, pp. 117-135 (1968). Zbl0259.68020MR243947
  4. [4] R. W. RITCHIE, « Classes of Predictably Computable Functions », Trans. Amer. Math. Soc, 106, pp. 139-173 (1963). Zbl0107.01001MR158822
  5. [5] M. O. RABIN, « Degrees of Difficulty of Computing a Function and a Partial Ordering of Recursive Sets », Technical Reporter Nr 2, Hebrew University, Jérusalem, (1960). 
  6. [6] Manuel BLUM, « A Machine-Independent Theory of the Complexity of Recursive Functions », Journal A.C.M., avril 1967, vol. 14, Nr 2, pp. 322-336. Zbl0155.01503MR235912
  7. [7] Manuel BLUM, « Recursive Function Theory and Speed of Computation », Canadian Math. Bull. 9 (1966), pp. 745-750. Zbl0158.24904
  8. [8] Dieter RÖDDING, « Klassen rekursiver Funktionen », Lecture Notes in Math. 70, 1968, Springer-Verlag, Berlin, pp. 159-222. Zbl0212.32802MR237335
  9. [9] S. C. KLEENE, « Extension of an Effectively Generated Class of Functions by Enumeration », Colloquium Math. VI (1958), pp. 67-78. Zbl0085.24602MR118672
  10. [10] Hartley ROGERS, Theory of Recursive Functions and Effective Computability, Mac Graw-Hill Book Company, New York, 1967. Zbl0183.01401MR224462

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.