Cos'è un algoritmo e cosa significa. Algoritmi

Oggi la tecnologia informatica è diventata parte integrante della nostra vita. Hanno introdotto nel vocabolario della persona media molti termini, il cui significato non gli è sempre chiaro. Ma tutti li usano. Ad esempio, cos’è un algoritmo? Un utente normale non sarà in grado di darti una risposta chiara, ma è necessario saperlo, poiché lo incontriamo ogni giorno.

Storia dell'origine del termine

Il concetto di algoritmo è stato sviluppato per la prima volta da un matematico di nome Muhammad Al-Khwarizmi. Visse in Oriente nei secoli VIII e IX e scrisse due grandi opere. Il primo ha dato origine alla parola "algebra" e il secondo al concetto di "algoritmo". Rappresentava le operazioni aritmetiche che conosciamo come addizione, sottrazione, moltiplicazione e divisione. Nel 1957, in una delle edizioni del dizionario inglese, gli autori ritenevano che l'algoritmo fosse un concetto obsoleto. Ancora una volta è entrato in uso attivamente solo con l'avvento dei computer. Indicavano azioni che facevano parte di un determinato processo. Ma non deve essere solo matematico. Ciò implica un algoritmo per azioni di qualsiasi natura, ad esempio preparare un piatto. Da quel momento, questo concetto è stato sulla bocca di quasi tutte le persone.

Tentativi di definizione del termine

Per molto tempo questo termine è stato considerato esclusivamente come un algoritmo per i numeri e le operazioni con essi. Dopotutto, la matematica stessa era per la maggior parte una scienza applicata. Le formule utilizzate per i calcoli a quel tempo erano considerate algoritmi. I passaggi seguiti per risolverli erano elementari, ma i calcoli stessi erano molto macchinosi e richiedevano molto tempo e impegno. I matematici non hanno nemmeno pensato di definire questo concetto. Ma col passare del tempo, la scienza si è sviluppata sempre di più e sono comparsi oggetti mai incontrati prima (matrici, vettori, insiemi, ecc.). Tutti dovevano essere operati. Ciò ha dato impulso alla comprensione che un algoritmo è un concetto complesso e deve essere definito con precisione per un ulteriore utilizzo. Gli scienziati sono divisi su questo tema. Alcuni credevano che l’algoritmo potesse essere applicato a tutto, mentre altri dubitavano che ogni problema potesse essere risolto con il suo aiuto. Quest’ultimo punto di vista si è rivelato corretto, ma ha potuto essere suffragato solo dando una definizione precisa del concetto di “algoritmo”.

Cosa significa il termine "algoritmo"?

Ogni giorno una persona deve risolvere problemi di varia complessità. Siamo così abituati a quelli semplici che intraprendiamo azioni per risolverli automaticamente. Quelli complessi richiedono molta riflessione. Quando sorge un problema, lo risolviamo per fasi, adottando misure. Quindi in matematica, ad esempio, per trovare l'incognita in un'equazione, è necessario agire passo dopo passo. Queste operazioni, che portano gradualmente alla soluzione del problema, sono chiamate algoritmo. Un algoritmo è una sequenza di azioni, che singolarmente sono i suoi passi. Hanno un posto specifico e devono seguirsi rigorosamente l'uno con l'altro. Esistono classi di algoritmi, si chiamano classi di complessità. Ciascuno di essi include un determinato insieme di problemi che hanno approssimativamente la stessa complessità di soluzione.

Proprietà comuni a tutti gli algoritmi

Oltre agli algoritmi, ci sono molte altre istruzioni nel nostro mondo. Ma grazie ad alcune proprietà possiamo distinguerlo dal resto. Questi includono:

Discretezza: lo schema dell'algoritmo prevede la soluzione del compito attraverso azioni sequenziali eseguite in rigoroso ordine.
Certezza: tutte le condizioni stabilite sono chiare e non presentano alcuna ambiguità. L'algoritmo delle azioni, quindi, non lascia spazio ad alcuna improvvisazione. Ciò ti consente di fare tutto meccanicamente senza bisogno di istruzioni aggiuntive.
Efficienza: entro un certo numero di passaggi, l'algoritmo fornisce sempre la soluzione corretta al problema.
Massività: un algoritmo è una soluzione a un problema che ha una forma generale. Cioè, è applicabile a tutti i problemi di una determinata classe, indipendentemente dai dati di origine. Sono selezionati da un determinato campo chiamato “ambito di applicabilità dell’algoritmo”.

