Informatics. Basics of algorithmization and programming

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 roadmaps for achieving a clearly defined goal. A piece of code to calculate the terms of the Fibonacci sequence - this is the implementation 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 for more efficient solving of logic problems. In fact, you might be surprised to learn how many complex algorithms people use when checking email or listening to music. This article presents some basic ideas for analyzing algorithms with practical examples, illustrating the importance of learning 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 on all possible inputs. Of these two types of execution time, the worst case is easiest to reason about and is therefore used more often 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 path

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 to solve this problem and all of them 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 real-world applications the algorithm will run faster.

Approximate Algorithms

Sometimes even the most advanced algorithm with the most advanced heuristics is too slow in reality fast 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 to solve 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 guarantee O(N*Log(N)) running time even in the worst case, but they 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 of N, then we know that the median is the (N/2-K)th number that is greater than a random number, so we discard K numbers less than or equal to 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 methods as other algorithms, resulting in a 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, a new problem can easily be reduced to an 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 goal of the algorithm is to send the maximum number of packets during each interval, and also to ensure an order in which packets that arrive earlier than others are 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 existing algorithmic knowledge.

Real examples

There are plenty of examples of solutions to real problems that require the latest algorithms. 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.

Knuth-Morris-Pratt algorithm

The Knuth-Morris-Pratt (KMP) algorithm receives the word X=xx... x[n] as input and scans it from left to right letter by letter, filling in the array of natural numbers l... l[n], where l[ i]=word length l(x...х[i]) (function l is defined in the previous paragraph). In words: l[i] is the length of the longest beginning of the word x...x[i], which is also its end.

What does all this have to do with subword searching?

In other words, how do you use the KMP algorithm to determine whether word A is a subword of word B?

Solution. Let's apply the KMP algorithm to the word A#B, where # is a special letter that is not found in either A or B. The word A is a subword of the word B if and only if among the numbers in the array l there is a number equal to the length of the word A.

Describe the algorithm for filling the table l...l[n].

Solution. Let's assume that the first i values ​​l...l[i] have already been found. We read the next letter of the word (i.e. x) and must calculate l.

In other words, we are interested in the beginning Z of the word x...x . The word Z" is the beginning and end of the word x...x[i]. However, not any word that is the beginning and end of the word x...x[i] is suitable - it must be followed by the letter x.

We get the following recipe for finding the word Z. Consider all the beginnings of the word x...x[i], which are also its ends. From them we will select the suitable ones - those followed by the letter x. From those that are suitable, we will choose the longest one. By adding x to its end, we get the desired word Z. Now it’s time to use the preparations we have made and remember that all words that are both the beginning and the end of a given word can be obtained by repeatedly applying the function l from the previous section to it.

Here's what happens:

(table l..l[i] is filled out correctly)

while i<>n do begin

(len is the length of the beginning of the word x..x[i], which is

its end; increasingly longer beginnings turned out to be

unsuitable)

while(x<>x) and (len>0) do begin

if x=x do begin

(x..x is the longest suitable beginning)

(no suitable ones)

Prove that the number of actions in the algorithm just given does not exceed Cn for some constant C.

Solution. This is not entirely obvious: processing each successive letter may require many iterations in the inner loop. However, each such iteration reduces len by at least 1, in which case l will be noticeably smaller than l[i]. On the other hand, when i increases by one, the value of l[i] can increase by no more than 1, so it cannot decrease often or greatly - otherwise the decrease will not be compensated by the increase.

More precisely, we can write the inequality

l

(number of iterations at the i-th step)<= l[i]-l+1

It remains to add these inequalities over all i and obtain an upper bound for the total number of iterations.

