Computer science. Basics of algorithmization and programming

The concept of an algorithm is as fundamental to computer science as the concept of information. There are many different definitions of an algorithm, since this concept is quite broad and is used in various fields of science, technology and everyday life.

An algorithm is a clear and precise sequence of actions that describes the process of transforming an object from the initial state to the final state.

Performer The algorithm can be either a person (cooking recipes, various instructions, algorithms for mathematical calculations) or technical device. Various machines (computers, industrial robots, modern household appliances) are formal executors algorithms. A formal performer is not required to understand the essence of the problem being solved, but is required to accurately execute a sequence of commands.

The algorithm can be written different ways(verbal description, graphic description - block diagram, program in one of the programming languages, etc.). A program is an algorithm written in .

To create an algorithm (program), you need to know:

a complete set of initial task data (initial state of the object);

the purpose of creating the algorithm (the final state of the object);

the performer's command system (that is, a set of commands that the performer understands and can execute).

The resulting algorithm (program) must have the following set of properties:

discreteness (the algorithm is divided into separate steps - commands);

unambiguity (each command determines the only possible action of the performer);

clarity (all algorithm commands are included in the system of executor commands);

effectiveness (the performer must solve the problem in a finite number of steps).

Most algorithms also have the property mass character (using the same algorithm you can solve many similar problems).

It was noted above that the same algorithm can be written in different ways. You can write down the algorithm natural language. This is how we use recipes, instructions, etc. To record algorithms intended for formal performers, special programming languages. Any algorithm can be described graphically in the form of a block diagram. A special notation system has been developed for this purpose:

Designation	Description	Notes
	Start and end of the algorithm
	Data input and output.	Data output is sometimes referred to differently:
	Action	In computing algorithms this is used to denote assignment
	Fork	Fork - a component necessary to implement branches and loops
	Starting a loop with a parameter
	Typical process	In programming - procedures or subroutines
	Transitions between blocks

Let us give an example of a description of the algorithm for summing two quantities in the form of a block diagram:

This way of describing the algorithm is the most visual and understandable to humans. Therefore, formal executor algorithms are usually developed first in the form of a flowchart, and only then a program is created on one of them.

The programmer has the opportunity to construct and use atypical algorithmic structures, however, this is not necessary. Any algorithm, no matter how complex, can be developed based on three typical structures: following, branching and repetition. In this case, the structures can be located sequentially one after another or nested within each other.

Linear structure (following).

The simplest algorithmic structure is linear. In it, all operations are performed once in the order in which they are recorded.

Branching.

IN full branching There are two options for the performer's actions depending on the value of the logical expression (condition). If the condition is true, then only the first branch will be executed, otherwise only the second branch.

The second branch may be empty. This structure is called incomplete branching or bypass.

From several branches you can construct a structure “ choice"(multiple branching), which will choose not from two, but from more options for the performer's actions, depending on several conditions. It is important that only one branch is executed - in such a structure, the order of the conditions becomes important: if several conditions are met, then only one of them will work - the first one from the top.

Cycle (repetition).

Cycleallows you to organize multiple repetitions of the same sequence of commands- it is called the body of the cycle. In various types of cyclic algorithms, the number of repetitions can depend on the value of a logical expression (condition) or can be hard-coded in the structure itself. There are cycles: “ d O», « P oka», loops with a counter. In the “until” and “until” loops, a logical expression (condition) can precede the loop body ( loop with precondition) or end the loop ( loop with postcondition).

Cycles« d O» - repetition of the body of the cycle until the condition is met:

Cycles « P oka» - repetition of the body of the cycle while the conditionperformed ( true):

C Icons with counter (with parameter)– repeating the body of the loop a specified number of times:

Auxiliary algorithm (subroutine, procedure).

Auxiliary algorithm is a module that can be accessed repeatedly from the main algorithm. The use of auxiliary algorithms can significantly reduce the size of the algorithm and simplify its development.

Methods for developing complex algorithms.

There are two methods for developing complex algorithms:

Method of sequential task detailing(“top-down”) is that the original complex task is divided into subtasks. Each of the subtasks is considered and solved separately. If any of the subtasks are complex, they are also broken down into subtasks. The process continues until the subtasks are reduced to elementary ones. Solutions to individual subproblems are then combined into a single algorithm for solving the original problem. The method is widely used because it allows several programmers to simultaneously develop a general algorithm and solve local subproblems. This is a necessary condition for rapid software development.