Tipi di algoritmi

A seconda di varie condizioni, come l'obiettivo, il percorso risolutivo, i dati iniziali, gli algoritmi si dividono in:

Meccanico: una sequenza rigida e corretta per ottenere il risultato richiesto (garantire il funzionamento del motore, ecc.).
Flessibile: 1) probabilistico: ha diversi modi per raggiungere la decisione giusta; 2) euristico - uno schema di algoritmo che non ha un programma d'azione univoco (ricette, ecc.), poiché si basa sulle qualità e sull'esperienza personali di una persona.
Ausiliario: sviluppato in precedenza e interamente destinato a risolvere un problema specifico.

Algoritmi in informatica

Per l’informatica, gli algoritmi sono di particolare importanza. In questa scienza sono divisi nei seguenti tipi:

Lineare: tutte le azioni vengono eseguite in sequenza, una dopo l'altra.
Un algoritmo di branching è quello in cui il soddisfacimento di una determinata condizione porta alla scelta di una delle due possibili opzioni per ulteriori azioni.
Ciclico: le stesse azioni vengono ripetute su dati di origine diversi, selezionando così quelli più adatti.

Struttura dell'algoritmo

Gli algoritmi hanno una propria struttura, che di solito viene visualizzata in un diagramma. Un diagramma dell'algoritmo è una sua rappresentazione grafica sotto forma di blocchi interconnessi. Ognuno di essi mostra uno dei passaggi dell'algoritmo. All'interno di ciascun blocco è contenuta una descrizione di un'azione specifica. Tali diagrammi vengono solitamente disegnati per facilitare la programmazione, poiché sono visivi e consentono di percepire visivamente la quantità di lavoro da svolgere. Una persona può comprendere il processo e correggerlo anche prima che si verifichino errori.

Regole per la compilazione degli algoritmi

La prima regola è che è necessario identificare un gran numero di oggetti che possono essere suscettibili all'algoritmo costruito. Il programmatore li converte in dati utilizzando la codifica. Entrano e escono. I primi servono per iniziare il lavoro, i secondi ne diventano il risultato. Questa si chiama trasformazione dei dati.
La seconda regola dice che lavorare con l'algoritmo richiede memoria libera. Dopotutto, senza di esso non ci sarà modo di inserire dati di input, lavorarci e ottenere output. La memoria è costituita da cellule. Se dai un nome a uno di essi, diventa una variabile.
La terza regola è già stata descritta sopra come una delle caratteristiche dell'algoritmo, ovvero la discrezionalità. Cioè, l'algoritmo è costituito da singole operazioni o passaggi.
La quarta regola ci ricorda il determinismo dell'algoritmo. Cioè, dopo ogni azione è necessario indicare cosa sarà successivo o interrompere il processo.
L'ultima regola afferma che dopo un certo numero di passaggi l'algoritmo completa il suo lavoro, ottenendo l'uno o l'altro risultato. E quale, indica lo stesso programmatore.

Pertanto, un algoritmo è un concetto complesso che, prima dell'avvento dei computer, veniva utilizzato solo in matematica ed era considerato obsoleto. Oggi viene utilizzato in tutti gli ambiti della vita, uno dei più importanti è l'informatica.

Ogni algoritmo si occupa dei dati: input, intermedi e output.

Arto. Viene inteso in due modi: in primo luogo, l'algoritmo è costituito da singoli passaggi elementari, o azioni, e ovviamente ci sono molti passaggi diversi che compongono l'algoritmo. In secondo luogo, l’algoritmo deve terminare in un numero finito di passaggi. Se viene costruito un processo infinito che converge alla soluzione desiderata, ad un certo punto si interrompe e il valore risultante viene preso come soluzione approssimativa al problema in esame. La precisione dell'approssimazione dipende dal numero di passaggi.

Elementarità (comprensibilità). Ogni passaggio dell'algoritmo deve essere semplice in modo che il dispositivo che esegue le operazioni possa completarlo in un unico passaggio.

Discrezione. Il processo di risoluzione di un problema è rappresentato come una sequenza finita di singoli passaggi e ogni passaggio dell'algoritmo viene eseguito in un tempo finito (non necessariamente unitario).

Determinismo (certezza). Ogni passaggio dell'algoritmo deve essere definito in modo univoco e inequivocabile e non deve consentire interpretazioni arbitrarie. Dopo ogni passaggio viene indicato quale passaggio eseguire successivamente oppure viene dato un comando di arresto, dopodiché il lavoro dell'algoritmo è considerato completo.

