algoritmo proposto e rappresentazione di un algoritmo

Questo è discusso in un libro Computer Science: An Overview (11th Edition) di J. Glenn Brookshear, nel Capitolo 5 Algoritmi . Per cominciare, l'autore definisce formalmente l'algoritmo come segue:

An algorithm is an ordered set of unambiguous, executable steps that defines a terminating process

Un'ulteriore discussione inizia a pagina 189. Autore spiega il significato di ambiguità in ciò che chiami "algoritmo proposto" come segue:

requirement imposed by the definition... is that the steps in an algorithm be unambiguous. This means that during execution of an algorithm, the information in the state of the process must be sufficient to determine uniquely and completely the actions required by each step. In other words, the execution of each step in an algorithm does not require creative skills. Rather, it requires only the ability to follow directions.

_{Per completezza, l'autore sottolinea che il requisito di cui sopra è intenzionalmente ridotto: "Nel Capitolo 12 apprenderemo che gli" algoritmi ", detti algoritmi non deterministici, che non sono conformi a questa restrizione sono un argomento importante di la ricerca. "}

L'ambiguità della rappresentazione dell'algoritmo è spiegata come segue:

It is important to emphasize the distinction between an algorithm and its representation — a distinction that is analogous to that between a story and a book. A story is abstract, or conceptual, in nature; a book is a physical representation of a story. If a book is translated into another language or republished in a different format, it is merely the representation of the story that changes — the story itself remains the same.

In the same manner, an algorithm is abstract and distinct from its representation. A single algorithm can be represented in many ways. As an example, the algorithm for converting temperature readings from Celsius to Fahrenheit is traditionally represented as the algebraic formula

   F = (9/5)C + 32

But it could be represented by the instruction

    Multiply the temperature reading in Celsius by 9/5
    and then add 32 to the product

or even in the form of an electronic circuit. In each case the underlying algorithm is the same; only the representations differ.

The distinction between an algorithm and its representation presents a problem when we try to communicate algorithms. A common example involves the level of detail at which an algorithm must be described. Among meteorologists, the instruction “Convert the Celsius reading to its Fahrenheit equivalent” suffices, but a layperson, requiring a more detailed description, might argue that the instruction is ambiguous. The problem, however, is not with the underlying algorithm but that the algorithm is not represented in enough detail for the layperson.

Più avanti nel capitolo, l'autore spiega anche come risolverlo:

the concept of primitives can be used to eliminate such ambiguity problems in an algorithm’s representation.

...A program is a representation of an algorithm. (Here we are using the term algorithm in its less formal sense in that many programs are representations of nonterminating “algorithms.”) In fact, within the computing community the term program usually refers to a formal representation of an algorithm designed for computer application.

...communication problems arise when the language used for an algorithm’s representation is not precisely defined or when information is not given in adequate detail.

Computer science approaches these problems by establishing a well-defined set of building blocks from which algorithm representations can be constructed. Such a building block is called a primitive. Assigning precise definitions to these primitives removes many problems of ambiguity, and requiring algorithms to be described in terms of these primitives establishes a uniform level of detail. A collection of primitives along with a collection of rules stating how the primitives can be combined to represent more complex ideas constitutes a programming language...

Non può esserci ambiguità in un algoritmo. Per definizione, un algoritmo è una procedura mediante la quale un computer può raggiungere un compito senza dover prendere decisioni da solo . Tutto ciò che fa è determinato dai passi dell'algoritmo e dai valori di input. Pertanto, qualsiasi ambiguità può solo essere dovuta a errori nella rappresentazione.

Si noti che esistono algoritmi non deterministici; questi scelgono una delle serie di azioni possibili in un solo passaggio. Tuttavia, le azioni possibili devono ancora essere prescritte esplicitamente e senza ambiguità e la fonte della casualità è considerata un valore di input. La distribuzione della casualità di solito è anche considerata parte della descrizione dell'algoritmo (di solito si vorrà utilizzare il miglior numero casuale disponibile, cioè uno equidistribuito ma non prevedibile).