Assembly method(“bottom-up”) consists in creating a variety of software modules that implement the solution of typical problems. When solving a complex problem, a programmer can use the developed modules as auxiliary algorithms (procedures). Many already have similar sets of modules, which significantly simplifies and speeds up the creation of a complex algorithm.

Control - purposeful interaction of objects, some of which are managers, others - managed.

In the simplest case, there are two such objects:

From a computer science point of view control actions can be considered as control information. Information can be transmitted in the form of commands. A sequence of commands to control an object leading to a predetermined goal is called control algorithm. Consequently, the control object can be called the executor of the control algorithm. In the example considered, the control object works “without looking” at what is happening with the control object ( control without feedback ). This control scheme is called open. Another control scheme can take into account information about the processes occurring in the control object:

In this case, the control algorithm must be flexible enough to analyze this information and make decisions about its further actions depending on the state of the control object ( feedback control). This control scheme is called closed.

Management processes are studied in more detail and discussed cybernetics. This science claims that the most diverse management processes in society, nature and technology occur in a similar way and are subject to the same principles.

Articles like “do programmers need algorithms” often appear, and they all have approximately the same template. The author of the article usually writes: “I have been writing websites/scripts in 1C for N years, and have never used algorithms or data structures. They immediately give examples of red-black trees or some other exotic structures, which in the area in which the author works are not often seen, if at all. Such articles boil down to the fact that in a particular area programmers do not use complex data structures and do not solve NP problems.

The very formulation of such a question is fundamentally incorrect. The number of specialties in the industry is constantly growing, and a person who writes websites on .net will do completely different things than a person who writes drivers for sensors on ARM architecture under an exotic OS. Let's first define what an algorithm is. Informally, Cormen defines an algorithm as a well-defined procedure that takes one or more values as input, and returns one or more values as a result. Formally, the algorithm is defined in different models computation: operations that can be performed on a Turing machine or using lambda calculus. So virtually any code that does something is an algorithm. It turns out that the question “does a programmer need algorithms” can be translated as “does a programmer need to be able to write code?” The correct question should be something like: “does a programmer in industry X need to know advanced algorithms and details of computational theory.”

If you look at all these articles, you will notice that the people who write them are actually offended by universities because they were forced to learn a lot of complex material - in the form of algorithmic analysis, complex algorithms and data structures - which did not seem to be useful to them . In fact, the authors of the articles are offended by universities because they were unable to predict the future field of work of the authors and give them only the minimum required set of skills. Indeed, in order to write simple websites and scripts, you do not need special knowledge of algorithms and data structures. Or is it still necessary?

Let's think about what a programmer needs to study at university in order to acquire the necessary skills for a successful career. Libraries? Frameworks? They become outdated, their interfaces change, they are all written most often in one language, which students may never use in the industry. Should we teach everyone how to write websites? Or teach everyone how to write an OS? Education should reach the widest possible audience and provide the widest possible range of skills. A programmer must first of all be able to analyze and solve problems - this is the main skill that computer science graduates should acquire. Writing code is simply a necessary tool that is used to solve problems. Who knows what skills you will need in the future? Thus, learning theory is the most optimal from an educational point of view. The acquired skills can be applied in any field, and you can learn a library or framework with good base knowledge will not be difficult. The paradox is that people who ask questions about the need for algorithms usually have some knowledge in this area. I do not remember a single person who did not have knowledge in the field of computational theory and proudly shouted about it, claiming that he did not need it.

So, you are an abstract programmer in a vacuum, you have been working for more than ten years putting together websites and solving simple, similar problems for clients/company. You feel good and comfortable in your niche, and only excruciatingly pain for wasted time in a class on computational theory and algorithmic analysis that gave you nothing. In the morning, while lighting a cigarette over a cup of coffee, in the depths of philosophical reflections on the frailty of existence, you wonder: why do programmers who do not solve complex problems need to know algorithms and the basics of analysis. Short answer: to be a qualified specialist and effectively use available tools, including the language in which you write. The theory of algorithms and analysis teaches not only exotic algorithms and data structures in the form of AVLs and red-black trees. It also gives ideas on how to effectively organize data, how to write code with maximum performance, where a bottleneck is possible in the system and how to deal with it. You are introduced to ready-made solutions so that you don’t write bicycles and don’t run to Google every time you need to do something non-trivial.