Produttività. L'algoritmo ha un certo numero di quantità di input: argomenti. Lo scopo dell'esecuzione dell'algoritmo è ottenere un risultato specifico che abbia una relazione molto specifica con i dati originali. L'algoritmo deve fermarsi dopo un numero finito di passi, a seconda dei dati, con l'indicazione di cosa considerare come risultato. Se non è possibile trovare una soluzione, è necessario indicare quale è considerato il risultato in questo caso.

Carattere di massa. L'algoritmo per risolvere il problema è sviluppato in forma generale, ad es. dovrebbe essere applicabile per una certa classe di problemi che differiscono solo nei dati iniziali. In questo caso i dati iniziali possono essere selezionati da una certa area chiamata area di applicabilità dell’algoritmo.

Efficienza. Lo stesso problema può essere risolto in modi diversi e, di conseguenza, in tempi diversi e con costi di memoria diversi. È auspicabile che l'algoritmo consista di un numero minimo di passaggi e che la soluzione soddisfi la condizione di accuratezza e richieda un dispendio minimo di altre risorse.

L'esatta definizione matematica dell'algoritmo è complicata dal fatto che l'interpretazione delle istruzioni prescritte non dovrebbe dipendere dal soggetto che le esegue. A seconda del suo livello intellettuale, potrebbe non comprendere affatto il significato delle istruzioni o, al contrario, interpretarlo in modo non voluto.

Il problema delle norme di interpretazione può essere aggirato se, oltre alla formulazione delle norme, vengono descritti la struttura e il principio di funzionamento del dispositivo di interpretazione. Ciò evita incertezze e ambiguità nella comprensione delle stesse istruzioni. Per fare ciò, è necessario specificare una lingua in cui sono descritte molte regole di comportamento o una sequenza di azioni, nonché il dispositivo stesso, che può interpretare le frasi fatte in questa lingua ed eseguire passo dopo passo ogni processo definito con precisione . Si scopre che un tale dispositivo (macchina) può essere implementato in una forma che rimane costante indipendentemente dalla complessità della procedura in questione.

Attualmente si possono distinguere tre tipi principali di modelli algoritmici universali. Differiscono nei presupposti di partenza riguardanti la definizione del concetto di algoritmo.

Primo tipo collega il concetto di algoritmo con i concetti più tradizionali della matematica: calcoli e funzioni numeriche. Secondo tipo si basa sull'idea di un algoritmo come un certo dispositivo deterministico in grado di eseguire solo operazioni molto primitive in un dato momento. Questa rappresentazione garantisce l'univocità dell'algoritmo e l'elementarità dei suoi passaggi. Inoltre, questa idea corrisponde all'ideologia della costruzione di computer. Il principale modello teorico di questo tipo, creato negli anni '30. Il matematico inglese Alan Turing, è una macchina di Turing.

Terzo tipo– si tratta di trasformazioni di parole in alfabeti arbitrari, in cui le operazioni elementari sono sostituzioni, cioè sostituire parte di una parola (una parola è una sequenza di caratteri alfabetici) con un'altra parola. I vantaggi di questo tipo di modello sono la massima astrazione e la capacità di applicare il concetto di algoritmo a oggetti di natura arbitraria (non necessariamente numerica). Esempi di modelli del terzo tipo sono i sistemi canonici del matematico americano Emil L. Post e gli algoritmi normali introdotti dal matematico sovietico A. A. Markov.

I modelli del secondo e del terzo tipo sono abbastanza vicini e differiscono principalmente per gli accenti euristici, quindi non è un caso che parlino della macchina di Post, sebbene Post stesso non ne abbia parlato.

Una registrazione di un algoritmo in una lingua è un programma. Se un programma è scritto in uno speciale linguaggio algoritmico (ad esempio PASCAL, BASIC o qualche altro), allora parliamo di programma originale. Viene chiamato un programma scritto in un linguaggio che un computer può comprendere direttamente (solitamente codici binari). macchina, O binario.

Qualsiasi modo di scrivere un algoritmo implica che ogni oggetto descritto con il suo aiuto sia specificato come rappresentante specifico di una classe spesso infinita di oggetti che possono essere descritti in questo modo.

I mezzi utilizzati per scrivere gli algoritmi sono in gran parte determinati da chi ne sarà l'esecutore.