We will use this algorithm to find out whether a word X of length n is a subword of a word Y of length m. (How to do this using the special # separator is described above.) In this case, the number of actions will be no more than C(n+m), and the memory used will also be used. Figure out how to use a memory of no more than Cn (which can be significantly less if the searched pattern is short and the word in which it is searched is long).

Solution. We apply the KMP algorithm to the word A#B. In this case: we calculate the values ​​l,...,l [n] for a word X of length n and remember these values. Next, we remember only the value of l[i] for the current i - besides it and besides the table

l...l[n], we don’t need anything for calculations.

In practice, words X and Y may not be in a row, so it is convenient to view word X and then word Y as separate loops. This also eliminates the hassle of using a separator.

Write an appropriate algorithm (checking whether the word X=x...x[n] is a subword of the word Y=y...y[m]

Solution. First we calculate the table l...l[n] as before. Then we write the following program:

(len - length of the maximum download of word X, at the same time

which is the end of the word y..j[j])

while (len<>n) and (j<>m) do begin

while(x<>y) and (len>0) do begin

(the beginning is not suitable, apply the l function to it)

(found a suitable one or were convinced of its absence)

if x=y do begin

(x..x is the longest suitable start)

(no suitable ones)

(if len=n, the word X was encountered; otherwise we reached the end

word Y without ever meeting X)

Boyer-Moore algorithm

This algorithm does what at first glance seems impossible: in a typical situation, it reads only a small part of all the letters of the word in which a given pattern is searched. How can this be? The idea is simple. Let, for example, we are looking for the pattern abcd. Let's look at the fourth letter of the word: if, for example, it is the letter e, then there is no need to read the first three letters. (In fact, the pattern doesn't have an e, so it can't begin until the fifth letter.)

We will present the simplest version of this algorithm, which does not guarantee fast operation in all cases. Let x...x[n] be the pattern to look for. For each character s, we find its rightmost occurrence in the word X, that is, the largest k for which x[k]=s. We will store this information in the pos[s] array; if the symbol s does not occur at all, then it will be convenient for us to set pos[s]=0 (we will see why later).

How to fill the pos array?

set all pos[s] equal to 0

for i:=1 to n do begin

During the search process, we will store in the last variable the number of the letter in the word opposite which the last letter of the sample appears. At first last=n (sample length), then last gradually increases.

(all previous positions of the sample have already been checked)

while last<= m do begin {слово не кончилось}

if x[m]<>y then begin (last letters are different)

last:=last+(n-pos]);

(n - pos] is the minimum sample shift,

at which opposite y there will be the same

letter in the sample. If there is no such letter at all,

then we shift it along the entire length of the sample)

if the current situation is suitable, i.e. If

x[i]..х[n]=y..y,

then report a match;

Experts recommend checking for matches from right to left, i.e. starting from the last letter of the sample (in which there is obviously a match). You can also save a little by doing the subtraction in advance and storing not pos[s], but n-pos[s],

those. the number of letters in the pattern to the right of the last occurrence of the letter. Various modifications of this algorithm are possible. For example, you can have the line

replace with

last:=last+(n-u),

where u is the coordinate of the second occurrence of the letter x[n] from the right in the pattern.

What is the easiest way to take this into account in the program?

Solution. When constructing the table pos write

write

last:=last+n-pos];

The presented simplified version of the Boyer-Moore algorithm in some cases requires significantly more n actions (the number of actions is of the order of mn), losing to the Knuth-Morris-Pratt algorithm.

An example of a situation in which the pattern is not included in the word, but the algorithm requires about mn actions to establish this.

Solution. Let the sample look like baaa... aa, and the word itself consists only of the letters a. Then at each step the discrepancy is clarified only at the last moment.

The real (not simplified) Boyer-Moore algorithm guarantees that the number of actions does not exceed C(m+n) in the worst case. It uses ideas close to those of the Knuth-Morris-Pratt algorithm. Let's imagine that we compared the sample with the input word, going from right to left. In this case, some piece of Z (which is the end of the sample) coincided, and then a difference was discovered: the Z in the sample is preceded by something different from the one in the input word. What can be said at this moment about the input word? It contains a fragment equal to Z, and the letter in front of it is not the same as in the sample. This information can allow a pattern to be shifted a few positions to the right without the risk of missing its occurrence. These shifts should be calculated in advance for each Z end of our sample. As experts say, all this (calculating the shift table and using it) can be done in C(m+ n) actions.

Rabin's algorithm

This algorithm is based on a simple idea. Let's imagine that in a word of length m we are looking for a pattern of length n. Let's cut out a window of size n and move it along the input word. We are interested in whether the word in the box matches the given pattern. It takes a long time to compare letters. Instead, we fix some function defined on words of length n. If the values ​​of this function on the word in the box and on the sample are different, then there is no coincidence. Only if the values ​​are the same should you check for a letter-by-letter match.

