An algorithm (ALG) is a rewritten, well-defined, sequential and finite set of instructions or rules that allow an activity to be executed in sequential steps for the person performing it in related fields such as Mathematics, Computer Science.
What is an Algorithm, and What are its Types and Features?
Given an initial state and an input, following successive steps, a final state is reached and a solution is obtained.
The word algorithm comes from Muḥammad ibn Mūsā al-Khwārizmī, a 9th-century Arab mathematician, originally from the ancient city of Khowarism located in the USSR. The famous mathematician was able to formulate the rules for four multi-step arithmetic operations.
Later, this formula was generally used to determine the sequences of operations that lead to the solution of any mathematical task.
As time passed, the process of searching and formalizing algorithms was not just a task for mathematicians, but different types of algorithms began to emerge.
Thus, algorithms emerged for games such as checkers and chess, involving shapes and positions where it is necessary to choose the next step of the objects.
These are the actions of an electric current or a specific machine, or, for example, the search algorithm for a word in a dictionary using texts.
However, it should be noted that in any case, algorithms do not work with real-world objects, but with their representations and abstractions. Therefore variables, symbols, encodings are used to denote them.
Algorithms are also used to solve problems many times in everyday life. For example, they are manuals that show algorithms for using a device or instructions an employee receives from their employer.
Examples of using algorithms in mathematics are the division algorithm to calculate the division of two numbers, the Euclidean algorithm to obtain the largest common divisor of two positive integers or the Gaussian method to solve a system of linear equations.
In general, there is no strict consensus on the official definition of an algorithm. Many authors refer to them as lists of instructions for solving an abstract problem, that is, the finite number of steps that transform a problem’s data into a solution.
However, it should be noted that some algorithms do not have to finish or solve a particular problem. For example, a modified version of the Eratosthenes sieve that never finishes calculating prime numbers is still an algorithm.
Throughout history, many authors tried to explain using mathematical models and algorithms such as Turing machines.
However, these models are subject to a certain type of data such as numbers, symbols, or graphs. However, algorithms generally work on large amounts of data structures.
In general, the common part in all definitions can be divided into three, unless we consider parallel algorithms.
1. Sequential Time
An ALG runs step-by-step in discrete time, thus defining a set of computational situations for each valid input.
2. Abstract State
Each computational situation can be defined using the first-order structure, and each ALG is independent of its implementation. Thus, first-order structures in an ALG are invariant under isomorphism.
3. Bounded State
The transition from one state to another is determined by a completely fixed and finite definition. In short, between each state and the next, only a fixed and finite number of terms of the current state can be considered.
In short, an ALG is a solution method that works step by step, where each step can be clearly defined without reference to a specific computer, and also has a fixed limit for the amount of data that can be read/written in one step.
This broad definition can cover both practical ALGs and those that only work in theory. For example, Newton’s method and Gauss-Jordan elimination work infinitely, at least in principle. However, it is not possible to program an endless process on a computer.
In particular, Arithmetic can be considered as a fourth feature that can be used to verify that every computable function can be programmed in a Turing machine. In the first step, there are only computable transactions that cannot be processed.
ALGs can be done in many ways, including natural language, pseudocode, flowcharts, and programming languages.
Natural language descriptions tend to be vague and lengthy. However, using pseudocode and flowcharts removes many natural language ambiguities.
These expressions are more structured ways to represent ALGs. However, they remain independent of a particular programming language.
The description of an ALG is usually made in high-level expression, form, and application.
In the high-level description, the problem is set up, a mathematical model is chosen, and the ALG is verbally explained with pictures and details. If an element is greater than the maximum, its value is assigned to the maximum.
To find the maximum element, the value of the first element is assumed to be maximum. Each value is then compared with the value of the maximum number found so far.
In figural expression, pseudocode is used to describe the sequence of steps that find the solution.
In the implementation method, some objects that can perform the ALG or commands expressed in a particular programming language are shown. It is also possible to include a theory that shows that the ALG is correct, the complexity analysis, or both.
Flowcharts are graphic descriptions of ALGs. They use symbols associated with arrows to indicate the order of instructions and are governed by the ISO.
They are used to represent small ALGs because they take up a lot of space and are somewhat difficult to create.
Because of their ease of reading, they are used as an introduction to ALGs, a description of a language, and a description of processes to people outside of computing.
Structured Rectangular Diagrams
One of the challenges of flowcharts is that they provide the possibility to graphically illustrate the flow of the solution towards a problem.
An erratic programmer misplacing the flow arrows can eventually lead to a more complex situation than the idea itself. In another case, it allows using graphical tools to represent the solution to a problem.
It is based on representing the entire ALG in a rectangular frame and, unlike the previous technique, it basically proceeds with the use of three symbols corresponding to each of the basic structures of programming logic.
Pseudocode is a method that looks like a programming language but has some natural language rules. It represents particularly complex instructions as it has many advantages over flowcharts. Also, it is not subject to any standard.
Pseudocode has a group of keywords and symbols that make up the vocabulary to represent the actions of this technique for computational ALGs.
To draw a flowchart using this technique, the following rules must be followed:
1. First Step
The word ALG is written and the name of the ALG is written after space. Thus, a reference is made to the stated situation.
If we call the Pseudocode as X, its purpose may not be so obvious. However, if we give the name Variable for the pseudocode, we can more easily say that its purpose is variable.
2. Second Step
The entire body of the ALG should be enclosed in the words Start and End, showing where the pseudocode begins and ends.
3. Third Step
After inserting the word begin, we need to state the state of the work to be done.
4. Fourth Step
In the last step, actions are written after the work to be done is declared.
Automata theory and the theory of iterative functions provide mathematical models that formalize the concept of ALGs. The most common models are the Turing machine, recorder, and μ – recursive functions.
These models are as precise as a machine language. They do not have colloquial expressions or ambiguity, but they are independent of any computer and any application.
Many ALGs are designed to be implemented in a program. However, ALGs can also be applied in other environments such as a neural network, an electrical circuit, or a mechanical and electrical device.
Some ALGs are even specially designed to be applied using a pencil and paper.
The traditional multiplication ALG, Euclid’s ALG, Eratosthenes’ sieve, and many ways to solve the square root are just a few examples.
It is a diagram of an ALG that solves the Hamilton loop problem and can be thought of as a function that converts the data of a problem (input) into data of a solution (output).
Also, the data itself can be represented as sequences of bits and generally as sequences of any symbol. Since each bitstream represents a natural number, ALGs are functions of natural numbers that can be calculated.
Each flowchart computes a function where each natural number is the encoding of a problem or a solution. For example, when they enter an endless loop, they may never end.
In such a case, it never returns any output value and we can say that the function is undefined for that input value.
ALGs are therefore considered as partial functions, meaning they do not have to be defined in all domains.
When a function can be calculated by algorithmic methods, the function is said to be computable, regardless of the amount of memory it occupies or the time it takes. Not all functions between data strings can be calculated.
As a measure of the efficiency of an ALG, the resources consumed by the system are examined. ALG analysis was developed to obtain values that somehow show the evolution of time and memory expenditure as a function of the size of the input values.
The analysis and study of ALGs is a discipline of computer science, and in most cases, its work is completely abstract without using any programming language or other applications.
Therefore, it shares the characteristics of mathematics disciplines in this sense. Therefore, the analysis of ALGs focuses on the basic principles of the ALG, not on a specific application.
One way to construct an ALG is to write it in pseudocode or use a very simple language such as Lexicon, whose code can be in the programmer’s language.
Some developers limit the definition of the ALG to procedures that must end at some point, while others consider procedures that can be executed endlessly, assuming there are some physical devices that can work forever.
In the second case, the successful completion of the ALG cannot be defined as its termination with satisfactory output.
However, success will be defined as a function of the output sequences delivered over a lifetime of running the ALG.
For example, a flowchart that verifies that there are multiple zeros in an infinite binary array must always be executed in order to return a useful value. If implemented correctly, the value returned by the system will be valid until it evaluates the next binary digit.
The output of this ALG is defined as the return of only positive values if there are multiple zeros in the array, and in any other case, it returns a mixture of positive and negative signals.
Until a solution is found, the most promising elements are applied and in most cases, the solution is not optimal.
They allow a problem to be divided into sub-problems so that they can be run on multiple processors simultaneously.
Some steps in this type of ALG are based on pseudo-random values.
The behavior of this method is linear and there are only one successor and one precursor step in each step.
The behavior of the ALG is tree-shaped, and each step can be branched into any number of steps immediately after it, and all branches are executed simultaneously.
Divide and Conquer
They divide the problem into separate subgroups, find a solution for each, and then combine them, thereby solving the entire problem.
It is based on the method of finding approximate non-optimal solutions to problems based on previous knowledge of the problems.
It tries to solve problems by increasing spatial costs and decreasing calculation costs.
Branching and Dimensioning
It is based on finding a solution to the problem by finding the best solutions and by means of an implicit tree that is passed in a controlled manner.
The solution area of the problem is based on the method of building in a fully studied tree that stores the cheapest solutions.