Se l'esecutore è una persona, la registrazione potrebbe non essere del tutto formalizzata; la chiarezza e la visibilità vengono prima di tutto. In questo caso, per la registrazione possono essere utilizzati diagrammi algoritmici o notazioni verbali.

Per scrivere algoritmi destinati agli esecutori di automi, è necessaria la formalizzazione, pertanto, in questi casi vengono utilizzati linguaggi formali speciali. Il vantaggio della notazione formale è che rende possibile studiare gli algoritmi come oggetti matematici; in questo caso, la descrizione formale dell'algoritmo serve come base per comprendere intellettualmente questo algoritmo.

Per scrivere algoritmi viene utilizzata un'ampia varietà di mezzi. La scelta dello strumento è determinata dal tipo di algoritmo eseguito. Si distinguono: modi principali per scrivere algoritmi:

■ verbale– l'algoritmo è descritto in linguaggio umano;

■ simbolico– l'algoritmo è descritto utilizzando un insieme di simboli;

■ grafico– l'algoritmo viene descritto mediante un insieme di immagini grafiche.

I modi generalmente accettati di scrivere un algoritmo sono registrazione grafica utilizzando diagrammi di algoritmi (diagrammi di flusso) e notazione simbolica con utilizzando un linguaggio algoritmico.

Per descrivere un algoritmo, i diagrammi vengono utilizzati per rappresentare una sequenza connessa di figure geometriche, ciascuna delle quali implica l'esecuzione di un'azione specifica dell'algoritmo. L'ordine delle azioni è indicato dalle frecce.

I seguenti tipi di simboli grafici vengono utilizzati nei diagrammi degli algoritmi.

Inizio E FINE L'algoritmo è designato utilizzando gli stessi simboli (Fig. 21.1).

Riso. 21.1.

Un passo dell'algoritmo associato all'assegnazione di un nuovo valore ad una determinata variabile, trasformando un determinato valore per ottenere un altro valore, è rappresentato dal simbolo "processi"(Fig. 21.2).

Riso. 21.2.

La scelta della direzione di esecuzione dell'algoritmo in funzione di alcune condizioni variabili è rappresentata dal simbolo " soluzione"(Fig. 21.3).

Riso. 21.3.

Qui R significa predicato (espressione condizionale, condizione). Se la condizione è soddisfatta (il predicato assume il valore TRUE), la transizione viene effettuata a un passaggio dell'algoritmo e, se non è soddisfatto, a un altro.

Esistono primitive per le operazioni di input e output dei dati, nonché altri simboli grafici. Attualmente, sono definiti dallo standard GOST 19.701–90 (ISO 5807–85) "Sistema unificato di documentazione dei programmi. Schemi di algoritmi, programmi e sistemi di dati. Convenzioni e regole di esecuzione". In totale, la collezione DGUE contiene 28 documenti.

Utilizzando il diagramma dell'algoritmo, è facile comporre un programma iniziale in un linguaggio algoritmico.

A seconda della sequenza di azioni nell'algoritmo, si distinguono algoritmi di struttura lineare, ramificata e ciclica.

Negli algoritmi struttura lineare le azioni vengono eseguite in sequenza una dopo l'altra.

Negli algoritmi struttura ramificata A seconda dell'adempimento o del mancato adempimento di una condizione, vengono eseguite diverse sequenze di azioni. Viene chiamata ciascuna di queste sequenze di azioni ramo dell'algoritmo.

Negli algoritmi struttura ciclica a seconda dell'adempimento o del mancato adempimento di qualsiasi condizione, viene eseguita una sequenza ripetitiva di azioni, chiamata corpo del ciclo. Un ciclo nidificato è un ciclo che si trova all'interno del corpo di un altro ciclo. Un ciclo iterativo è un ciclo il cui numero di ripetizioni non è specificato, ma viene determinato durante l'esecuzione del ciclo.

In questo caso, viene chiamata una ripetizione del ciclo iterazione.

In informatica si chiama piano d'azione algoritmo.
L'algoritmo è costituito da passaggi separati: squadre. Nessuno di essi può essere saltato, molto spesso nessuna squadra può essere scambiata.
Esecutore- una persona, animale o macchina in grado di comprendere ed eseguire determinati comandi.
Ambiente dell'artista– oggetti che circondano il performer e con i quali lavora.
Elenco dei comandi dell'esecutore (SKI)– un insieme di comandi comprensibili all’esecutore. L'esecutore può eseguire solo i comandi inclusi nel suo SKI.