Knowledge of the theory of analysis and algorithms is actually used by all programmers every day, we’re just so used to these things that we don’t even think about it. Whatever problem you solve - be it a simple website with data fetching from a database, or a bash script on a server, you will use some kind of data structures. At least a primitive array, and most likely something more complex. Languages give us many different structures, many of which are used interchangeably. Often we have several variations of the same abstract type with different implementations. For example, C++ has vector and list data structures. How are they different, and what would be the advantages and disadvantages of using one or the other? How is map implemented in C++, and how does it differ from multimap? How is list implemented in Python - via an array or a linked list and what is the best way to work with it? Why is it not advisable to use an ArrayList in C# and instead use a List? How is SortedDictionary implemented and how will it affect program execution if used instead of Dictionary? How does continuation work, when should it be used, and are there any side effects when using it? When was the last time you used curried functions, which are found in almost every language? If you think that map in C++ is implemented as a hash table, you are wrong. It is implemented on red-black trees, and the hash table is implemented by unordered_map. Separately worth mentioning dynamic programming. Understanding what it is, how recursive functions can be rewritten optimally, and what memoization is will often help you avoid shooting yourself in the foot. Thus, just to fully and effectively use the language in which you write, you already need to have at least a superficial knowledge of data structures, what they are, and how they can affect the execution of your program.

What about libraries? After all, they solve so many problems! To use libraries efficiently, you also need to understand them. First, functions in libraries may have side effects or behavior that you wouldn't know without understanding the algorithms. Having received a bug in this case, you can try long and hard to catch it and decide when it could have been avoided. Secondly, various tools and libraries often need to be “customized” - told what algorithms, data structures and technologies to use internally. Without basic knowledge, you will have to either go read mana or choose at random. Thirdly, there are many problems that cannot be solved simple call Library or framework API. What will you do in this case? Spend hours searching possible solutions and ask a friend for help? Fourthly, many problems can be solved very simply with a few lines of code or built-in language tools. If you pull out a library to solve every problem, then your programs will be giant monsters, occupying hundreds of megabytes or more on disk, eating up all the memory on the server, and at the same time having rather meager functionality. In addition, the presence of a bunch of included libraries entails compatibility problems, and the program may crash randomly due to the strange behavior of several libraries in one project. Thoughtless use of libraries can lead to quite disastrous consequences, and developers who only know how to use libraries, but are not able to solve even simple problem on their own will never be valued because their solutions will not be competitive.

One programmer with more than ten years of experience worked with me. One day we needed a function that the library we used did not support at that time: a primitive text-wrap in one of the visual components. This “programmer” looked at what standard means this cannot be done, and immediately stated that the implementation of such a function is impossible. The problem was solved by a third-year intern with an analytical brain, who wrote a simple algorithm in two hours and implemented it in required component. I inherited another project in the form of a website on .net. The main page consisted of several small graphs and took almost 10 seconds to load. It turned out that the person who originally did this project piled up a bunch of terrible designs from triple nested loops, which took a long and sad time to take data from the database and then tie it to graphs. After some refactoring, the page loaded almost instantly.

Can a programmer do without knowledge of algorithms and analysis theory? Maybe there are a lot of such “programmers”. It would be a stretch to call them programmers. A lot of programmers come to me for interviews, with ten to fifteen years of experience, and not really understanding what they do and why. They have their own niche, they go from company to company, without staying in them for more than a year. As a rule, they have a small set of tasks that they can solve, and if you take a step to the side, then the person is lost and needs to teach himself new skills. Such people are invited to the project, and they get rid of them as quickly as possible, because they waste a lot of time reinventing wheels and reading mana to learn what they should have already known from university. As a rule, they do not have any particular career and unstable income.

