Algorithms

Algortimy Content of the lesson:

Algorithm
Algorithm Characteristic
Examples of Algorithms
Computer Program
Notation of Algorithms

Algorithm

Algorithm is a set of precise instructions or steps to solve a given type of task. The term algorithm usually appears in the programming, where it is meant as a theoretical principle to solve a problem (in opposite to a notation in a concrete programming language). It is a prescript for the computer (processor) to make calculations to solve a given problem. A kitchen recipe can also be described as a kind of an algorithm.

If we had to refine the term for our needs we can say that an algorithm is a prescript to solve a particular problem. In other words, it is a precisely defined sequence of steps which needs an input data (correct input values) and which finds a solution using a finite number of steps. If we want to be really accurate, we can define an algorithm as a "procedure realizable by the Turing machine". Nevertheless, we do not have to define an algorithm now because this is usually solved at universities; we have to know the principles.

Finality - Every algorithm has to end using a finite number of steps. The number of steps can be arbitrarily large (depending on the range and value of the input data), but must be finite for each individual entry.
Determination - Every step of an algorithm must be clearly and precisely defined; in each situation it must be absolutely clear what and how should be done, how to continue the implementation of an algorithm. As the plain language does not usually provide complete accuracy and clarity of an expression, programming languages have been designed for writing algorithms so each command has its clearly defined meaning. Expression of computational methods in a programming language is called a program.
Input (versatility) - Inputs have defined sets of values, which they can acquire. An algorithm can be used for a whole set of input data. An algorithm usually works with some input variables that are delivered to it before the start of its implementation, or in the course of its progress.
Output (finality) - An algorithm has at least one output - a value which is in a required relation to the specified inputs and thus creates an answer to a problem that is being solved by the algorithm. (Algorithm leads from processing input values to an output – end result).
Universality (generality, mass usage) - An algorithm does not handle one specific problem (such as "how to count 3 x 7"), but a general category of similar problems (such as "how to calculate the product of two integers").
Efficiency - It is generally required that an algorithm is effective, which means that all operations requested by an algorithm are sufficiently simple to be able at least in principle to be carried out in finite time using only a pencil and a piece of paper.

In practice, therefore, only those algorithms are subjects of interest which are of good quality in some sense. Such algorithms fulfill various criteria, measured e.g. by the number of steps needed to run the algorithm, or simplicity and elegance of the algorithm. Problems of efficiency of algorithms, which means methods how to choose the best algorithm from more known ones dealing with a specific problem, are dealt by branches of informatics called algorithmic analysis and theory of complexity.

A part of the text about the algorithm and its features has been taken from Wikipedia (http://cs.wikipedia.org/wiki/Algoritmus).

Computer Program

A computer program (thereinafter referred to as a program) is from the point of view of informatics a description of operations that solve a given assignment. The notation of an algorithm in any programming language is called a program. A program is usually produced (written) by a programmer. As an example there is a simple program that lets user enter two numbers a and b and displays their sum on the screen.

An algorithm implemented by this program could be expressed in a natural language using these steps:

Enter number a.
Enter number b.
Display the sum of a+b on the screen.

A sample of a program written in Pascal


			Program SectiDveCisla;

            var a,b:integer;

            begin

            	readln(a);

                readln(b);

                writeln(a+b);

       		end.

The same sample written in Java


			import java.util.Scanner;

			public class InputExp {

			   public static void main(String[] args) {

                int a,b;
                
                Scanner in = new Scanner(System.in);
                
                a = in.nextInt();
                b = in.nextInt();
                in.close();
                
                System.out.println(a+b);
                }
            }

Writing a program has its own rules, but the lucidity of the source code of the program can be improved by the way we write it. The previous sample of program can be rewritten as the following sample:

The same sample written in Java (adjusted version)


			import java.util.Scanner;


			public class InputExp {


			    public static void main(String[] args) {


                int a,b;

                
                  Scanner in = new Scanner(System.in);

                
                   a = in.nextInt();

                   b = in.nextInt();

                   in.close();

                
                   System.out.println(a+b);

                 }

            }

We can see that even if we do not understand the program it is easier to follow now.

Notation of Algorithms

Algorithms can be written in many ways. We will show some of them on the simple algorithm for the sum of two given numbers:

A) By verbal expression (similar to a cooking recipe):

Enter number a.
Enter number b.
Display the sum of a+b on the screen.

B) Using a diagram (a simple scheme, drawing, flowchart etc.) showing the procedure:

a-plus-b-algorithm

C) Using a programming language:

A sample of a program written in Pascal


			Program SectiDveCisla;

            var a,b:integer;

            begin

            	readln(a);

                readln(b);

                writeln(a+b);

       		end.

A sample of a program written in C


            #include "stdafx.h"

			

			int _tmain(int argc, _TCHAR* argv[])

			{
	
                int a, b;
	
            	scanf("%d", &a);

                scanf("%d", &b);

                printf("%d",a+b);

            return 0;

			}

Additional Texts

Links

http://cs.wikipedia.org/wiki/Algoritmus
http://cs.wikipedia.org/wiki/The_Art_of_Computer_Programming monograph The Art of Computer Programming
http://cs.wikipedia.org/wiki/Po%C4%8D%C3%ADta%C4%8Dov%C3%BD_program
http://www.fi.muni.cz/~tomp/java/ucebnice/resources.html - Tomáš Pitner's website with links to Java issues
http://cs.wikipedia.org/wiki/Turingův_stroj
http://cs.wikipedia.org/wiki/Church-Turingova_teze - an answer to the question "Why can every possible algorithm be expressed using the Turing machine?".

Questions

What do you understand by the term algorithm?
What basic features should an algorithm fulfill? Try to give samples for the features.
What do you imagine under the term “computer program”?
Is it possible to improve the readability of the program by a different structure of notation? Give an example.

webdesign, xhtml, css, php - Mgr. Michal Mikláš