Per risolvere la maggior parte dei problemi, non è sufficiente dare un comando all'esecutore, è necessario creare per lui un algoritmo: un piano d'azione composto da comandi che capisce (incluso nel suo SKI).
Algoritmo- un piano d'azione definito con precisione per l'esecutore, volto a risolvere un problema. L'algoritmo può includere solo i comandi presenti nello SKI.

Quali sono gli algoritmi?

Algoritmo lineare
In un algoritmo lineare, i comandi vengono eseguiti in sequenza, uno dopo l'altro. Un esempio di algoritmo lineare è l’algoritmo per la preparazione del tè.

Algoritmo di ramificazione

In un algoritmo di branching, l'ordine dei comandi può essere diverso a seconda dell'ambiente. Un esempio di algoritmo di ramificazione è l'algoritmo di attraversamento stradale.

Algoritmo round robin
In un algoritmo ciclico alcune azioni vengono ripetute più volte (in informatica si dice che viene eseguito un loop). Esistono due tipi di algoritmi ciclici. In uno di essi sappiamo in anticipo quante volte dobbiamo eseguire queste azioni, nell'altro dobbiamo fermarci solo quando completiamo il lavoro, cioè le nostre azioni si fermano quando viene soddisfatta qualche condizione.
Un esempio di ciclo del primo tipo è la nostra vita nei giorni feriali (dal lunedì al sabato): eseguiamo quasi le stesse azioni 6 volte.
Un esempio di ciclo del secondo tipo è l'algoritmo per segare un tronco: non possiamo dire in anticipo quante volte dobbiamo spostare la sega lontano da noi e verso noi stessi - dipende dalla densità dell'albero, dalla qualità del la sega e i nostri sforzi. Sappiamo però per certo che dovremo finire il lavoro quando il prossimo tronco segato cadrà a terra.

Modi di scrivere algoritmi

Nella pratica esistono tre metodi più comuni per scrivere algoritmi:

verbale(registrazione in linguaggio naturale);
grafico(registrazione tramite simboli grafici);
programma(testi in linguaggi di programmazione).

Modo verbale di scrivere algoritmi

Metodo verbale: un modo per scrivere un algoritmo in linguaggio naturale. Questo metodo è molto conveniente se è necessario descrivere approssimativamente l'essenza dell'algoritmo. Tuttavia, con una descrizione verbale non è sempre possibile esprimere in modo chiaro e accurato la logica delle azioni.

Come esempio di un modo verbale di scrivere un algoritmo, considera un algoritmo per trovare l'area di un rettangolo

dove S è l'area del rettangolo; a, b – la lunghezza dei suoi lati.

Ovviamente a, b devono essere specificati in anticipo, altrimenti il problema non si risolve.

Il modo verbale di scrivere l'algoritmo è simile al seguente:

L'inizio dell'algoritmo.
Impostare il valore numerico del lato a.
Impostare il valore numerico del lato b.
Calcola l'area S del rettangolo utilizzando la formula S=a*b.
Emette il risultato dei calcoli.
Fine dell'algoritmo.

Modo grafico per descrivere gli algoritmi

Per una rappresentazione più visiva dell'algoritmo, viene utilizzato un metodo grafico. Esistono diversi modi per descrivere graficamente gli algoritmi. La descrizione grafica degli algoritmi più utilizzata nella pratica è l'uso dei diagrammi di flusso. L'indubbio vantaggio dei diagrammi a blocchi è la chiarezza e la semplicità della scrittura dell'algoritmo.

Ad ogni azione dell'algoritmo corrisponde una figura geometrica (simbolo del blocco). Nella tabella seguente è riportato un elenco dei simboli più comunemente utilizzati.

Poiché nell’algoritmo lineare i comandi vengono eseguiti in sequenza, lo schema a blocchi sarà simile a:

Poiché in un algoritmo di branching l'ordine dei comandi può essere diverso a seconda dell'ambiente, il diagramma di flusso assumerà la forma:

In un algoritmo ciclico, alcune azioni vengono ripetute più volte e per questo il diagramma di flusso assumerà la forma:

Metodo software di scrittura degli algoritmi

Affinché un algoritmo sia comprensibile a un robot, un computer o un'altra macchina, non è sufficiente scrivere semplicemente dei comandi; è anche necessario formalizzare l'algoritmo in una forma in cui la macchina lo capisca (scrivere un programma), cioè scriverlo utilizzando i comandi di SKI, seguendo le regole di progettazione.