What is the gain with this approach? It would seem nothing - after all, in order to calculate the value of a function on a word in a window, you still need to read all the letters of this word. So it’s better to immediately compare them with the sample. Nevertheless, winning is possible, and here’s why. When you move the window, the word does not change completely, but only a letter is added at the end and removed at the beginning. It would be nice if this data could be used to calculate how the function changes.

Give an example of a function convenient for calculation.

Solution. Let's replace all the letters in the word and pattern with their numbers, which are integers. Then a convenient function is the sum of the digits. (When you move the window, you need to add a new number and subtract the missing one.)

For every function there are words to which it is poorly applicable. But another function in this case may work well. An idea arises: you need to store a lot of functions and select a random one from them at the beginning of the algorithm. (Then the enemy who wants to mess with our algorithm will not know which function to fight.)

Give an example of a family of convenient functions.

Solution. Let's choose some number p (preferably prime, see below) and some residue x modulo p. We will consider each word of length n as a sequence of integers (replacing letters with codes). We will consider these numbers as coefficients of a polynomial of degree n-1 and calculate the value of this polynomial mod p at point x. This will be one of the functions of the family (for each pair p and x, therefore, its own function is obtained). Shifting the window by 1 corresponds to subtracting the leading term (xn-1 should be calculated in advance), multiplying by x and adding the dummy term.

The next consideration suggests that coincidences are not very likely. Let the number p be fixed and also prime, and X and Y be two different words of length n. Then they correspond to different polynomials (we assume that the codes of all letters are different - this is possible if p is greater than the number of letters of the alphabet). The coincidence of function values ​​means that at point x these two different polynomials coincide, that is, their difference becomes 0. The difference is a polynomial of degree n-1 and has no more than n-1 roots. Thus, if u is much less than p, then random x has little chance of hitting the wrong point.

Similar documents

Theoretical information. Basic concepts. String, its length, substring. The concept of algorithm complexity. Algorithms based on the sequential search method. Algorithms of Rabin, Knuth - Morris - Pratt, Boyer - Moore.

course work, added 06/13/2007


Organization of the ability to view text files and search for the necessary words in the text. Editing text (font, size). Algorithm for searching a substring in a string (Knuth-Morris-Pratt method). Loading text from a file (with extension .txt).

course work, added 05/29/2013


Search in arrays and lists, key and arbitrary data. Linear (sequential) search. Binary search in an ordered array. Rabin-Karp algorithm, a simple and improved hash function. Boyer-Moore algorithm with shift by stop characters and suffixes.

presentation, added 10/19/2014


Study of the concept of an algorithm, features of linear and branching algorithms. Properties of the algorithm: understandability, accuracy, discreteness, mass production and effectiveness. Drawing up a program to calculate the value of a function and plotting its graph.

test, added 03/25/2013


Study of the definition, description and call of functions, pointers and references to them. Writing a function to multiply an arbitrary column of a two-dimensional array by const. Multiplying 2 array columns by constants. Drawing up a block diagram of the algorithm and program text.

laboratory work, added 01/09/2012


Basic properties of the algorithm. The formal and informal executor of the algorithm, the system of its commands. Methods for writing an algorithm. Verbal description, line-by-line recording, supporting summary. Characteristics of an algorithmic language. Execution of the algorithm by a computer.

presentation, added 04/04/2014


Theoretical and practical aspects of solving applied problems using functions and procedures of structured (modular) programming. Features of the development of an algorithm scheme and a program for calculating an array z in the Turbo Pascal 7.0 language, their description.

course work, added 12/11/2009


Characteristics of the implementation features of array search using linear, binary, Fibonace tree and extrapolar methods using the Turbo Pascal language program. Adaptation of the Rabin-Karp and Knuth-Morris-Pratt algorithm for finding a row in a row.

course work, added 09/16/2010


Description of the operating principle of a genetic algorithm, testing its operation for functions according to the option based on a ready-made program. Basic parameters of the genetic algorithm, its structure and content. Methods for implementing the algorithm and its components.

laboratory work, added 12/03/2014


Development in assembly language of a control algorithm using a cyclic CRC code for a data array stored in a certain memory area. Saving code for subsequent periodic checking of the data array. Data corruption message. Description of the algorithm.

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.”

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 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 do not write bicycles and do not 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 ArrayList in C# and use List instead? 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 implementing 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.

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, to 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.

