Алгоритм записанный на языке программирования называется утверждением моделью задачей программой

В математике и вычислительной технике алгоритм представляет собой конечную последовательность четко определенных инструкций для выполнения некоторой задачи. Которая при заданном начальном состоянии завершится в определенном конечном состоянии. Неформально понятие алгоритма часто иллюстрируется на примере рецепта. Хотя и более сложного. Алгоритмы часто содержат шаги. Которые повторяются (повторяются) или требуют принятия решений, например. С помощью логики или сравнений.

Содержание

$15.99$18.00

Бестселлер

(873)

СДЕЛКА ДНЯ

ЗАКАНЧИВАЕТСЯ В

Алгоритмы составляют основополагающую концепцию в

информатике. В большинстве высокоуровневых компьютерных программ алгоритмы действуют в сложных паттернах. Каждый из которых использует все меньшие и меньшие подметоды. Которые строятся до программы в целом.

Другими словами. Компьютерную программу можно рассматривать как алгоритм. В который вложены наборы меньших алгоритмов.

Большинство алгоритмов могут быть непосредственно реализованы компьютерными программами; любые другие алгоритмы. По крайней мере теоретически. Могут быть смоделированы компьютерными программами.

История

Еще в 1600 году до н. э.вавилоняне разработали алгоритмы факторизации и нахождения квадратных корней чисел. Евклидов алгоритм. Приведенный в Элементах Евклида около 300 г. до н. э., был полезен для определения наибольшего общего делителя двух целых чисел. Среди прочего. Последний алгоритм, вероятно. Не был открыт Евклидом и, возможно. Был известен грекам на 200 лет раньше.

Между 813 и 833 годами персидский математик Аль-Хаваризми (Абу Джаафар Абдулла Мухаммад Ибн Муса аль-Хаваризми) описал процедуру решения линейных и квадратичных уравнений. Слово

Первоначально термин арифметических вычислений с индо-арабскими цифрами. Позже, основываясь на европейских латинских переводах имени аль-Хорезми. Слово превратилось в Значение этого слова было также расширено. Чтобы включить все определенные математические процедуры для решения задач или выполнения задач.

Отсутствие математической строгости в Однако их понимание алгоритмов было значительно улучшено в 1936 году, когда

Алан Тьюрингописал компьютера), и утверждение. Что все возможные вычисления могут быть эмулированы на машине Тьюринга—утверждение. Известное как В настоящее время формальным критерием для алгоритма является то. Что это процедура. Которая может быть реализована на полностью заданной машине Тьюринга или эквивалентном формализме. Таким образом. Концепция алгоритма стала основой для развития информатики.

Первый случай алгоритма. Написанного для компьютера, встречается в заметках Ады Лавлейс об аналитической машине Чарльза Бэббиджа. Написанных в 1842 году. За это ее многие считают первым в мире программистом.

Бэббидж, однако. Так и не завершил свою аналитическую машину. И алгоритм так и не был реализован на ней.

Формализация алгоритмов

Алгоритмы необходимы для того, чтобы компьютеры обрабатывали информацию. Компьютерная программа-это в основном алгоритм. Который говорит компьютеру. Какие конкретные шаги выполнять и в каком порядке выполнять заданную задачу. Задача может быть чем-то вроде расчета зарплаты сотрудников или печати отчетов студентов. В формальном плане алгоритм можно рассматривать как любую последовательность операций. Которые могут быть выполнены системой

Обычно, когда алгоритм связан с обработкой информации. Данные считываются из входного источника или устройства. Записываются в выходной приемник или устройство и сохраняются для дальнейшей обработки.

Такие данные хранятся в структуре данных (инструмент для эффективного хранения данных в компьютере). И с ними может быть выполнен заранее определенный набор операций в соответствии с требованиями алгоритма.

Для любого такого вычислительного процесса алгоритм должен быть строго определен—то есть определен таким образом. Чтобы он применялся ко всем возможным обстоятельствам. Другими словами. Он должен быть в состоянии справиться с любым возможным несоответствием. Ошибкой или альтернативной ситуацией. Возникающей во время вычисления.

Например, он должен иметь возможность работать с недопустимым вводом. Таким как буква вместо числа.