Regole di progettazione del programma:

qualsiasi algoritmo ha un nome;
l'algoritmo inizia con una parentesi graffa di apertura “(“ e termina con una parentesi graffa di chiusura “)”; i comandi posti tra queste parentesi sono chiamati corpo dell'algoritmo;
l’algoritmo può includere solo quei comandi che si trovano nello SKI dell’esecutore;
ogni comando termina con il segno “;”, che indica la fine del comando;
Per facilitarci la comprensione dei programmi, utilizziamo commenti: spiegazioni testuali che iniziano con i segni “/*” e terminano con i segni “*/”; l'esecutore non presta attenzione ai commenti nell'algoritmo.

Compiti pratici:

Crea un diagramma di flusso per trovare il perimetro di un quadrato.
Realizza uno schema a blocchi per preparare il tè.
Realizza uno schema a blocchi per attraversare un incrocio con un semaforo.

Materiale utilizzato dai libri:

"Le moderne tecnologie dell'informazione", autori: docenti del centro "Turbo".
"Algoritmi ed esecutori", autore Polyakov K.

Prima di iniziare a scrivere super programmi, scopriamo cos'è un programma? Un programma è un algoritmo specifico che il tuo computer deve eseguire.

Bene, ora la domanda principale: cos’è un algoritmo?

Proprietà degli algoritmi

Non reinventerò la ruota, ma elencherò semplicemente le proprietà dell'algoritmo note da molti anni.

Estremità (efficacia) algoritmo significa che un risultato deve essere ottenuto in un numero finito di passaggi;
Discrezione algoritmo significa che l'algoritmo deve essere scomposto in una sequenza di passaggi;
Comprensibilità algoritmo significa che l'algoritmo deve contenere solo quei comandi inclusi nell'insieme di comandi che uno specifico esecutore può eseguire;
Precisione algoritmo significa che ogni comando deve essere compreso in modo inequivocabile;
Carattere di massa algoritmo significa che, una volta compilato, l'algoritmo deve essere adatto a risolvere problemi simili con dati iniziali diversi.
Determinismo (certezza). Un algoritmo ha la proprietà del determinismo se per gli stessi insiemi di dati iniziali produce lo stesso risultato, cioè il risultato è determinato in modo univoco dai dati iniziali.

Così, Algoritmo- si tratta di un'istruzione chiara e precisa all'esecutore per eseguire una sequenza finale di passaggi che portano dai dati iniziali al risultato desiderato.

Immagina di dover tagliare un'arancia con un coltello. Per eseguire questa azione ho bisogno di un algoritmo.

Voglio tagliare un'arancia. Come farlo?

Tipi di algoritmi

Lineare (i comandi sono sequenziali senza ripetizioni o transizioni);

Esempio di algoritmo:

Inizio
tira fuori il coltello
tagliare un'arancia (È un'arancia, non un altro frutto. La PRECISIONE è responsabile di questo)
mangiare un'arancia
FINE

Ciclico (esiste un gruppo di azioni che si ripetono in base ad alcune condizioni);

Esempio di algoritmo:

Inizio
tira fuori il coltello
FINO A quando le arance non saranno finite
tagliare un'arancia
mangia tutte le arance
FINE