In the end, why do you need to know algorithms and analysis theory if you can do the work without this knowledge? To be a qualified specialist in your profession, have career growth and respect from colleagues. To effectively solve problems and not reinvent the wheel. In order not to write monsters with a huge number of third-party libraries, which take up hundreds of megabytes on the disk, eat up a lot of memory on the server and regularly crash for a random reason depending on the phase of the moon. To use the language you write effectively and to the fullest extent possible. To make informed and meaningful decisions about the choice of library and technology to solve a problem. If your job is to write SQL query and typing a command into the console, then I want to disappoint you: you are not a programmer, you are a user, you really don’t need algorithms and the like, and you wasted your time at the university because for such work it is enough to complete courses or read a couple of introductory books yourself .

The first step to understanding the importance of studying and knowing algorithms is to accurately define what is meant by an algorithm. According to the popular book Algorithms: Construction and Analysis (Cormen, Leiserson, Rivest, Stein) “an algorithm is any well-defined computational procedure whose input is given a certain quantity or set of quantities, and the result of which is an output ( output) value or set of values." In other words, algorithms are like road maps for achieving a clearly defined goal. A piece of code for calculating members of the Fibonacci sequence is an implementation of a specific algorithm. Even a simple function of adding two numbers is an algorithm, albeit a simple one.

Some algorithms, such as those for calculating the Fibonacci sequence, are intuitive and relate to innate logical thinking and problem-solving skills. However, most of us would do well to learn complex algorithms so that in the future we can use them as building blocks to solve logic problems more efficiently. In fact, you might be surprised to learn how many complex algorithms people use when checking Email or listening to music. This article introduces some basic ideas of algorithm analysis, with practical examples illustrating the importance of studying algorithms.

Algorithm Execution Time Analysis

One of the most important aspects of the algorithm is its speed. It is often easy to come up with an algorithm problem solver, but if the algorithm is too slow, then it is returned for revision. Because the exact speed of an algorithm depends on where the algorithm runs, as well as implementation details, computer scientists usually talk about execution time relative to the input data. For example, if the input consists of N integers, then the algorithm may have a running time proportional to N 2 , which is represented as O(N 2 ). This means that if you run the implementation of the algorithm on a computer with an input of size N, it will take C*N 2 seconds, where C is some constant that does not change as the size of the input changes.

However, the execution time of many complex algorithms depends not only on the size of the input data, but also on many other factors. For example, an algorithm for sorting a set of integers can run much faster if the set is already sorted. It is customary to talk about the worst case of execution and the average case of execution. The worst-case execution time is the maximum running time of the algorithm with the “worst” of all possible inputs. The average execution case is the average running time of the algorithm for all possible inputs. Of these two types of execution time, the worst case is easiest to reason about and is therefore often used as a benchmark for a given algorithm. The process of determining the worst-case and average-case execution time of an algorithm can be quite complex because It is usually not possible to run the algorithm for all possible inputs.

Sorting

Sorting is good example an algorithm that is often used by programmers. The easiest way to sort a group of elements is to start by removing the smallest element from the group and putting it first. Then the second largest element is removed and placed second, and so on. Unfortunately, the running time of this algorithm is O(N 2), which means that it will take an amount of time proportional to the number of elements squared. If we had to sort billions of elements, then this algorithm would require 10 18 operations. If we assume that typical desktop PCs perform approximately 10 9 operations per second, then it will take years to finish sorting these billion elements.

Fortunately, there are a number of more advanced algorithms, such as quicksort, heapsort, and mergesort. These algorithms have a running time of O(N * Log(N)). Thus, the number of operations required to sort billions of elements is reduced to such reasonable limits that even the cheapest desktop PC can perform such sorting. Instead of a billion squared operations (10 18), these algorithms require only 10 billion operations (10 10), i.e. 100 million faster.

Shortest way

Algorithms for finding the shortest path from one point to another have been studied for many years. There are plenty of examples of applied applications of these algorithms, but for simplicity of presentation we will stick to the following statement: we need to find the shortest path from point A to point B in a city with several streets and intersections. There are many different algorithms for solving this problem and they all have their own advantages and disadvantages. Before we dive into them, let's look at the execution time of a simple brute-force algorithm. If an algorithm considers every possible path from A to B (which does not form cycles) it is unlikely to end in our lifetime, even if A and B are in a small town. The running time of this algorithm is exponential, which is denoted as O(C N) for some C. Even for small values of C, C N becomes an astronomical number when N becomes moderately large.

