Algorithm

Flow diagrams serve to represent algorithms graphically

Ada Lovelace's "nota G" diagram, the first published computer algorithm

In mathematics, logic, computer science, and related disciplines, an algorithm (from the Latin algorithmus and this from the Greek arithmos, which means "number", perhaps also influenced by the name of the Persian mathematician Al-Khwarismi) is a set of defined and unambiguous, ordered and finite instructions or rules that typically allows solving a problem, performing a computation, processing data and carry out other tasks or activities. Given an initial state and an input, following successive steps leads to a final state and a solution is obtained. Algorithms are the object of study of algorithmia.

In everyday life, algorithms are often used to solve certain problems. Some examples are user manuals, which show algorithms for using a device, or the instructions a worker receives from his employer. Some examples in mathematics are the multiplication algorithm, to calculate the product, the division algorithm to calculate the quotient of two numbers, Euclid's algorithm to obtain the greatest common divisor of two positive integers, or Gauss's method to solve a system of linear equations.

In programming terms, an algorithm is a sequence of logical steps that allow you to solve a problem.

Definition

In general, there is no definitive consensus regarding the formal definition of an algorithm. Many authors refer to them as lists of instructions to solve a calculation or an abstract problem, that is, a finite number of steps convert the data of a problem (input) into a solution (output). However, it should be noted that some algorithms do not necessarily have to finish or solve a particular problem. For example, a modified version of Eratosthenes' sieve, which never finishes calculating prime numbers, is still an algorithm.

Throughout history, various authors have tried to formally define algorithms using mathematical models. This was done by Alonzo Church in 1936 with the concept of "effective calculability" based on his lambda calculus and by Alan Turing based on the Turing machine. The two approaches are equivalent, in the sense that exactly the same problems can be solved with both approaches. However, these models are subject to a particular type of data, such as numbers, symbols, or graphs, while in general, the algorithms work on a vast number of data structures. In general, the common part in all the definitions can be summarized in the following three properties, as long as we do not consider parallel algorithms:

• Sequential time. An algorithm works in discreet time – step by step – thus defining a sequence of states computational for each valid entry (Entry are the data supplied to the algorithm before starting).
• Abstract state. Each computer state can be formally described using a first order structure and each algorithm is independent of its implementation (the algorithms are abstract objects), so that in an algorithm the first order structures are invariant under isomorphism.
• Explored scan. The transition from one state to the next is completely determined by a fixed and finite description; that is, between each state and the next one can only take into account a fixed and limited number of terms of the current state.

In short, an algorithm is anything that works step by step, where each step can be described unambiguously and without reference to a particular computer, and also has a fixed limit on the amount of data that can be can read/write in one step.

This broad definition covers both practical algorithms and those that only work in theory, for example, Newton's method and Gauss-Jordan elimination work, at least in principle, with infinite-precision numbers; however, it is not possible to program infinite precision in a computer, and they do not stop being algorithms. In particular, it is possible to consider a fourth property that can be used to validate the Church-Turing thesis, that all calculable functions are you can program in a Turing machine (or equivalently, in a sufficiently general programming language):

• Aritmetizability. Only undeniably calculated operations are available in the initial step.

Means of expression of an algorithm

Algorithms can be expressed in many ways, including natural language, pseudocode, flowcharts, and programming languages among others. Natural language descriptions tend to be ambiguous and lengthy. Using pseudocode and flowcharts avoids many natural language ambiguities. Such expressions are more structured ways to represent algorithms; however, they remain independent of a specific programming language.

The description of an algorithm is usually done at three levels:

1. High-level description. The problem is set, a mathematical model is selected and the algorithm is explained verbally, possibly with illustrations and omitting details.
2. Formal description. A pseudocode is used to describe the sequence of steps that find the solution.
3. Implementation. It shows the algorithm expressed in a specific programming language or some object capable of carrying out instructions.

It is also possible to include a theorem proving that the algorithm is correct, a complexity analysis, or both.

Flowchart

Flow diagram that expresses an algorithm to calculate the square root of a number x{displaystyle x}

Flowcharts are graphical descriptions of algorithms; they use symbols connected with arrows to indicate the sequence of instructions and are governed by ISO.

Flowcharts are used to represent small algorithms because they take up a lot of space and are laborious to build. Due to their ease of reading, they are used as an introduction to algorithms, a description of a language and a description of processes for people unfamiliar with computing.

Pseudocode

Pseudocode (fake language, the prefix pseudo means false) is a high-level description of an algorithm that employs a mixture of natural language with some syntactic conventions typical of programming languages, such as assignments, loops, and conditionals, although it is not governed by any standard.

Pseudocode is intended to make it easier for people to understand an algorithm, and therefore may omit irrelevant details that are necessary in an implementation. Different programmers often use different conventions, which may be based on the syntax of particular programming languages. However, the pseudocode, in general, is understandable without the need to know or use a specific programming environment, and it is sufficiently structured so that its implementation can be done directly from it.

Thus, the pseudocode fulfills the aforementioned functions to represent something abstract, the protocols are the programming languages. Look for more accurate sources to have a better understanding of the subject.

Formal Systems

The theory of automata and the theory of recursive functions provide mathematical models that formalize the concept of algorithm. The most common models are the Turing machine, log machine, and μ-recursive functions. These models are as precise as machine language, lacking colloquial expressions or ambiguity; however, they remain independent of any computer and any implementation.

Implementation