2.4.1. The concept of basic algorithms

2.4.2. Linear structure algorithms

2.4.3. Basic algorithms for branching structures and examples of their programming

2.4.4. Basic algorithms for regular cyclic structures and examples of their programming

2.4.5. Basic algorithms for iterative cyclic structures and examples of their programming

2.4.6. Basic algorithms for processing one-dimensional arrays

2.4.7. Basic algorithms for processing two-dimensional arrays

2.4.8. Test questions on the topic “Basic algorithms and examples of their implementation”

2.4.9. Test tasks on the topic “Basic algorithms and examples of their implementation”

2.4.1. The concept of basic algorithms

Basic data processing algorithms are the result of decades of research and development. But they continue to play an important role in the expanding use of computing processes.

The basic imperative programming algorithms include:

The simplest algorithms implementing basic algorithmic structures.

Algorithms working with data structures. They define the basic principles and methodology used to implement, analyze, and compare algorithms. Provides insight into data presentation methods. Such structures include linked lists and strings, trees, and abstract data types such as stacks and queues.

Algorithms sorting, designed to organize arrays and files, are of particular importance. Related to sorting algorithms are priority queues, selection problems, and merging problems.

Algorithms search, designed to find specific elements in large collections of elements. These include basic and advanced search methods using trees and digital key transformations, including digital search trees, balanced trees, hashing, and methods that are suitable for working with very large files.

Graph Algorithms useful in solving a number of complex and important problems. A general graph search strategy is developed and applied to fundamental connectivity problems, including shortest path, minimum spanning tree, network flow, and matching problems. The unified approach to these algorithms shows that they are based on the same procedure, and that this procedure is based on the underlying abstract priority queue data type.

Algorithms string processing include a number of methods for processing (long) character sequences. Searching a string leads to pattern matching, which in turn leads to parsing. File compression technologies can also be attributed to this class of tasks.

2.4.2. Linear structure algorithms

Example 2.4.2-1.

where x = -1.4; y = 0.8; variables k and k are of integer type, the remaining variables are of real type; [n] is the integer part of the number n.

The diagram of the algorithm and programs in the languages ​​QBasic, Pascal, C++ are presented in Fig. 2.4.2-1.

Please note that the integer variable k received a rounded value n, and the integer variable m- truncated using a function FIX() to the whole part of the value n.

Example 2.4.2-2. Calculate and display the following quantities:

where x = 2.9512; y = 0.098633; variables i and j are of integer type; the remaining variables are of real type.

The algorithm diagram and program codes are presented in Fig. 3.2.1-2.

Rice. 2.4.2-2.

The results of executing the program with the above values ​​of the initial data have the following form:

Example 2.4.2-3. Calculate and display the value of the first escape velocity.

Let's formalize it. The minimum speed at which a spacecraft in the Earth's gravitational field can become an artificial satellite is equal to

where is the gravitational constant; M – mass of the Earth;
– distance from the center of the Earth to the spacecraft.

The algorithm diagram and program codes are presented in Fig. 3.2.1-3.

Rice. 2.4.2-3.

The results of executing the program with the above values ​​of the initial data have the following form.

Any process management requires certain rules and clear actions. A computer is a device designed to automate the creation, storage, processing and transmission of data, which means that clear instructions must be followed to perform a particular task.

To create programs designed to solve a problem on a computer, it is necessary to draw up an algorithm for solving it.

Algorithms, for example, are the rules of addition, multiplication, solving algebraic equations, matrix multiplication, etc. The word algorithm comes from algoritmi, which is a Latin transliteration of the Arabic name of the 9th century Khwarezmian mathematician al-Khwarizmi. Thanks to the Latin translation of al-Khwarizmi's treatise, Europeans in the 12th century became acquainted with the positional number system, and in medieval Europe the algorithm was called the decimal positional number system and the rules of counting in it.

In other words, an algorithm is a precise instruction, and instructions are found in almost all areas of human activity. Algorithms for conducting a physical experiment, assembling a cabinet or TV, or processing a part are possible. However, not every instruction is an algorithm.

An instruction becomes an algorithm only when it satisfies certain requirements. One of the requirements of the algorithm is unambiguity, i.e. if when applied to the same data it will give the same result.