One of the fastest algorithms for solving this problem has a running time of O(E*V*Log(V)), where E is the number of road segments and V is the number of intersections. The algorithm will take about 2 seconds to find the shortest path in a city of 10,000 intersections and 20,000 road segments (usually about 2 road segments per intersection). This algorithm is known as Dijkstra's algorithm, it is quite complex and requires the use of a priority queue data structure. However, in some cases, even this execution time is too slow (take for example finding the shortest path from New York to San Francisco - there are millions of intersections in the USA), in such cases programmers try to improve the execution time using so-called heuristics. A heuristic is an approximation of something that is relevant to a task. In a shortest path problem, for example, it may be useful to know how far a point is from a destination. Knowing this, you can develop a faster algorithm (for example, the A* search algorithm in some cases works much faster than Dijkstra’s algorithm). This approach does not always improve the worst-case execution time of the algorithm, but in most cases real applications the algorithm starts working faster.

Approximate Algorithms

Sometimes even the most advanced algorithm with the most advanced heuristics is too slow on the fastest computer. In such cases, it is necessary to reduce the accuracy of the final result. Instead of trying to get the shortest path, you can limit yourself to a path that is, for example, 10% larger than the shortest path.

In fact, there are many important problems for which the currently known algorithms produce the optimal result too slowly. The most famous group of these problems is called NP (non-deterministic polynomial). If a problem is called NP-complete or NP-hard, it means that no one knows enough good way to obtain the optimal solution. Also, if someone develops an efficient algorithm for solving one NP-hard problem, then that algorithm can be applied to all NP-hard problems.

A good example of an NP-hard problem is the traveling salesman problem. A seller wants to visit N cities, and he knows how long it takes to travel from one city to another. The question is how quickly can he visit all the cities? The fastest known algorithm for solving this problem is too slow - and many believe it will always be - so programmers look for algorithms that are fast enough to give good decision, but often not optimal.

Random Algorithms

Another approach used to solve some problems is to make the algorithm random. This approach does not improve the algorithm's worst-case time, but quite often works well in the average case. The quicksort algorithm is a good example of the use of randomization. In the worst case, the quicksort algorithm sorts a group of elements in O(N 2), where N is the number of elements. If randomization is used in this algorithm, then the chances of a worst case become negligibly small, and on average the quicksort algorithm runs in O(N*Log(N) time). Other algorithms even guarantee O(N*Log(N)) running time in the worst case, but are slower in the average case. Although both algorithms have a running time proportional to N*Log(N), the quicksort algorithm has a smaller constant factor - i.e. it requires C*N*Log(N), while other algorithms require more than 2*C*N*Log(N) operations.

Another algorithm using random numbers searches for the median of a group of numbers and its average running time is O(N). This is much faster compared to the algorithm that sorts the numbers and takes the average, and runs in O(N*Log(N)). There are deterministic algorithms (not random) that can find the median in O(N) time, but the random algorithm is easier to understand and often faster than these deterministic algorithms.

The main idea of the median search algorithm is to select a random number among the numbers and count how many numbers in the group are less than the selected number. Let's say there are N numbers, K of them are less than or equal to the selected number. If K is less than half N, then we know that the median is the (N/2-K)th number that is greater than the random number, so we discard K numbers less than or equal to the random number. Now let's say we want to find the (N/2-K)th smallest number, instead of the median. The algorithm is the same, we just randomly select a number and repeat the steps described.

Compression

Another class of algorithms is designed for data compression. This algorithm does not have an expected result (like a sorting algorithm), but instead optimizes according to some criteria. In the case of data compression, an algorithm (for example, LZW) tries to make the data occupy as few bytes as possible, but at the same time, so that it can be decompressed to its original form. In some cases, this type of algorithm uses the same techniques as other algorithms, resulting in good result, but not optimal. For example, JPG and MP3 compress data in such a way that the final result is lower quality than the original, but also smaller in size. MP3 compression does not preserve every feature of the original audio file, but it attempts to preserve enough detail to provide acceptable quality while significantly reducing file size. The JPG format follows the same principle, but the details are significantly different because... the goal is to compress the image, not the audio.

Why is it so important to know algorithms?

To use algorithms properly, it is important to know all the mentioned types of algorithms. If you have to develop an important part software, then you should be able to estimate the speed of your algorithm. The accuracy of your estimate depends on how proficient you are in analyzing the execution time of algorithms. In addition, it is necessary to know the details of the algorithms, which will allow us to predict special cases in which the program will not work quickly or will produce unacceptable results.