Many algorithms have been devised to be implemented in a program. However, algorithms can be implemented in other media, such as a neural network, an electrical circuit, or a mechanical and electrical device. Some algorithms are even specially designed to be implemented using pencil and paper. The traditional multiplication algorithm, Euclid's algorithm, Eratosthenes' sieve, and many ways to solve the square root are just a few examples.

Variables

They are elements that take specific values of a specific data type. The declaration of a variable can be done starting with var. There are mainly two ways to give initial values to variables:

1. By an assignment sentence.
2. Using a data entry procedure (e.g. 'read').

Example:

...
i:=1;
read(n);
while i ك n do begin
(* loop body *)
i: = i + 1
end;
...

Sequential structures

The sequential structure is one in which one action follows another in sequence. The operations follow one another in such a way that the output of one is the input of the next and so on until the end of the process. The assignment of this consists of passing values or results to an area of memory. This zone will be recognized with the name of the variable that receives the value. The allocation can be classified as follows:

1. Simple: It consists of passing a constant value to a variable (to ← 15)
2. Accountant: It consists of using it as a checker of the number of times a process is performed (to ← to + 1)
3. Accumulator: Consists of using it as a suitor in a process (to ← a + b)
4. Working: Where you can receive the result of a mathematical operation that involves many variables (to ← c + b*1/2).

An example of sequential structure, such as obtaining the area of a triangle:

Home
...
float b, h, a;
printf("Say the base");
scanf("%f", &b);
printf("Say the height");
scanf("%f", &h);
a = (b*h)/2;
printf("The area of triangle is %f", a)
...
Fin

Algorithms as functions

Schematic of an algorithm that solves a hamiltonian cycle problem

An algorithm can be conceived as a function that transforms the data of a problem (entryed) into the data of a solution (exit). Moreover, the data can be represented in turn as bit sequences, and in general, of any symbols. As each bit sequence represents a natural number (see binary system), then algorithms are essentially functions of natural numbers in the natural numbers that can be calculated. I mean, every algorithm calculates a function f:: N→ → N{displaystyle fcolon mathbb {N} to mathbb {N} } where each natural number is the coding of a problem or a solution.

Sometimes algorithms are susceptible to never ending, for example, when they enter an infinite loop. When this happens, the algorithm never returns any output value, and we can say that the function is undefined for that input value. For this reason, algorithms are considered to be partial functions, that is, not necessarily defined in their entire domain of definition.

When a function can be computed by algorithmic means, no matter how much memory it occupies or how long it takes, the function is said to be computable. Not all functions between data sequences are computable. The stopping problem is an example.

Analysis of algorithms

As a measure of the efficiency of an algorithm, the resources (memory and time) consumed by the algorithm are usually studied. Algorithm analysis has been developed to obtain values that somehow indicate (or specify) the evolution of time and memory expenditure as a function of the size of the input values.

The analysis and study of algorithms is a discipline of computer science and, in most cases, its study is completely abstract without using any type of programming language or any other implementation; Therefore, in that sense, it shares the characteristics of the mathematical disciplines. Thus, the analysis of algorithms focuses on the basic principles of the algorithm, not on those of the particular implementation. One way to capture (or sometimes "code") an algorithm is to write it in pseudocode or use a very simple language such as Lexico, whose codes can be in the language of the programmer.

Some writers restrict the definition of an algorithm to procedures that must finish at some point, while others consider procedures that could run forever without stopping, assuming there was some physical device that was capable of running forever. In this last case, the successful completion of the algorithm could not be defined as its termination with a satisfactory output, but rather the success would be defined as a function of the sequences of outputs given during a period of life of the execution of the algorithm. For example, an algorithm that checks that there are more 0's than 1's in an infinite binary sequence must always execute in order to return a useful value. If implemented correctly, the value returned by the algorithm will be valid, until it evaluates to the next binary digit. In this way, while evaluating the following sequence, two types of signals can be read: a positive signal (if the number of zeros is greater than the number of ones) and a negative signal otherwise. Finally, the output of this algorithm is defined as returning exclusively positive values if there are more 0's than 1's in the sequence, and otherwise it will return a mix of positive and negative signals.

Algorithm Example

The problem is to find the maximum of a set of numbers. For a more complex example see Euclid's Algorithm.

High-level description

Given a finite set C{displaystyle C} Numbers, you have the problem of finding the largest number. Without loss of generality you can assume that such a set is not empty and that its elements are numbered as c0,c1,...... ,cn{displaystyle c_{0},c_{1},dotsc_{n}}.

I mean, given a set C={c0,c1,...... ,cn!{displaystyle C={c_{0},c_{1},dotsc_{n}}}} is asked to find m{displaystyle m} such as x≤ ≤ m{displaystyle xleq m} for all elements x{displaystyle x} that belongs to the whole C{displaystyle C}.

To find the maximum element, it is assumed that the first element (c0{displaystyle c_{0}}) is the maximum; then it runs through the set and compares each value to the maximum number value found until that time. In the event that an element is greater than the maximum, its value is assigned to the maximum. When the list is finished, the maximum number that has been found is the maximum of the entire set.

Formal description

The algorithm can be written in a more formal way in the following pseudocode:

About the notation:

• "←" represents an assignment: m{displaystyle m} ← x{displaystyle x} means the variable m{displaystyle m} takes the value of x{displaystyle x};
• "return" ends the algorithm and returns the value to your right (in this case, the maximum C{displaystyle C}).

Implementation

In C++ language:

int max(int c[], int n){ int i, m = c[chuckles]0]; for (i = 1; i . n; i+) if (c[chuckles]i] ▪ m) m = c[chuckles]i]; return m;!