In relation to a computer, the algorithm allows you to formalize a computational process that begins with processing a certain set of possible initial data and is aimed at obtaining results determined by these initial data. The term computing process also extends to the processing of other types of information, for example, symbolic, graphic or audio.

If the computational process ends with obtaining results, then the algorithm is said to be applicable to the considered set of initial data. Otherwise, they say that the algorithm is not applicable to the set of initial data. Any applicable algorithm has the following basic properties:

· discreteness;

· certainty;

· effectiveness;

· mass character.

Discreteness – sequential execution of simple or previously defined (subroutine) steps. The transformation of source data into results is carried out discretely in time.

Certainty consists in the coincidence of the results obtained, regardless of the user and the technical means used (unambiguous interpretation of instructions).

Efficiency means the possibility of obtaining a result after performing a finite number of operations.

Mass character lies in the possibility of applying the algorithm to a whole class of similar problems that differ in specific values ​​of the initial data (development in general form).

To specify an algorithm, it is necessary to describe its following elements:

· a set of objects that make up the totality of possible initial data, intermediate and final results;

· start rule;

· the rule of direct processing of information (description of the sequence of actions);

· ending rule;

· rule for extracting results.

The algorithm is always designed for a specific performer. In our case, such a performer is a computer. To ensure the possibility of implementation on a computer, the algorithm must be described in a language understandable to the computer, that is, in a programming language.

The concepts of algorithm and program are not very clearly delineated. Typically, a program is the final version of an algorithm for solving a problem, oriented towards a specific user.

Thus, we can give the following definition of a computer program:

The main ways to describe algorithms include the following:

· verbal-formular (in natural language);

· structural or block diagram;

· using special algorithmic languages;

· using graph diagrams (a graph is a collection of points and lines in which each line connects two points. The points are called vertices, the lines are called edges).

Before compiling programs, they most often create an algorithm for solving a given problem using one of the methods described above.

At verbally-formulaic way the algorithm is written in the form of text with formulas for the points that make up the sequence of actions.

Let, for example, you need to find the value of the following expression:

y = 4a – (x + 3).

In a verbal and formulaic way, the algorithm for solving this problem can be written in the following form:

1. Enter the values ​​of a and x.

2. Add x and 3.

3. Multiply a by 4.

4. Subtract the sum (x+3) from 4a.

5. Output y as the result of evaluating the expression.

At block-schematic description the algorithm is depicted by geometric figures (blocks) connected by control lines (flow directions) with arrows. The blocks record a sequence of actions.

This type of recording of the algorithm has the greatest advantages. It is the most visual: each operation of the computational process is depicted as a separate geometric figure. In addition, the graphical representation of the algorithm clearly shows the ramifications of ways to solve the problem depending on various conditions, the repetition of individual stages of the computational process and other details.

The design of programs must meet certain requirements (Fig. 2.). Currently, there is a unified system of program documentation (USPD), which establishes the rules for the development, execution of programs and program documentation. The ESPD also defines the rules for the design of flowcharts of algorithms (GOST 10.002-80 ESPD, GOST 10.003-80 ESPD).

One of the properties of the algorithm is discreteness, i.e. presentation of the calculation process into individual steps and the allocation of individual sections of the program to certain structures.

Any computing process can be represented as a combination of elementary algorithmic structures:

· Following. Assumes sequential execution of commands from top to bottom. If an algorithm consists only of sequence structures, then it is linear.

· Branching. The program execution proceeds along one of two, several or many branches. The choice of branch depends on the condition at the branch input and the data received here.

· Cycle. Assumes the possibility of repeated repetition of certain actions. The number of repetitions depends on the cycle condition.

· Function (subroutine). Commands separated from the main program are executed only if they are called from the main program (from anywhere in it). The same function can be called from the main program as many times as desired.

There are three main types of algorithms:

Modern programming systems usually provide users with powerful and convenient program development tools. These include:

· compiler or interpreter;

· integrated development environment;

· tools for creating and editing program texts;

· extensive libraries of standard programs and functions;

· debugging programs, i.e. programs that help find and fix errors in the program;

· user-friendly dialogue environment;

· multi-window operating mode;

· powerful graphic libraries; utilities for working with libraries;

· built-in assembler;

· built-in help desk;

· other specific features.