Of course, there will be times when you stumble upon previously unexplored problems. In such cases, you need to come up with a new algorithm, or apply the old algorithm in a new way. The more you know about algorithms, the more likely you are to find a good solution to a problem. In many cases new task can easily be reduced to the old one, but to do this you need to have a fundamental understanding of the old problems.

As an example, consider how network switches work. The switch has N cables connected to it, and receives data packets arriving through these cables. The switch must first parse the packets and then send them back over the correct cable. A switch, like a computer, operates in discrete mode - packets are sent at discrete intervals, rather than continuously. A fast switch strives to send as many packets as possible during each interval, otherwise they will accumulate and the switch will crash. The purpose of the algorithm is to send maximum amount packets during each interval, and also ensure the order in which packets that arrived earlier than others were also sent earlier than others. In this case, it turns out that an algorithm known as “stable matching” is suitable for solving this problem, although at first glance this may not be obvious. Such connections between problem and solution can only be discovered using already existing algorithmic knowledge.

Real examples

Examples of solutions to real problems requiring the latest algorithms plenty. Almost everything you do on a computer depends on algorithms that someone spent a long time developing. Even the most simple programs would not exist without the algorithms that work behind the scenes to manage memory and load data from the hard drive.

There are dozens of examples of the use of complex algorithms, but we will discuss two problems whose solution requires the same skills as solving some problems on TopCoder. The first problem is known as the maximum flow problem, and the second involves dynamic programming, a technique that can often solve problems at seemingly impossible lightning speeds.

Articles like “do programmers need algorithms” often appear, and they all have approximately the same template. The author of the article usually writes: “I have been writing websites/scripts in 1C for N years, and have never used algorithms or data structures. They immediately give examples of red-black trees or some other exotic structures, which in the area in which the author works are not often seen, if at all. Such articles boil down to the fact that in a particular area programmers do not use complex data structures and do not solve NP problems.

The very formulation of such a question is fundamentally incorrect. The number of specialties in the industry is constantly growing, and a person who writes websites on .net will do completely different things than a person writing drivers for sensors on ARM architecture under an exotic OS. Let's first define what an algorithm is. Informally, Cormen defines an algorithm as a well-defined procedure that takes one or more values as input, and returns one or more values as a result. Formally, an algorithm is defined in different models of computation: operations that can be performed on a Turing machine or using lambda calculus. So virtually any code that does something is an algorithm. It turns out that the question “does a programmer need algorithms” can be translated as “does a programmer need to be able to write code?” The correct question should be something like: “does a programmer in industry X need to know advanced algorithms and details of computational theory.”

Let's think about what a programmer needs to study at university in order to acquire the necessary skills for a successful career. Libraries? Frameworks? They become outdated, their interfaces change, they are all written most often in one language, which students may never use in the industry. Should we teach everyone how to write websites? Or teach everyone how to write an OS? Education should reach the widest possible audience and provide the widest possible range of skills. A programmer must first of all be able to analyze and solve problems - this is the main skill that computer science graduates should acquire. Writing code is simply a necessary tool that is used to solve problems. Who knows what skills you will need in the future? Thus, learning theory is the most optimal from an educational point of view. The acquired skills can be applied in any field, and learning a library or framework with a good knowledge base will not be difficult. The paradox is that people who ask questions about the need for algorithms usually have some knowledge in this area. I do not remember a single person who did not have knowledge in the field of computational theory and proudly shouted about it, claiming that he did not need it.

So, you are an abstract programmer in a vacuum, you have been working for more than ten years putting together websites and solving simple, similar problems for clients/company. You feel good and comfortable in your niche, and only excruciatingly pain for wasted time in a class on computational theory and algorithmic analysis that gave you nothing. In the morning, while lighting a cigarette over a cup of coffee, in the depths of philosophical reflections on the frailty of existence, you wonder: why do programmers who do not solve complex problems need to know algorithms and the basics of analysis. The short answer is to be skilled and effectively use the tools available, including the language in which you write. The theory of algorithms and analysis teaches not only exotic algorithms and data structures in the form of AVLs and red-black trees. It also provides insight into how to organize data effectively, how to write code for maximum performance, where bottlenecks may occur in the system, and how to deal with them. You are introduced to ready-made solutions so that you don’t write bicycles and don’t run to Google every time you need to do something non-trivial.