Diramazione (l'esecuzione del comando dipende da una condizione).

Esempio di algoritmo:

Inizio
tira fuori il coltello
SE il coltello è smussato, affilatelo
tagliare un'arancia
mangiare un'arancia
FINE

È tutto. Nella prossima lezione vedremo la struttura di un programma in Pascal.

Concetto di algoritmo

Il concetto di algoritmo è un concetto centrale nell’informatica. La parola "algoritmo" deriva dal nome del matematico uzbeko al-Khorezmi, che formulò le regole per eseguire operazioni aritmetiche nel IX secolo. Nella matematica e nell'informatica moderne, il termine algoritmo ha le seguenti definizioni:

- una sequenza di azioni con regole di esecuzione rigorosamente definite;
- una prescrizione che determina il contenuto e la sequenza delle operazioni che trasformano i dati iniziali nel risultato desiderato;
- una descrizione esatta di un determinato processo computazionale o qualsiasi altra sequenza di azioni;
- una prescrizione esatta e completa della sequenza di esecuzione di un numero finito di azioni necessarie per risolvere qualsiasi problema di un dato tipo.

L'algoritmo può essere progettato per essere eseguito da una persona o da un dispositivo automatico: un esecutore formale. Il compito dell'esecutore è implementare accuratamente un algoritmo esistente. L'esecutore formale non è obbligato ad approfondire l'essenza dell'algoritmo e potrebbe addirittura non essere in grado di comprenderlo.

Un esempio di artista formale è una lavatrice automatica, che esegue rigorosamente le azioni prescritte, anche se ti sei dimenticato di metterci la polvere. Una persona può anche agire come esecutore formale, ma prima di tutto, vari dispositivi automatici, incluso un computer, sono esecutori formali. Ogni algoritmo viene creato in base a un esecutore specifico.

Ogni esecutore può eseguire comandi solo da un determinato elenco rigorosamente definito: il sistema dei comandi dell'esecutore. Per ciascun comando devono essere specificate le condizioni di applicabilità (in quali stati ambientali il comando può essere eseguito) e devono essere descritti i risultati dell'esecuzione del comando. Dopo aver chiamato il comando, l'esecutore esegue l'azione elementare corrispondente.

In informatica, l’esecutore universale degli algoritmi è il computer.

Tipi di algoritmi

Un algoritmo in relazione a un computer è una prescrizione esatta, cioè un insieme di operazioni e regole per la loro alternanza, con l'aiuto del quale, partendo da alcuni dati iniziali, è possibile risolvere qualsiasi problema di tipo fisso.

Gli algoritmi, a seconda dell'obiettivo, delle condizioni iniziali del problema, dei modi per risolverlo e della determinazione delle azioni dell'esecutore, sono suddivisi come segue:

Algoritmo probabilistico (stocastico). fornisce un programma per risolvere un problema in diversi modi o metodi che portano al probabile raggiungimento di un risultato.
Algoritmo euristico(dalla parola greca “eureka”) è un algoritmo in cui il raggiungimento del risultato finale del programma d'azione non è chiaramente predeterminato, così come non è indicata l'intera sequenza delle azioni, e non sono identificate tutte le azioni dell'esecutore . Gli algoritmi euristici includono, ad esempio, istruzioni e prescrizioni. Questi algoritmi utilizzano procedure logiche universali e metodi decisionali basati su analogie, associazioni ed esperienze passate nella risoluzione di problemi simili.
Algoritmo lineare- un insieme di comandi (istruzioni) eseguiti in sequenza uno dopo l'altro.
Algoritmo di ramificazione- un algoritmo contenente almeno una condizione, a seguito del controllo della quale il computer fornisce una transizione a uno dei due possibili passaggi.
Algoritmo round robin- un algoritmo che prevede la ripetizione ripetuta della stessa azione (le stesse operazioni) su nuovi dati iniziali. La maggior parte dei metodi di calcolo e di enumerazione delle opzioni sono ridotti ad algoritmi ciclici. Un ciclo di programma è una sequenza di comandi (serie, corpo del ciclo) che possono essere eseguiti ripetutamente (per nuovi dati sorgente) finché non viene soddisfatta una determinata condizione.
Algoritmo (procedura) ausiliario (slave)- un algoritmo precedentemente sviluppato e interamente utilizzato nell'algoritmo di uno specifico problema. In alcuni casi, se esistono sequenze identiche di istruzioni (comandi) per dati diversi, viene assegnato anche un algoritmo ausiliario per ridurre la registrazione.

L'algoritmo può essere specificato in diversi modi:

- verbale, cioè registrare una sequenza di azioni in linguaggio naturale;
- grafico, utilizzando appositi simboli grafici;
- stereotipato, cioè utilizzando formule matematiche che determinano l'ordine dei calcoli;
- tabellare e sotto forma di una tabella in cui sono registrate le fasi di esecuzione dell'algoritmo e i risultati dell'esecuzione.

Diagramma di flusso dell'algoritmo

Specificare gli algoritmi utilizzando i diagrammi di flusso si è rivelato un mezzo molto conveniente per rappresentare gli algoritmi ed è diventato molto diffuso.

Diagramma di flusso dell'algoritmo: una rappresentazione grafica dell'algoritmo sotto forma di frecce interconnesse (linee di transizione) e blocchi- simboli grafici, ciascuno dei quali corrisponde ad un passo dell'algoritmo. All'interno del blocco viene fornita la descrizione dell'azione corrispondente.

La tabella mostra i simboli più comunemente usati.

Simboli del diagramma di flusso
Nome del simbolo	Designazione ed esempio di riempimento	Spiegazione
Processi		Azione computazionale o sequenza di azioni
Soluzione		Verifica delle condizioni
Modifica		Inizio del ciclo
Processo predefinito		Calcoli tramite subroutine, subroutine standard
Input Output		I/O in generale
Inizio-stop		Inizio, fine dell'algoritmo, ingresso e uscita dalla subroutine
Documento		Uscita dei risultati

Blocca " processi" viene utilizzato per denotare un'azione o una sequenza di azioni che modifica il significato, la forma di presentazione o il posizionamento dei dati. Per migliorare la chiarezza del diagramma è possibile riunire più blocchi di elaborazione singoli in un unico blocco. La presentazione delle singole operazioni è abbastanza libera.

Blocca " soluzione" viene utilizzato per indicare le transizioni di controllo condizionale. Ogni blocco "soluzione" deve identificare la domanda, la condizione o il confronto che definisce.

Blocca " modifica» utilizzato per organizzare strutture cicliche. (La parola “modifica” significa “modifica, trasformazione”). All'interno del blocco viene scritto un parametro di ciclo, di cui per ogni ripetizione vengono indicati il valore iniziale, la condizione al contorno e il passo di modifica del valore del parametro.

Blocca " processo predefinito" viene utilizzato per indicare chiamate ad algoritmi ausiliari che esistono autonomamente sotto forma di alcuni moduli indipendenti e per chiamate a routine di libreria.

Ad esempio, ecco un diagramma a blocchi dell'algoritmo per trovare il massimo tra due valori:

Regole per la costruzione dell'algoritmo

Affinché un algoritmo possa raggiungere il suo scopo, deve essere costruito secondo determinate regole. Pertanto, non dobbiamo parlare delle proprietà dell'algoritmo, ma delle regole per costruire l'algoritmo o dei requisiti dell'algoritmo.

Prima regola- quando si costruisce un algoritmo, prima di tutto, è necessario specificare un insieme di oggetti con cui funzionerà l'algoritmo. La rappresentazione formalizzata (codificata) di questi oggetti è chiamata dati. L'algoritmo inizia a lavorare con un determinato insieme di dati, chiamati input, e come risultato del suo lavoro produce dati, che vengono chiamati output. Pertanto, l'algoritmo converte i dati di input in dati di output. Finché non avremo formalizzato i dati di input, non potremo costruire un algoritmo.

Seconda regola- La memoria è necessaria affinché l'algoritmo funzioni. La memoria memorizza i dati di input con cui l'algoritmo inizia a funzionare, dati intermedi e dati di output che sono il risultato dell'algoritmo. La memoria è discreta, cioè costituita da singole celle. Una posizione di memoria denominata è chiamata variabile. Nella teoria degli algoritmi, le dimensioni della memoria non sono limitate, cioè si ritiene che possiamo fornire all'algoritmo qualsiasi quantità di memoria necessaria per il funzionamento.

Terza regola- discrezione. L'algoritmo è costruito da singoli passaggi (azioni, operazioni, comandi). Più precisamente, da molti passaggi.

Quarta regola- determinismo. Dopo ogni passo è necessario indicare quale passo verrà eseguito successivamente oppure dare un comando di arresto.

Quinta regola- convergenza (efficacia). L'algoritmo deve terminare dopo un numero finito di passaggi. In questo caso è necessario indicare quale è considerato il risultato dell'algoritmo.

Proprietà dell'algoritmo

Discrezione(discontinuità, separatezza) - l'algoritmo deve rappresentare il processo di risoluzione di un problema come esecuzione sequenziale di passaggi semplici (o precedentemente definiti). Ogni azione prevista dall'algoritmo viene eseguita solo dopo che quella precedente ha completato l'esecuzione.

Certezza- ogni regola dell'algoritmo deve essere chiara e inequivocabile. A causa di questa proprietà, l'esecuzione dell'algoritmo è di natura meccanica e non richiede alcuna istruzione o informazione aggiuntiva sul problema da risolvere.

Efficienza(finitezza) - l'algoritmo deve portare alla soluzione del problema in un numero finito di passi.

Carattere di massa- l'algoritmo per risolvere il problema è sviluppato in forma generale, ovvero dovrebbe essere applicabile a una determinata classe di problemi che differiscono solo nei dati iniziali. In questo caso, i dati iniziali possono essere selezionati da una determinata area, chiamata area di applicabilità dell'algoritmo.