Алгоритмы, как правило. Выполняют свои операции в последовательном порядке: сверху вниз и слева направо. Иногда, однако. Некоторые структуры управления (такие как циклы) могут изменять порядок. В котором выполняется определенный сегмент программы.

Компьютерная программа может рассматриваться как алгоритм. В котором имеется набор меньших алгоритмов. И каждый из них может содержать дополнительные подмножества алгоритмов.

Этот дизайн называется Чтобы проиллюстрировать это. Каждый подалгоритм предназначен для выполнения конкретной задачи. А основной алгоритм сводит результаты этих задач вместе. Чтобы сгенерировать решение (или выход) для вычислительной задачи.

Этот тип формализации алгоритма основан на предпосылках Уникальным для этой концепции формализованных алгоритмов является Это происходит от интуиции (Альтернативные понятия алгоритма можно найти в

Характеристика Кнута

Дональд Кнут составил список из пяти свойств. Которые до сих пор широко приняты в качестве требований к алгоритму:

[1]

  1. Конечность:
  2. Определенность:
  3. Входныеданные : Эти входные данные берутся из определенных наборов объектов.
  4. Вывод:
  5. Эффективность:

Примером такого алгоритма может служить евклидов алгоритм определения наибольшего общего делителя двух натуральных чисел.

Это описание алгоритма интуитивно понятно. Но лишено формальной строгости. Некоторые термины—такие как

Таким образом. Академически принятое определение алгоритма предусматривает конечные временные рамки работы. Некоторые, однако. Настаивают на том. Что определение должно включать процедуры. Которые могут выполняться вечно без остановки, утверждая. Что некоторые сущности могут быть необходимы для выполнения таких задач.

В таком случае успех алгоритма должен быть переопределен. Чтобы разрешить выходные последовательности. Которые не ограничены временем. Например, алгоритм. Который проверяет. Есть ли больше нулей. Чем единиц в бесконечной случайной двоичной последовательности. Должен работать вечно. Чтобы быть эффективным. При правильной реализации вывод алгоритма будет полезен. Пока алгоритм исследует последовательность. Он дает положительный ответ. Когда число исследуемых нулей превышает число единиц. И отрицательный ответ в противном случае.

Тогда успех этого алгоритма можно было бы определить как получение в конечном итоге только положительных ответов. Если в последовательности больше нулей. Чем единиц. И получение смеси положительных и отрицательных ответов в других случаях.

Выражающие алгоритмы

Алгоритмы могут быть выражены во многих типах нотаций. Таких как естественные языки, псевдокод, блок-схемыи языки программирования. Выражения алгоритмов на естественном языке. Как правило. Многословны и неоднозначны. И они редко используются для сложных или технических алгоритмов. Псевдокод и блок-схемы являются структурированными способами выражения алгоритмов. Которые избегают многих неоднозначностей. Распространенных в операторах естественного языка. Избегая при этом деталей реализации.

Языки программирования в основном предназначены для выражения алгоритмов в форме. Которая может быть выполнена компьютером, но они часто используются как способ определения или документирования алгоритмов.

Реализация

Most algorithms are intended to be implemented as computer programs. Many algorithms, however. Are implemented by other means. Such as a biological neural network—the human brain implementing arithmetic or an insect relocating food—or an electric circuit. Or a mechanical device.

Examples

One of the simplest algorithms is to pick out the largest number from an unsorted list of numbers. The solution necessarily requires looking at every number in the list. But only once at each. From this follows a simple algorithm. Which can be stated in English as follows:

  1. Assume the first item is the largest.
  2. Look at each of the remaining items in the list. And if a particular item is larger than the largest item found so far. Make a note of it.
  3. The last noted item is the largest in the list when the process is complete.

Here is a more formal coding of the algorithm in pseudocode:

Algorithm LargestNumber

 Input: A list of numbers L. Output: The largest number in the list L. 
 if L.size = 0 return null largestL[0] for each item in L, do if item > largest, then largestitem return largest 
  • «←» is a loose shorthand for «changes to». For instance. With «largest ← the item«, it means that the largest number found so far changes to this item.
  • «return» terminates the algorithm and outputs the value listed behind it.

Below is a much simpler algorithm presented somewhat formally but still in English instead of pseudocode. It determines whether a given number n is even or odd:

  1. BEGIN
  2. Read the value of n.
  3. Divide n by 2 and store the remainder in rem.
  4. If rem is 0, go to step 7.
  5. Print «n is an odd number.»
  6. Go to step 8.
  7. Print «n is an even number.»
  8. END

A more complex example is Euclid’s algorithm. Which is one of the oldest algorithms.

Algorithm analysis

As it happens. Most people who implement algorithms want to know how much of a particular resource (such as time or storage) is required for a given algorithm. Methods have been developed for the analysis of algorithms to obtain such quantitative answers. For example. The above algorithm has a time requirement of O(n), using the big O notation with n as the length of the list. At all times. The algorithm needs to remember only two values: The largest number found so far. And its current position in the input list. Therefore it is said to have a space requirement of O(1) In this example the sizes of the numbers themselves could be unbounded and one could therefore argue that the space requirement is O(log n). In practice, however. The numbers considered would be bounded and hence the space taken up by each number is fixed. (Note that the size of the inputs is not counted as space used by the algorithm.)

Different algorithms may complete the same task with a different set of instructions in less or more time, space. Or effort than others. For example. Consider two different recipes for making a casserole: One is a frozen package and simply needs to be warmed up in the microwave; but the other spells out how to make a casserole from scratch and involves using a conventional oven. Both recipes end up with roughly the same dish. But each has a different time and space requirement.

The analysis and study of algorithms is a field within computer science and is often practiced abstractly (without the use of a specific programming language or other implementation). In this sense. It resembles other mathematical disciplines in that the analysis focuses on the underlying principles of the algorithm. Not on any particular implementation. The pseudocode is simplest and abstract enough for such analysis.

Classes

There are various ways to classify algorithms. Each with its own merits.

Classification by implementation

One way to classify algorithms is by implementation means.

  • Recursion or iteration: A recursive algorithm is one that invokes (makes reference to) itself repeatedly until a certain condition is met. A method common to functional programming. Iterative algorithms use repetitive control structures. Like loops. To solve the given problems. A programmer has to determine which method is best to use for a particular problem.
  • Serial or parallel: Algorithms that are executed sequentially (one at a time) are known to be serial. Parallel algorithms take advantage of computer architectures where several processors can work on a problem at the same time. Parallel algorithms divide the problem into more symmetrical or asymmetrical sub-problems and pass them to many processors and put the results back together at the end. Problems that have no parallel algorithms are called «inherently serial problems.»
  • Deterministic or random: Deterministic algorithms solve problems with exact decisions at every step of the algorithm. Randomized algorithms. As their name suggests. Explore the search space randomly until an acceptable solution is found.
  • Exact or approximate: While many algorithms reach an exact solution. Approximation algorithms seek an approximation which is close to the true solution. Approximation may use either a deterministic or a random strategy. Such algorithms have practical value for many hard problems. Usually dealing with physical situations.

Classification by design paradigm

Another way of classifying algorithms is by their design methodology or paradigm. There are a certain number of paradigms. Each different from the other. Furthermore. Each of these categories will include many different types of algorithms. Some commonly found paradigms include:

  • A divide and conquer algorithm repeatedly reduces an instance of a problem to one or more smaller instances of the same problem (usually recursively). Until the instances are small enough to solve easily. An example of such is Binary Search; given a sorted list of characters and a target character. It will check the midpoint character in the list and tests to see if it is the target character. And if not. Whether the target is above or below the midpoint. Then, it uses the midpoint character as one of the bounds and then checks the new midpoint character of the one half of the list it is now searching. It repeats this procedure until the target is found or it cannot continue.
  • A Dynamic programming algorithm is used when a problem requires the same task or calculation to be done repeatedly throughout the program. Removing the redundancy can optimize such a program. Which is done by performing the repeated operations just once and storing the result for later use.
  • A greedy algorithm is similar to a dynamic programming algorithm. But the difference is that solutions to the sub-problems do not have to be known at each stage; instead a «greedy» choice can be made of what looks best for the moment. The difference between dynamic programming and greedy method is. It extends the solution with the best possible decision (not all feasible decisions) at an algorithmic stage based on the current local optimum and the best decision (not all possible decisions) made in previous stage. It is not exhaustive. And does not give accurate answer to many problems. But when it works. It will be the fastest method.
  • Linear programming. When solving a problem using linear programming. The program is put into a number of linear inequalities and then an attempt is made to maximize (or minimize) the inputs. Many problems (such as the maximum flow for directed graphs) can be stated in a linear programming way. And then be solved by a generic algorithm such as the simplex algorithm. A complex variant of linear programming is called integer programming. Where the solution space is restricted to all integers.
  • Reduction is another powerful technique in solving many problems by transforming one problem into another problem. For example. One selection algorithm for finding the median in an unsorted list is first translating this problem into sorting problem and finding the middle element in sorted list. The goal of reduction algorithms is finding the simplest transformation such that the complexity of the reduction algorithm does not dominate the complexity of the reduced algorithm. This technique is also called «transform and conquer.»
  • Search and enumeration: Many problems (such as playing chess) can be modeled as problems on graphs. A graph exploration algorithm specifies rules for moving around a graph and is useful for such problems. This category also includes the search algorithms and backtracking.
  • The probabilistic and heuristic paradigm: Algorithms belonging to this class fit the definition of an algorithm more loosely.
  1. Probabilistic algorithms are those that make some choices randomly (or pseudo-randomly); for some problems. It can in fact be proven that the fastest solutions must involve some randomness.
  2. Genetic algorithms attempt to find solutions to problems by mimicking the theory of biological evolution, in which cycles of «random mutations» are thought to yield successive generations of «solutions.» This process is likened to the concept of «survival of the fittest.» In genetic programming. The algorithm is regarded as a «solution» to a problem.
  3. Heuristic algorithms. Whose general purpose is not to find an optimal solution. But an approximate solution where the time or resources to find a perfect solution are not practical. An example of this would be local search. Taboo search. Or simulated annealing algorithms. A class of heuristic probabilistic algorithms that vary the solution of a problem by a random amount.

Classification by field of study

Every field of science has its own problems and needs efficient algorithms. Related problems in one field are often studied together. Some example classes are search algorithms. Sorting algorithms. Merge algorithms. Numerical algorithms. Graph algorithms. String algorithms. Computational geometric algorithms. Combinatorial algorithms. Machine learning, cryptography, data compression algorithms. And parsing techniques.

Some of these fields overlap with each other and advancing in algorithms for one field causes advancement in many fields and sometimes completely unrelated fields. For example. Dynamic programming is originally invented for optimization in resource consumption in industries. But it is used in solving a broad range of problems in many fields.

Classification by complexity

Some algorithms complete in linear time. Some complete in an exponential amount of time. And some never complete. One problem may have multiple algorithms. And some problems may have no algorithms. Some problems have no known efficient algorithms. There are also mappings from some problems to other problems. So computer scientists found it is suitable to classify the problems rather than algorithms into equivalence classes based on their complexity.

Notes

References

  • Church, Alonzo. «An Unsolvable Problem of Elementary Number Theory» The American Journal Of Mathematics 58 (1936): 345-363.
  • Davis, Martin. The Undecidable: Basic Papers On Undecidable Propositions. Unsolvable Problems and Computable Functions New York:Raven Press, 1965.
  • Knuth, Donald E. The Art of Computer Programming. Volume 1/Fundamental Algorithms (2nd ed.) Addison-Wesley, 1973. ISBN 0201038099
  • Post, Emil. «Finite Combinatory Processes. Formulation I» The Journal of Symbolic Logic 1 (1936): 103-105.
  • Rosser, J.B. «An Informal Exposition of Proofs of Godel’s Theorem and Church’s Theorem» Journal of Symbolic Logic 4 (1939).

External links

All links retrieved March 5, 2016.

Credits

New World Encyclopedia writers and editors rewrote and completed the Wikipedia article in accordance with New World Encyclopedia standards. This article abides by terms of the Creative Commons CC-by-sa 3.0 License (CC-by-sa). Which may be used and disseminated with proper attribution. Credit is due under the terms of this license that can reference both the New World Encyclopedia contributors and the selfless volunteer contributors of the Wikimedia Foundation. To cite this article click here for a list of acceptable citing formats.The history of earlier contributions by wikipedians is accessible to researchers here:

The history of this article since it was imported to New World Encyclopedia:

Note: Some restrictions may apply to use of individual images which are separately licensed.