Knowledge of the theory of analysis and algorithms is actually used by all programmers every day, we’re just so used to these things that we don’t even think about it. Whatever problem you solve - be it a simple website with data fetching from a database, or a bash script on a server, you will use some kind of data structures. At least a primitive array, and most likely something more complex. Languages give us many different structures, many of which are used interchangeably. Often we have several variations of the same abstract type with different implementations. For example, C++ has vector and list data structures. How are they different, and what would be the advantages and disadvantages of using one or the other? How is map implemented in C++, and how does it differ from multimap? How is list implemented in Python - via an array or a linked list and what is the best way to work with it? Why is it not advisable to use an ArrayList in C# and instead use a List? How is SortedDictionary implemented and how will it affect program execution if used instead of Dictionary? How does continuation work, when should it be used, and are there any side effects when using it? When was the last time you used curried functions, which are found in almost every language? If you think that map in C++ is implemented as a hash table, you are wrong. It is implemented on red-black trees, and the hash table is implemented by unordered_map. Dynamic programming is worth mentioning separately. Understanding what it is, how recursive functions can be rewritten optimally, and what memoization is will often help you avoid shooting yourself in the foot. Thus, just to fully and effectively use the language in which you write, you already need to have at least a superficial knowledge of data structures, what they are, and how they can affect the execution of your program.

What about libraries? After all, they solve so many problems! To use libraries efficiently, you also need to understand them. First, functions in libraries may have side effects or behavior that you wouldn't know without understanding the algorithms. Having received a bug in this case, you can try long and hard to catch it and decide when it could have been avoided. Secondly, various tools and libraries often need to be “customized” - told what algorithms, data structures and technologies to use internally. Without basic knowledge, you will have to either go read mana or choose at random. Thirdly, there are many problems that cannot be solved by simply calling the API of a library or framework. What will you do in this case? Spending hours searching for possible solutions and asking a friend for help? Fourthly, many problems can be solved very simply with a few lines of code or built-in language tools. If you pull out a library to solve every problem, then your programs will be giant monsters, occupying hundreds of megabytes or more on disk, eating up all the memory on the server, and at the same time having rather meager functionality. In addition, the presence of a bunch of included libraries entails compatibility problems, and the program may crash randomly due to the strange behavior of several libraries in one project. Thoughtless use of libraries can lead to quite disastrous consequences, and developers who only know how to use libraries but are unable to solve even a simple problem on their own will never be valued because their solutions will not be competitive.

One programmer with more than ten years of experience worked with me. One day we needed a function that the library we used did not support at that time: a primitive text-wrap in one of the visual components. This “programmer” saw that this could not be done using standard means, and immediately declared that the implementation of such a function was impossible. The problem was solved by a third-year intern with an analytical brain, who wrote a simple algorithm in two hours and implemented it into the required component. I inherited another project in the form of a website on .net. The main page consisted of several small graphs and took almost 10 seconds to load. It turned out that the person who originally did this project piled up a bunch of terrible designs from triple nested loops, which took a long and sad time to take data from the database and then tie it to graphs. After some refactoring, the page loaded almost instantly.

In the end, why do you need to know algorithms and analysis theory if you can do the work without this knowledge? To be a qualified specialist in your profession, have career growth and respect from colleagues. To effectively solve problems and not reinvent the wheel. In order not to write monsters with a huge number of third-party libraries, which take up hundreds of megabytes on the disk, eat up a lot of memory on the server and regularly crash for a random reason depending on the phase of the moon. To use the language you write effectively and to the fullest extent possible. To make informed and meaningful decisions about the choice of library and technology to solve a problem. If your job is to write an SQL query and enter a command into the console, then I want to disappoint you: you are not a programmer, you are a user, you really don’t need algorithms and the like, and you wasted your time at the university because for such work It is enough to complete the courses or read a couple of introductory books on your own.

To write applications different levels complexity, you first need to gain knowledge of how this is done. And it is advisable to start with the very basics of algorithmization and programming. We will talk about them in the article.

