Leonid A. Levin. Fundamentals of Computing.

The HTML , PDF , Postscript , and DVI files.

The LaTeX sources:

    Foreword.
  1. Models of Computations; Polynomial Time and Church's Thesis.
    1. Deterministic Computation.
    2. Rigid Models.
    3. Pointer Machines.
    4. Simulation.
  2. Universal Algorithm; Diagonal Results.
    1. Universal Turing Machine.
    2. Uncomputability; Goedel Theorem.
    3. Intractability; Compression and Speed-up Theorems.
  3. Games; Alternation; Exhaustive Search; Time v. Space.
    1. How to Win.
    2. Exponentially Hard Games.
    3. Reductions; Non-Deterministic and Alternating TM; Time/Space.
    4. Fast and Lean Computations.
  4. Nondeterminism; Inverting Functions; Reductions.
    1. Example of a Narrow Computation: Inverting a Function.
    2. Complexity of NP Problems.
    3. An NP-Complete Problem: Tiling.
  5. Randomness in Computing.
    1. A Monte-Carlo Primality Tester.
    2. Randomized Algorithms and Random Inputs.
    3. Randomness and Complexity.
    4. Pseudo-randomness.
    5. Cryptography.
References.

You can also click for my papers (some online), my CV, or my research overview.