OOPortal OOPortal


Structured Programming  «Prev  Next»
Lesson 2Programming Fundamentals Prerequisites
ObjectiveVerify that you have the right background for this course.

Programming Fundamentals Prerequisites

There really aren't any prerequisites for this course other than a general familiarity with computers and an interest in learning how to write computer programs.
No previous programming experience is required for this course.
If your background includes downloading and installing software from the Web or creating Web pages with HTML and a scripting language, then some of the tasks you will be asked to do in the course will be made a bit easier.
In the next lesson, you will learn what you need to take this course.

Concept and History of Algorithms

The concept of algorithm has existed for centuries, however a partial formalization of what would become the modern algorithm began with attempts to solve the Entscheidungsproblem (the "decision problem") posed by David Hilbert in 1928. Subsequent formalizations were framed as attempts to define "effective calculability" or the "effective method".
Alan Turing's Turing machines from 1936 to 1937 and 1939 gave a formal definition of algorithms, corresponding to the intuitive notion.

Kolmogorov complexity

In algorithmic information theory, the Kolmogorov complexity of an object, such as a piece of text, is the length of the shortest computer program in a programming language that produces the object as output. It is a measure of the computational resources needed to specify the object, and is also known as descriptive complexity,
  1. Kolmogorov-Chaitin complexity,
  2. algorithmic entropy, or
  3. program-size complexity.
It is named after Andrey Kolmogorov, who first published on the subject in 1963.
The notion of Kolmogorov complexity can be used to state and prove impossibility results akin to
  1. Cantor's diagonal argument,
  2. Goedel's incompleteness theorem, and
  3. Turing's halting problem.