Menú

Here are the notes for the first lesson. These are just the first lines; the whole document can be found HERE.

Algorithms are at the core of Computer Science and, in particular, of string pattern recognition. However, the word “algorithm” does not possess a generally accepted deﬁnition. For the purposes of these notes, we will adopt an informal deﬁnition, which will be ﬂexible enough to describe the solutions to problems in string pattern recognition but not so formal as to be lengthy and unfriendly. An algorithm is a procedure that takes an input and, after performing a series of well-deﬁned computational operations, produces an output. Knuth [Knu73] has identiﬁed ﬁve properties –widely accepted– that an algorithm should have:

1. Input: The initial values or input instance of the problem.
2. Deﬁniteness: Every algorithm must be precisely deﬁned so that there is no ambiguity.
3. Finiteness: An algorithm must terminate after a ﬁnite number of steps.
4. Output: An algorithm must produce a set of ﬁnal values out of the input.
5. Efectiveness: All the operations must be sufficiently basic.

Berlinski in his year-2000 book [Ber00] provides a snappy, humoresque deﬁnition of an algorithm:

“In the logician’s voice:
“an algorithm is
a ﬁnite procedure,
written in a ﬁxed symbolic vocabulary,
governed by precise instructions,
moving in discrete steps, 1, 2, 3, . . .,
whose execution requires no insight, cleverness,
intuition, intelligence, or perspicuity,
and that sooner or later comes to an end.”

..........................................................................................................................................................

..........................................................................................................................................................

[Ber00] D. Berlinski. The Advent of the Algorithm: The 300-year Journey from an Idea to the Computer. Harcourt, Inc., San Diego, 1. edition, 2000. 1. editon 2000.
[Knu73] Donald E. Knuth. The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley, 1973.