This is the name of a complex technical science, the task of which is to systematize the methods of creating, processing, transmitting, storing and reproducing data using It also includes operating principles and management methods that help achieve the goal. The term “computer science” itself is of French origin and is a hybrid of the words “information” and “automation”. It arose thanks to the development and dissemination of new technologies for collecting, processing and transmitting data, which were associated with their recording on computer media. This is the origin of computer science. The basics of algorithmization and programming are one of the most important areas of this science.

What does she do?

Computer science faces the following challenges:

Hardware and software support for computer technology.
Means for ensuring interaction between humans and computer components.

The term “interface” is often used to refer to the technical part. Here we have a free program. The basics of algorithmization and programming are always used when creating products for mass distribution that “should” win a wide audience. After all, to be popular, the application being developed must work and look optimal.

Presentation of Algorithms

They can be written in a significant number of ways. The most popular are the following:

Verbal and formulaic description. This implies the placement of text and specific formulas that will explain the features of interaction in all individual cases.
Block diagram. Availability is implied graphic symbols, which make it possible to understand the features of the program’s interaction within itself and with other applications or computer hardware. Each of them can be responsible for a separate function, procedure or formula.
This implies the creation of separate methods of description for specific cases, which show the features and order of tasks.
Operator diagrams. This involves creating a prototype - it will show the interaction based on the paths that individual operands will take.

Pseudocode. Sketch of the skeleton of the program.

Recording the algorithm

How to start creating your own prototype of a program, function or procedure? To do this, it is enough to use these general recommendations:

Each algorithm must have its own name, which explains its meaning.
Be sure to make sure there is a beginning and an end.
Input and output data must be described.
You should specify the commands that will be used to perform certain actions on specific information.

Recording methods

There can be as many as five representations of the algorithm. But there are only two ways to write:

Formal-verbal. It is characterized by the fact that the description is made mainly using formulas and words. The content, as well as the sequence of execution of the stages of the algorithm, in this case is written in natural professional language in free form.
Graphic. The most common. It uses block symbols or algorithm diagrams. The connection between them is shown using special lines.

We develop a program structure

There are three main types:

Linear. With this structure, all actions are performed sequentially in order and only once. The diagram looks like a sequence of blocks, arranged from top to bottom, depending on the order in which they are executed. The resulting primary and intermediate data cannot influence the direction of the computational process.
Branching. It has found wide application in practice when solving complex problems. Thus, if it is necessary to take into account initial conditions or intermediate results, then the necessary calculations are performed in accordance with them and the direction of the computational process can change depending on the result obtained.

Cyclical. To make it easier for you to work with many tasks, some areas program code It makes sense to repeat it many times. In order not to prescribe how many times and what needs to be done, a cyclic structure is used. It provides for a sequence of commands that will be repeated until a given condition is met. The use of loops allows you to greatly reduce the complexity of writing a program.

Programming

It is important on which programs will be created. It should be noted that many of them are “tailored” to specific operating conditions (for example, in a browser). In general, programming languages are divided into two groups:

Functional.
Operator rooms:

Not procedural;

Procedural.

Can you guess which ones are most often used? Operator-procedural - that's the answer. They can be machine-centric or independent. The first include assemblers, autocodes, and symbolic coding. Independents divide based on their orientation:

procedural;
problematic;
object.

Each of them has its own scope of application. But to write programs (useful applications or games), object-oriented languages are most often used. Of course, you can use others, but the fact is that they are the most developed for creating final consumer products for the masses. Yes, and if you don’t yet have an exact vision of where to start, I suggest you pay attention to the basics of algorithmization and object-oriented programming. Now this is a very popular direction where you can find a lot of educational material. In general, the basics of algorithmization and programming languages are now needed due to the fact that there is a shortage of qualified developers, and their importance will only grow in the future.

Conclusion

When working with algorithms (and subsequently with programs), you should strive to think through all the details down to the smallest. Subsequently, identifying each undeveloped section of code will only lead to additional work, increasing development costs and task completion times. Careful planning and elaboration of all the nuances will significantly save time, effort and money. Well, now they can say that after reading this article you have an understanding of the basics of algorithmization and programming. All that remains is to apply this knowledge. If you want to study the topic in more detail, I can recommend the book “Fundamentals of Algorithmization and Programming” (Semakin, Shestakov) 2012.