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.

a l g o r i f m) è uno dei concetti base della logica e della matematica. Con A. intendiamo un'istruzione esatta che specifica il calcolo. un processo che porta dai dati iniziali, che possono variare, al risultato desiderato. Le parole “informatica” e “computazionale” che appaiono sopra non dovrebbero essere intese nel senso stretto di informatica digitale. Quindi, già nel corso di algebra scolastica si parla di calcoli con le lettere, e sebbene qui le lettere svolgano anche il ruolo di sostituti dei numeri, già in aritmetica. Nei calcoli compaiono simboli che non denotano alcuna quantità: parentesi, segni di uguale, segni aritmetici. Azioni. Possiamo andare oltre e considerare i calcoli con simboli arbitrari e le loro combinazioni; È in questo senso ampio che si intende il termine “calcolo” quando si descrive il concetto “A.”. Quindi, possiamo parlare di A. traduzione da una lingua all'altra, di A. lavoro di uno spedizioniere di treni (elaborazione delle informazioni sul movimento dei treni in ordini) e altri esempi di algoritmi. descrizioni dei processi di controllo studiati dalla cibernetica. SIGNIFICATO DI A. La parola “A” stessa. risale al IX secolo. (deriva da Algoritmi, che a sua volta è una traslitterazione latina, pare fatta nel XII secolo, del nome arabo del matematico khorezmiano al-Khwarizmi). Al giorno d'oggi, l'A. più semplice appare già alle elementari: questa è l'aritmetica dell'A. azioni (nell'Europa della metà del secolo A. era proprio ciò che veniva chiamata l'aritmetica scolastica moderna, cioè il sistema dei numeri posizionali decimali e l'arte di contare in esso, poiché il trattato di al-Khwarizmi fu uno dei primi, se non il primissimo, grazie Inoltre, l'Europa ha conosciuto il sistema posizionale). Sottolineiamo che alle elementari si insegna A. contabilità. Quando si parla della capacità di una persona di sommare numeri, ciò che si intende non è che per due numeri qualsiasi prima o poi sarà in grado di trovare la loro somma, ma che conosce un certo metodo uniforme di addizione applicabile a due specifiche registrazioni di numeri qualsiasi. , cioè e., in altre parole, addizione A. (un esempio di tale A. è la famosa addizione A. di numeri in una “colonna”). A. si trovano nella scienza ad ogni passo, la capacità di risolvere un problema “in forma generale” significa sempre, in sostanza, la padronanza di un certo A. Il concetto di problema “in forma generale” viene chiarito con l'aiuto del concetto di problema di massa. Il termine “problema” può essere inteso come il compito di trovare un oggetto che abbia determinate proprietà; si chiama questo oggetto soluzione a un problema (in particolare, per il problema di trovare una risposta a una domanda, la soluzione è la risposta “sì” o “no” alla domanda posta). Un problema è insolubile se non ha soluzione, cioè non esiste alcun oggetto che abbia le proprietà richieste. È chiaro, quindi, che l’irrisolvibilità del problema non dà motivo di agnosticismo. conclusioni; al contrario, stabilire l'irrisolvibilità di un problema specifico è una cognizione importante. Atto. Un problema di massa è definito da una serie di problemi “singoli” separati e consiste nella necessità di trovare un metodo generale (cioè A.) per risolverli. L'irrisolvibilità di un problema di massa significa l'impossibilità di trovare corrispondenze. R. I problemi di massa sono estremamente caratteristici e importanti per la logica e la matematica. Anche la soluzione di singoli problemi è spesso preziosa proprio perché fornisce contemporaneamente un metodo generale per risolvere un'intera classe di problemi; allo stesso tempo, la formulazione di un problema di massa significa la trasformazione di una certa classe di problemi in un unico problema - il problema di trovare una risposta per risolvere tutti i problemi di questa classe; qui si manifesta la connessione tra categorie di dialettica come l'individuale, il particolare e l'universale. Il ruolo dei problemi di massa determina il significato di A. Stabilire l'irrisolvibilità di un particolare problema di massa (cioè l'assenza di un unico algoritmo che consenta di trovare soluzioni a tutti i problemi individuali di una determinata serie) è l'atto cognitivo più importante, dimostrando che per risolvere problemi individuali specifici, sono fondamentalmente necessari metodi specifici per ciascuno di questi problemi. L'esistenza di problemi di massa insolubili serve quindi come concreta incarnazione dell'inesauribilità del processo cognitivo. Contenere. i fenomeni che hanno costituito la base per la formazione del concetto “A.” occupano da tempo un posto importante nella scienza. Molti problemi sorti in matematica e logica consistevano nella ricerca di determinati metodi costruttivi. La ricerca di tali metodi è stata particolarmente intensificata in connessione con la creazione di pratiche matematiche e logico simbolismo, oltre a comprendere l'assenza fondamentale di questi metodi in un certo numero di casi: tutto ciò è stato un fattore potente nello sviluppo della scienza. conoscenza. La consapevolezza dell'impossibilità di risolvere qualsiasi problema mediante calcolo diretto portò alla creazione nel XIX secolo. teoria degli insiemi. concetti. Solo dopo un periodo di rapido sviluppo di questo concetto (nell'ambito del quale la questione dei metodi costruttivi nella loro comprensione moderna non si pone affatto) è diventato possibile negli ultimi decenni tornare nuovamente alle questioni di costruttività, ma a un nuovo livello , arricchito dal concetto cristallizzato di “A”. (un altro esempio della posizione di Lenin sulla natura spiraliforme dello sviluppo della conoscenza). E sebbene il concetto "A." non è un'astrazione di così vasta portata come, ad esempio, il concetto di “insieme”, non può essere considerato casuale il fatto che storicamente il primo di questi concetti sia sorto più tardi del secondo. ESEMPI A. Simile ai concetti “insieme”, “corrispondenza”, “numero naturale”, “relazione”, ecc., il concetto “A”. è il primario logico-matematico concetto (una delle categorie della logica e della matematica). Non consente una definizione formale attraverso concetti più semplici, ma (come altre categorie matematiche) è astratta direttamente dall'esperienza. Il concetto "A." si impara solo attraverso gli esempi. Esempio 1. I possibili dati iniziali sono combinazioni finite non vuote costituite da bastoncini (I), cioè oggetti I, II, III, ecc. A. è costituito da quanto segue. regole (che devono essere seguite a partire dalla regola 1°): 1°. Sottolinea la levetta più a sinistra in basso e procedi alla 2° regola. 2°. Posiziona la levetta più a destra in alto e procedi con la regola del 3°. 3°. Esaminare il bastoncino sottolineato e, se non è sottolineato, procedere con la 4° regola. 4°. Consideriamo il bastoncino immediatamente successivo a quello sottolineato; se non è sottolineato procedere alla 5° regola; se è sottolineato procedere all'attuazione della 7° regola. 5°. Spostare la linea inferiore dal bastoncino sottolineato a quello successivo immediatamente successivo e procedere alla regola del 6°. 6°. Spostare la linea superiore dal bastoncino barrato a quello immediatamente precedente e procedere all'attuazione della regola del 7°. 7°. Cancellate il bastoncino barrato e tutti i bastoncini che lo seguono e procedete con la regola dell'8°. 8°. Cancella la linea inferiore del bastoncino sottolineato; quello che è successo è il risultato. Applicando questa A. alla combinazione ||||, presa come dato iniziale, otteniamo in sequenza: per regola 1° – |||, per regola 2° – ? || , secondo le regole 3°, 4°, 5° – | ? | , secondo le regole 6°, 3°, 4° – | ? | secondo la 7° regola – | ?, secondo l'8° regola – || (risultato). Se proviamo ad applicare A. alla combinazione |||, otteniamo: secondo la 1° regola – ? ||, secondo la 2° regola – ? | , secondo le regole 3°, 4°, 5° – | ? , secondo la 6° regola – | I |, allora bisogna procedere all'attuazione della 3° regola, ma la 3° regola è fattibile solo a condizione che il bastoncino sottolineato non sia sottolineato. Pertanto, per la situazione attuale, A. non contiene istruzioni su come procedere; il cosidetto stop inefficace (uno stop non accompagnato da un risultato). È facile notare che in generale è stato formulato. A. dà il risultato quando applicato a qualsiasi combinazione di un numero pari di bastoncini, e il risultato in questo caso è una combinazione composta dalla metà del numero di bastoncini; A. non dà alcun risultato se applicato a qualsiasi combinazione composta da un numero dispari di bastoncini. Esempio 2. In logica e matematica, viene chiamato qualsiasi insieme finito di segni. “alfabeto”, i segni in esso contenuti sono “lettere” dell'alfabeto, e la sequenza finale (inclusa quella vuota) di lettere scritte una dopo l'altra k.-l. alfabeto chiamato "parola" in questo alfabeto. Ad esempio, i numeri arabi formano un alfabeto e ogni rappresentazione decimale di un numero intero è una parola in questo alfabeto. Consideriamo l'alfabeto (a, b) di due lettere: a e b. Esempi di parole in questo alfabeto sono: v, aw, vva aaavavv, ecc. Concordiamo di chiamare “ammissibile” il passaggio da una parola di questo alfabeto a un'altra parola dello stesso alfabeto secondo una delle seguenti ipotesi. due regole: 1) se la parola ha la forma aP, dove P è una parola arbitraria, vai alla parola Pb; 2) se la parola assomiglia a va?, dove? – qualsiasi parola, vai alla parola Rava. Successivamente viene formulata una traccia, un'istruzione: “partendo da una parola k.-l. (presa come dato iniziale), effettuare delle transizioni ammissibili fino ad ottenere una parola della forma aa?; quando si ottiene una parola di questo tipo , scarta le prime due lettere e ciò che rimane è il risultato." Poiché è fattibile al massimo una regola di transizione ogni volta, formuliamo la prescrizione forma un alfabeto, i cui possibili dati iniziali sono parole dell'alfabeto (a, b). Prendiamo la parola vavaa come dato iniziale. Secondo la regola 2 otteniamo waaava. Applicando nuovamente la regola 2, otteniamo aavaava. In virtù delle nostre istruzioni, dobbiamo fermarci; il risultato (dell'applicazione di A. alla parola vavaa) è vavaa. Prendiamo la parola vaava come dato iniziale. Con la regola 2 otteniamo avaava. Con la regola 1 otteniamo vaavav. Successivamente otteniamo in sequenza avavava, vavavav, vavavava, ecc. È possibile dimostrare che il processo non finirà mai (cioè una parola che inizia con due lettere a non apparirà mai e per ciascuna delle parole risultanti sarà possibile effettuare una transizione valida). Pertanto, A. non dà alcun risultato quando applicato alla parola vaava. Prendiamo la parola vaav come dato iniziale. Otteniamo vaavv, avvav, vvavav in sequenza. Inoltre, nessuna delle regole 1 e 2 è fattibile e allo stesso tempo il risultato non ha funzionato. Pertanto, se applicato alla parola awaav, anche A. non produce risultati. Le caratteristiche principali di A. Secondo A. A. Markov, A. è caratterizzato dalle seguenti caratteristiche principali. caratteristiche: a) determinatezza dell'algoritmo. prescrizione, che consiste nella sua accuratezza e intelligibilità generale che non lascia spazio ad arbitrarietà (a causa di questa certezza della prescrizione, il processo algoritmico è deterministico: ogni fase del processo determina in modo univoco la fase successiva); b) la massa, che consiste nella possibilità per ciascun A. procedere da dati iniziali variabili entro certi limiti; c) efficacia, che consiste nel concentrarsi sull'ottenimento del risultato desiderato. Il determinismo di A. garantisce la possibilità di comunicazione da una persona ad un'altra persona affinché quest'altra persona possa compiere A. senza la partecipazione della prima; Questa stessa proprietà del determinismo permette di trasferire l'esecuzione di A. ad una macchina. La natura di massa dell'analisi presuppone che esista un certo insieme (per ogni analisi il suo) di possibili dati iniziali. Come sia impostata questa totalità è un'altra questione. Possiamo supporre che l'insieme dei possibili dati iniziali corrispondenti a qualsiasi A. non sia specificato separatamente dall'A., ma sia indicato con naturale. immagine dal contenuto stesso di questo A. (ad esempio, per A. addizione per colonna, l'insieme corrispondente è costituito da tutte le coppie di record di numeri nel sistema decimale). Quando un oggetto specifico viene selezionato come dato iniziale di A., allora si parla di applicare A. a questo oggetto. Se A. dà un risultato quando applicato a un determinato oggetto, allora dicono che è applicato a questo oggetto. L'efficacia di A. non significa affatto che A. debba essere applicabile a qualsiasi oggetto del corrispondente insieme di possibili dati iniziali (vedi esempi 1 e 2). È opportuno notare qui che è possibile costruire un algoritmo per il quale non esiste A. che riconoscerebbe dai dati iniziali arbitrari del primo A. se il primo A. è applicabile a loro o meno. Astrazioni di base della teoria di A. In ambito scientifico. In pratica, si sono sviluppate una serie di caratteristiche specifiche. per la matematica e le astrazioni logiche. Queste sono innanzitutto l'astrazione dell'infinito attuale, l'astrazione dell'identificazione, l'astrazione della realizzabilità potenziale. Sov. lo scienziato A. A. Markov ha dimostrato che gli ultimi due sono necessari quando si considera l'algoritmo A.. il processo è diviso in dipartimenti. passi, ciascuno dei quali si presuppone così elementare che la sua possibilità è effettiva. l’attuazione è fuori dubbio. Allo stesso tempo, il numero di questi passaggi elementari necessari per ottenere un risultato può essere così elevato che il raggiungimento del risultato può essere considerato praticamente impossibile. Tuttavia, l'idea pratica la fattibilità o l'impossibilità di un particolare numero di passaggi è relativa. Cambia con lo sviluppo dell'informatica. significa (in linea di principio può cambiare anche l'idea della natura elementare di un particolare passaggio). Nella teoria di A., quindi, si astrae dalla “fattibilità pratica” e si considera fattibile qualsiasi numero finito di passi. Così, studiando A. consentire l’astrazione della fattibilità potenziale, che consiste nell’astrazione dai confini reali delle nostre capacità. Lo sviluppo del calcolo elettronico ad alta velocità. le macchine stanno rapidamente spingendo questi confini sempre più in là. Ciò che ieri era solo potenzialmente fattibile, oggi diventa praticamente fattibile. Ciò avvicina la teoria dell’aritmetica alla pratica dell’informatica. macchine e permette a queste due discipline di arricchirsi a vicenda. Trasferimento delle attività alla macchina su s/l. la serie è impossibile senza preliminare. elaborazione delle decisioni A.. La compilazione di tale A., di regola, è di fondamentale importanza (ad esempio, nel problema della traduzione automatica, la cosa principale è la compilazione di una traduzione A.). L'astrazione della potenziale fattibilità è necessaria quando si considerano non solo quelli algoritmici. processi, ma anche gli oggetti stessi che partecipano a tali processi (compresi i “dati iniziali” e i “risultati”). Quindi, per parlare di qualsiasi numero naturale (più precisamente, di scrivere questo numero, diciamo, nel sistema decimale), dobbiamo permetterci di considerare record di numeri così grandi che questi record non si adatterebbero al globo; così, e qui, astraendo dal fisico. fattibilità di tale record, utilizzare l'astrazione della potenziale fattibilità. In generale, è necessario ricorrere all'astrazione della fattibilità potenziale per ragionare su parole arbitrariamente lunghe in un dato alfabeto. Oggetti la cui costruzione e considerazione sono possibili nel quadro dell'astrazione della fattibilità potenziale (in contrasto con l'astrazione dell'infinito reale), chiamati. oggetti costruttivi. Questi sono i numeri naturali rappresentati dalle loro voci in k.-l. il loro sistema di notazione, le parole di un dato alfabeto, ecc., nonché coppie, terzine e sequenze generalmente finite costituite da registrazioni di numeri, parole dell'alfabeto, ecc.; numeri razionali (che possono essere rappresentati come terzine di numeri naturali), ecc. Anche le cosiddette espressioni sono oggetti costruttivi. calcolo infinitesimale, o sistemi formali, che permettono di applicare a quest'ultimo l'apparato della teoria di A. Qualunque A. (intesa come prescrizione) può (dopo aver scritto questa prescrizione sotto forma di combinazione di alcuni simboli) essere considerata come oggetto costruttivo. Al contrario, gli oggetti la cui considerazione è impossibile senza implicare l'astrazione dell'infinito attuale, non rientrano tra gli oggetti costruttivi. Quindi, ad esempio, gli oggetti costruttivi non sono numeri reali (nel senso di Cantor, Dedekind o Weierstrass), geometrici. punti (poiché l'analisi di un'astrazione come "punto" porta all'idea di un punto come un sistema effettivamente infinito di piccoli corpi), ecc. Gli oggetti strutturali sono raggruppati in modo naturale. modo aggregato, esempi dei quali sono la raccolta di tutte le parole di un dato alfabeto e, in generale, qualsiasi raccolta di tutti gli oggetti di una classe. "tipo" dall'elenco. tipi di oggetti strutturali di cui sopra. Ciascuno di questi insiemi di oggetti strutturali è specificato dal metodo di costruzione degli oggetti che gli appartengono. Altro fondamentale L'astrazione utilizzata quando si considerano gli oggetti costruttivi e l'architettura è l'astrazione dell'identificazione. In alcuni casi si parla di due oggetti come identici. Le condizioni di “identicità” si stabiliscono di volta in volta in relazione ad una data situazione. Quindi, ad esempio, quando una persona esegue calcoli su carta, il carattere in cui sono scritti i numeri è solitamente indifferente e le voci 1647 e 1647 sono considerate le stesse; tuttavia si possono immaginare situazioni in cui la differenza tra carattere romano e corsivo è significativa (come, ad esempio, nella percezione delle parole trovate in questa Enciclopedia Filosofica). Allora i due record saranno già considerati disuguali, ma i record 1647 e 1647 saranno ancora - nei casi ordinari - gli stessi (anche se fisicamente si tratta di oggetti diversi). È generalmente accettato che gli oggetti costruttivi siano costituiti da alcune “parti elementari” abbastanza semplici (proprio come le parole sono fatte di lettere) e due oggetti costruttivi sono considerati uguali se consistono di parti elementari identiche disposte nello stesso ordine. Senza il concetto di “uguaglianza”, in base al quale, ad esempio, i numeri scritti con il gesso su una lavagna e i numeri scritti con l'inchiostro su un quaderno sono considerati uguali, l'apprendimento è impossibile. L'astrazione dell'identificazione ci permette di parlare di oggetti identici come di uno stesso oggetto. Porta alla formazione del concetto di “oggetto astratto”: vale a dire, due oggetti concreti identici sono considerati rappresentanti dello stesso oggetto astratto. Ogni A. applicato a oggetti identici porta anche a oggetti identici. Pertanto, possiamo supporre che ogni A. specifichi il processo di trasformazione di oggetti costruttivi astratti. Questa proprietà di A. (insieme al determinismo) determina la loro ripetibilità o riproducibilità: essendo stato sviluppato sotto forma di A. su oggetti costruttivi astratti, A. può essere riprodotto ripetutamente per qualsiasi oggetto costruttivo specifico consentito per un dato A. Da quanto sopra dovrebbe diventare chiaro che i dati iniziali sono gli stessi dei dati finali. risultati derivanti dall'attuazione di k.-l. A., sono sempre oggetti costruttivi (ogni “stato” algoritmico. processo è un oggetto costruttivo!). L'impossibilità di processi anche potenzialmente realizzabili su oggetti non costruttivi è associata anche alla mancanza di un modo per riconoscerli come identici o diversi (cfr. la nota posizione della cibernetica sui vantaggi delle forme discrete di memorizzazione delle informazioni rispetto a quelle continue ). Ci sono vari punti di vista. riguardo ai metodi consentiti nello studio di A. Uno di questi, proposto dai rappresentanti della direzione costruttiva in matematica e logica, è che poiché per la formazione del concetto di A. sono sufficienti le astrazioni di identificazione e potenziale fattibilità, allora lo sviluppo della teoria di A. dovrebbe essere effettuato nell'ambito di queste astrazioni. Un'altra vista consente lo studio di A. tutti i metodi generalmente consentiti in logica e matematica, incl. e richiedendo l'astrazione dell'infinito attuale. Si può quindi immaginare il caso in cui, per dimostrare che un certo A., applicato a un certo oggetto, darà un risultato, sarà necessario utilizzare la legge del terzo escluso, che è strettamente correlata all'astrazione dell'infinito attuale. Concetti fondamentali della teoria di A. Tra quelli fondamentali. i concetti che sorgono sulla base del concetto di aritmetica includono i concetti di funzione calcolabile, insieme risolvibile e insieme enumerabile. La funzione viene chiamata calcolabile, purché esista un algoritmo che calcoli questa funzione nel modo seguente. senso: a) A. è applicabile a qualsiasi oggetto compreso nel dominio di definizione della funzione, e dà come risultato il valore della funzione che assume per questo oggetto preso come argomento; b) A. non è applicabile a nessun oggetto non compreso nell'ambito della funzione. Viene chiamato un insieme situato in una determinata raccolta di oggetti costruttivi (ovvero un insieme composto da alcuni oggetti di questa raccolta). risolvibile (relativo all'insieme che lo racchiude), purché ci sia un A. che risolve questo insieme (relativo all'insieme specificato) nel successivo. senso: A. è applicabile a qualsiasi oggetto dell'insieme circostante e fornisce di conseguenza una risposta alla domanda se questo oggetto appartiene o meno all'insieme in esame. Infine viene chiamato un insieme non vuoto (vedi vuoto). enumerabile, purché esista una A che enumera questo insieme nel successivo. senso: a) il risultato dell'applicazione di A. a qualsiasi numero naturale esiste e appartiene all'insieme in esame; b) ciascun elemento dell'insieme in esame può essere ottenuto applicando l'aritmetica a qualche numero naturale. Per definizione, anche l'insieme vuoto è solitamente classificato come enumerabile. Una stessa funzione calcolabile (rispettivamente un insieme risolvibile, un insieme enumerabile) può essere calcolata (rispettivamente risolta, enumerata) mediante diversi A. Dalle definizioni segue che gli argomenti e i valori di una funzione calcolabile, elementi di un insieme risolvibile o enumerabile sono sempre oggetti costruttivi. Sostituzione di oggetti costruttivi (un certo sciame di aggregati fissi) con i loro numeri in un algoritmo arbitrario numerazione (cioè una numerazione per la quale esiste un algoritmo per ottenere il suo numero da un oggetto e viceversa), ci si può limitare, come spesso si fa nella teoria dell'aritmetica, a considerare solo tali funzioni computabili, gli argomenti e i cui valori sono numeri naturali, e solo tali insiemi risolvibili ed enumerabili, i cui elementi sono anche numeri naturali. Si può dimostrare che ogni insieme risolvibile è enumerabile. Allo stesso tempo, è stato possibile costruire un insieme enumerabile ma non risolvibile. Questo primo esempio concreto (pubblicato dallo scienziato americano A. Church nel 1936 nell’articolo “One Unsolvable Problem in Elementary Number Theory”) dell’assenza di un algoritmo (cioè di un algoritmo che risolve l’insieme costruito) è stato la fonte o esempio di quasi tutti gli altri esempi di questo tipo. Si è scoperto che un insieme è risolvibile se e solo se sia esso che il suo complemento (all'insieme di oggetti che lo racchiude) sono enumerabili. Pertanto, esistono complementi agli insiemi enumerabili che sono essi stessi non enumerabili. La connessione tra la teoria della logica e la logica. I concetti di insiemi decidibili ed enumerabili sono strettamente legati alla classificazione delle definizioni (ci limitiamo qui solo a tali definizioni, ciascuna delle quali definisce oggetti di un certo tipo o, che è lo stesso, una certa classe di oggetti). Come sai, ce ne sono due principali. schemi di definizione: “per differenza di genere e di specie” e “per induzione”. Quando si definisce "attraverso il genere e la differenza specifica", viene specificato un certo insieme comprensivo di oggetti ("genere") e viene indicata una caratteristica ("differenza di specie") che distingue tra gli oggetti un decreto, una raccolta della classe di oggetti definiti . Se; considerare che questa definizione è costruttiva, cioè che gli oggetti sono costruttivi e che la presenza o assenza di differenza di specie in un elemento del genere è algoritmicamente riconoscibile, allora l'insieme definito risulta decidibile (e ogni insieme decidibile può essere definito in questo modo). Pertanto, gli insiemi solubili vengono identificati con insiemi definiti costruttivamente attraverso il genere e la differenza specifica. La definizione “per induzione” è composta da due parti: la parte fondamentale, contenente un certo elenco di oggetti che si dichiarano appartenenti alla classe definita, e la parte induttiva, che afferma che se oggetti di questo o quel tipo appartengono a essendo la classe definita, alla classe definita appartengono anche oggetti di questo o quel tipo, collegati ai primi oggetti da una certa relazione. (Sono possibili anche casi più complessi delle cosiddette definizioni incrociate, quando più classi di oggetti vengono definite contemporaneamente l'una attraverso l'altra). Se assumiamo che la definizione sia costruttiva, cioè gli oggetti sono costruttivi, la lista degli oggetti iniziali contenuta nella parte base è finita, e le regole di transizione dagli oggetti già definiti a quelli nuovi algoritmici contenuti nella parte induttiva (nel senso che la presenza o l'assenza della relazione discussa nella parte la parte induttiva è riconosciuta attraverso una sorta di A.), allora arriviamo al concetto di insieme definito costruttivamente per induzione, o (sinonimo) di insieme effettivamente generato (poiché tale definizione specifica un processo di generazione efficace, in determinate fasi della sviluppo del quale gli oggetti definiti "emergono" o "si generano"). Un esempio di definizione costruttiva per induzione è la definizione delle posizioni degli scacchi ammissibili (cioè le posizioni che possono apparire sulla scacchiera durante la partita). La parte base contiene un'unità. posizione di partenza. La parte induttiva contiene le regole per le mosse dei pezzi. L'insieme delle posizioni ammissibili viene così effettivamente generato. Un altro esempio di insieme effettivamente generato è l'insieme di tutte le formule dimostrabili di un k.-l. sistema formale o calcolo: la parte base della definizione delle formule dimostrabili contiene assiomi, la parte induttiva contiene regole di inferenza (gli assiomi si dichiarano dimostrabili per definizione e quindi si dice che se qualche formula è dimostrabile, allora le formule da esse ottenute secondo alle regole di inferenza sono anche dimostrabili). Il processo di generazione qui è il processo di dimostrazione di tutte le formule dimostrabili. Infine, anche il processo di confutazione di tutte le formule falsificabili nel calcolo infinitesimale è un esempio di processo generativo efficace. Il concetto di processo di generazione efficace è strettamente correlato al concetto di A. Abbiamo dato una definizione (approssimativa) di processo di generazione efficace basata sul concetto di A. A sua volta, il concetto di processo di generazione ci consente di definire sulla sua base, se non il concetto stesso di A, almeno il concetto di funzione calcolabile. Infatti, supponiamo che un certo processo di generazione sia in grado di “generare” oggetti che hanno la forma di coppie (x, y), e che due coppie “generate” qualsiasi con primi termini coincidenti abbiano anche gli stessi secondi termini. Quindi segue il processo. definisce la funzione y = f(x) in questo modo: la funzione è definita per l'oggetto x0 se e solo se x0 è il primo membro della c.-l. coppia generata: il valore delle funzioni per l'argomento x0 è in questo caso uguale al secondo membro di questa coppia. La funzione definita nel decreto. nel senso di un processo di generazione efficace, è ovviamente calcolabile [per trovare f(x0), dobbiamo espandere il processo fino a trovare coppie con x0 come primo termine]. Viceversa, ogni funzione computabile può essere definita mediante un processo di generazione efficiente. Algoritmico processi e processi generatori sono logicamente vicini tra loro. Punti di vista. Ognuno di essi si basa solo su concetti costruttivi. La differenza tra loro è che l'algoritmo il processo si svolge sulla base di un'esigenza, e il processo generativo si svolge sulla base del permesso di agire in un certo modo. Qui si manifesta la differenza tra il necessario e il possibile (in un processo algoritmico ogni fase è univocamente, cioè necessariamente, determinata dalla fase precedente, mentre quando il processo generativo si dispiega dopo ogni fase, per quella successiva si presentano solo una moltitudine di possibilità) palcoscenico). Affinando opportunamente il concetto di processo di generazione efficace, risulta che ogni insieme effettivamente generato è enumerabile, e viceversa. Questa circostanza, combinata con le relazioni di cui sopra tra insiemi enumerabili e decidibili, ci consente di concludere quanto segue. Qualsiasi classe di oggetti che ammette una definizione costruttiva per genere e differenza specifica ammette anche una definizione costruttiva per induzione, ma non viceversa: esiste una classe di oggetti che è costruttivamente definita per induzione, ma non consente una definizione costruttiva per genere e differenza specifica; L'aggiunta a questa classe di oggetti (oltre all'insieme che la racchiude di oggetti strutturali) non consente un'efficace definizione induttiva. Ogni processo generativo costruttivo può essere rappresentato come un processo per ottenere formule dimostrabili di un calcolo opportuno. Pertanto, un esempio di classe che possiede le proprietà appena descritte può essere costruito come una classe di tutte le formule dimostrabili di un certo calcolo. Inoltre, si è scoperto che questa circostanza si verifica per chiunque sia sufficientemente contenuto. calcolo (ad esempio, per il calcolo dei predicati o per i calcoli che formalizzano l'aritmetica), perché se il calcolo è sufficientemente significativo, allora in esso può esprimersi qualsiasi processo generatore efficace. La classe di tutte le formule dimostrabili di un tale calcolo (essendo, ovviamente, enumerabili) non è decidibile, quindi non esiste alcun algoritmo che riconosca la dimostrabilità delle formule del calcolo; in questo senso il calcolo si dice indecidibile. Poiché la classe di tutte le formule di calcolo dimostrabili non è decidibile, sarà complementare. per esso la classe di tutte le formule indimostrabili non è enumerabile e, quindi, non può essere ottenuta mediante alcun processo di generazione; in particolare, è impossibile costruire un calcolo del genere, che “confuterebbe” tutte le formule indimostrabili dell'originale. calcolo e solo loro; Inoltre, tutte queste formule indimostrabili non possono essere confutate con i mezzi dell'originale. calcolo, quindi all'inizio. nel calcolo ci sono i cosiddetti formule indecidibili (cioè né dimostrabili né confutabili). In queste considerazioni possiamo limitarci solo a tali formule, che contengono. le interpretazioni del calcolo infinitesimale esprimono proposizioni significative (cioè vere o false) e, quindi, trovano proposizioni indecidibili tra tali formule. Ne consegue che è possibile presentare una formula che esprima un giudizio vero, ma non dimostrabile nel calcolo; in questo senso il sistema si dice incompleto. Sottolineiamo che, data la natura generale del ragionamento svolto, la proprietà di incompletezza è inerente ad ogni argomento sufficientemente contenuto. calcolo. Il concetto di indecidibilità del calcolo infinitesimale si basa sul concetto di aritmetica, e non sorprende che il fatto di indecidibilità sia stabilito sulla base di ricerche nel campo della teoria del calcolo infinitesimale.Molto significativo (e forse inaspettato a prima vista) è il fatto che una logica così generale. un fatto come l'incompletezza dei calcoli (fatto che esprime l'impossibilità fondamentale di formalizzare completamente il processo di inferenza logica e dimostrato per la prima volta in modo rigoroso dallo scienziato austriaco K. Gödel nel lontano 1931, prima che il concetto di “A.”) fosse chiarito, può essere ottenuto, come abbiamo appena visto, mediante la teoria dell'aritmetica, il che già da sola dimostra le enormi possibilità di applicazione della teoria dell'aritmetica a questioni di logica. Queste applicazioni non si limitano all'esempio fornito. Nel 1932 i sovietici. lo scienziato A. N. Kolmogorov ha proposto un'interpretazione della logica costruttiva creata dagli intuizionisti utilizzando contiene. significa che non hanno nulla a che vedere con gli atteggiamenti dell'intuizionismo; vale a dire, Kolmogorov proponeva di interpretare ogni frase di logica costruttiva come un problema. Il concetto di problema richiedeva però una specificazione, che poteva essere data solo sulla base della teoria di A già sviluppata. Due classi specifiche di problemi adatte all'interpretazione della logica costruttiva furono rispettivamente proposte dall'Amer. lo scienziato SK Kleene nel 1945 e i gufi. scienziato Yu T. Medvedev nel 1955. Nel 1956 gufi. lo scienziato N.A. Shanin ha proposto un nuovo concetto, secondo il quale non tutte le affermazioni di logica costruttiva richiedono l'interpretazione sotto forma di problema. Questo circolo di idee include le questioni di “costruttivizzazione”, o “trovare analoghi costruttivi”, classiche. matematico concetti e proposte; anche la soluzione a questi problemi è possibile solo sulla base della teoria A. Costruttivizzazione della base. concetti matematici l'analisi ha portato al cosiddetto ora in fase di sviluppo. matematica costruttiva analisi. Vengono delineati i modi di costruttivizzazione e altri aspetti matematici. teorie. Uno dei principali Le tecniche utilizzate nella costruttivizzazione è il passaggio dagli oggetti studiati ai loro nomi, che sono sempre oggetti costruttivi. SOLUZIONE DEI PROBLEMI. Un caso speciale di problemi di massa è la risoluzione dei problemi. Problemi di risoluzione di k.-l. di un insieme è il problema di costruire un algoritmo che risolva questo insieme. Corrispondente una serie di problemi individuali qui consiste nel risolvere la questione dell'appartenenza a un insieme posto per ciascun oggetto dall'insieme comprensivo di oggetti costruttivi. Al contrario, qualsiasi problema di massa, rispettivamente. una serie di problemi individuali di risposta a una domanda, può essere considerata come un problema di risoluzione di un certo insieme, vale a dire l'insieme di quei problemi individuali, la cui risposta è "sì". Ciò rende chiaro l’importante ruolo della risoluzione dei problemi. Erano quelli che venivano studiati dal punto di vista. la loro risolvibilità. Tra i problemi di soluzione spiccano quelli posti per classi di formule di calcolo dimostrabili. Il problema di risolvere la classe di tutte le formule dimostrabili di k.-l. calcolo chiamato anche il problema di risolvere il calcolo stesso. (Nei testi russi, il problema della risoluzione è solitamente chiamato “problema di risolubilità”; tuttavia, il “problema di risolubilità” è meglio chiamato problema: “rispondere se un dato problema ha una soluzione”). Problemi di massa irrisolvibili. Il problema del permesso per k.-l. Nel calcolo c'è sempre il problema di risolvere un insieme enumerabile. In generale, tutti i problemi di risoluzione che sono sorti naturalmente in matematica si sono rivelati problemi di risoluzione di insiemi enumerabili. Questo è il primo esempio sopra menzionato di un problema di soluzione insolubile (e allo stesso tempo il primo esempio di un problema di massa insolubile in generale), pubblicato da Church nel 1936. Questo è il cosiddetto il problema dell'identità per i sistemi associativi, le prove dell'indecidibilità della forma furono pubblicate nel 1947 indipendentemente l'una dall'altra da A. A. Markov e Amer. lo scienziato EL Post; questo risultato è interessante in quanto primo esempio di prova dell’irrisolvibilità di un problema di massa sorto (già nel 1914) al di fuori della logica e della teoria: è il famoso problema dell’identità dei gruppi, posto nel 1912, la cui irrisolvibilità era dimostrato nel 1952. scienziato P. S. Novikov (Premio Lenin, 1957). Ciascuno dei problemi di identità consiste nel trovare un algoritmo che stabilisca l'equivalenza o la non equivalenza di due parole di un dato alfabeto (se si tratta di un sistema associativo o di un gruppo dipende dall'una o dall'altra definizione di equivalenza). Pertanto, il problema dell'identità può essere considerato come un problema di risoluzione dell'insieme di tutte le coppie di parole equivalenti tra loro (rispetto all'insieme di tutte le possibili coppie di parole). Inoltre, poiché è possibile specificare un processo generativo per ottenere tutte le coppie di parole equivalenti tra loro, l'insieme di tutte queste coppie è enumerabile. Consistenza. A partire dall'esempio di Church nel 1936 e proseguendo fino al 1944, tutte le prove dell'irrisolvibilità dei problemi di massa furono eseguite o potevano essere eseguite nel modo seguente. metodo uniforme. Il problema evidentemente irrisolvibile studiato da Church è stato ridotto al problema di massa in esame, così che se il problema di massa in questione fosse risolvibile, allora anche il problema di Church sarebbe risolvibile (in questo senso possiamo dire che la prova dell'indecidibilità del problema in esame si riduceva alla prova dell'indecidibilità del problema di Chiesa). Sorse la questione se per qualsiasi problema di soluzione insolubile la sua irrisolvibilità possa essere stabilita in questo modo. Questa domanda, chiamata problema della riducibilità, fu posta da Post nel 1944; Allo stesso tempo, Post ha fornito diversi esempi di problemi di soluzione irrisolvibili, la cui irrisolvibilità è stata da lui stabilita utilizzando un metodo diverso da quello sopra descritto (questi esempi non hanno ancora risolto il problema della riducibilità, poiché rimaneva aperta la questione se fosse era impossibile per loro trovare tali prove di irrisolvibilità, che furono ridotte a dimostrare l'irrisolvibilità del problema di Church; successivamente, per alcuni degli esempi sopra riportati, tali prove furono effettivamente trovate). Il problema della riducibilità fu al centro delle ricerche sulla teoria dell'aritmetica fino al 1956, quando fu risolto autonomamente dall'Unione Sovietica. scienziato A.A. Muchnik e Amer. scienziato R. M. Friedberg. Ha costruito un esempio di un problema di soluzione indecidibile (per un insieme enumerabile), la cui indecidibilità non può essere dimostrata riducendo il problema di Church a questo problema. Muchnik ha dimostrato ancora di più, e cioè che non solo il problema di Chiesa, ma nessun altro problema può servire come un “problema indecidibile standard”, nel senso che la prova dell’indecidibilità di qualsiasi problema con soluzione indecidibile per un insieme enumerabile potrebbe

Comprensibilità - l'algoritmo deve consistere in comandi “comprensibili” per l'esecutore (inclusi nel sistema dei comandi dell'esecutore).

Discrezione (discontinuità, separatezza) - l'algoritmo deve rappresentare il processo di risoluzione di un problema come esecuzione sequenziale di passaggi semplici (o precedentemente definiti).

Certezza - cioè. Ogni regola dell’algoritmo deve essere chiara, inequivocabile e non lasciare spazio ad arbitrarietà. Grazie a questa proprietà, l'esecuzione dell'algoritmo è di natura formale e non richiede alcuna istruzione o informazione aggiuntiva sul problema da risolvere.

Efficacia (o finitezza) - l'algoritmo deve portare alla soluzione del problema (o alla risposta che non esiste soluzione) in un numero finito di passaggi.

Carattere di massa - l'algoritmo per risolvere il problema è sviluppato in una forma generale, vale a dire 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 determinata area, chiamata area di applicabilità dell'algoritmo.

La caratteristica principale di qualsiasi algoritmo è la sua esecuzione formale, che consente di eseguire determinate azioni (comandi) non solo da parte di esseri umani, ma anche da dispositivi tecnici (esecutori). Pertanto, gli esecutori di algoritmi possono essere, ad esempio, una persona, un computer, una stampante, un manipolatore robotico, una macchina utensile a controllo numerico, una cellula vivente, un animale addestrato, un programma informatico, un virus informatico, un “ tartaruga” in Logowriter o Logomirs (esecutore geometrico) e così via.

L'esecutore dell'algoritmo è un dispositivo di controllo collegato ad un insieme di strumenti. Il dispositivo di controllo comprende gli algoritmi e ne organizza l'esecuzione comandando gli strumenti appropriati. E gli strumenti eseguono azioni eseguendo comandi dal dispositivo di controllo. Prima di creare un algoritmo per risolvere un problema, è necessario scoprire quali azioni può eseguire l'esecutore proposto.

Queste azioni sono chiamate azioni valide dell'esecutore. Solo loro possono essere utilizzati.

L'esecutore degli algoritmi computazionali è chiamato calcolatrice. Una calcolatrice può gestire numeri e variabili che rappresentano numeri. Pertanto, un algoritmo è una sequenza organizzata di azioni accettabili per alcuni esecutori. Lo stesso artista può essere simulato su un computer in molti modi.

Complessità dell'algoritmo

La complessità dell'algoritmo ci consente di stimare quanto velocemente cresce la complessità dell'algoritmo all'aumentare della quantità di dati di input. L’intensità del lavoro si riferisce al numero di operazioni elementari che devono essere eseguite per risolvere un problema utilizzando un dato algoritmo. Tipicamente, la stima della complessità dell'algoritmo è espressa come O(f(N)), dove O è la funzione di complessità e N è il numero di casi o esempi elaborati. I meno costosi sono gli algoritmi per i quali la funzione di complessità ha la forma f(N)=C e f(N)=C*N, dove C è una costante. Nel primo caso i costi computazionali non dipendono dalla quantità di dati elaborati, nel secondo caso aumentano linearmente. I più costosi sono gli algoritmi la cui complessità ha una potenza e una dipendenza fattoriale dal numero di osservazioni elaborate.

ORDINAMENTO

L'ordinamento è il processo di disposizione di molti oggetti informativi simili in ordine crescente o decrescente in base ai loro valori. Ad esempio, un elenco i di n elementi verrà ordinato in ordine crescente di valori di elemento se i<= i <= ... <= i.

Esistono due tipi di algoritmi di ordinamento: ordinamento di array, che possono essere posizionati nella memoria operativa o su disco come file ad accesso diretto, e ordinamento di file sequenziali situati su dischi o nastri magnetici.

La differenza principale tra l'ordinamento dell'array e l'ordinamento sequenziale dei file è che ciascun elemento dell'array è accessibile in qualsiasi momento. Ciò significa che in qualsiasi momento qualsiasi elemento dell'array può essere confrontato con qualsiasi altro elemento dell'array e due elementi qualsiasi dell'array possono scambiarsi di posto. Al contrario, in un file sequenziale è disponibile un solo elemento alla volta. A causa di queste differenze, i metodi di ordinamento differiscono in modo significativo tra i due tipi di ordinamento.

In generale, quando si ordinano i dati, solo una parte delle informazioni viene utilizzata come chiave di ordinamento, utilizzata nei confronti. Quando viene eseguito uno scambio, viene trasferita l'intera struttura dei dati.

METODI DI RICERCA

La ricerca di informazioni in un array non ordinato richiede la scansione sequenziale dell'array. La scansione inizia dal primo elemento e termina trovando un elemento o raggiungendo la fine dell'array. Questo metodo dovrebbe essere utilizzato per dati non ordinati, ma può essere utilizzato anche per dati ordinati. Se i dati vengono ordinati, è possibile utilizzare la ricerca binaria, che è molto più veloce.

un sistema di regole, formulato in un linguaggio comprensibile all'esecutore, che determina il processo di transizione da dati iniziali accettabili a un risultato certo e ha le proprietà di massa, finitezza, certezza e determinismo.

La parola “algoritmo” deriva dal nome del grande scienziato dell’Asia centrale dell’VIII-IX secolo. Al-Khorezmi (regione storica di Khorezm nel territorio del moderno Uzbekistan). Delle opere matematiche di Al-Khorezmi, solo due sono pervenute a noi: algebrica (dal titolo di questo libro è nata la parola algebra) e aritmetica. Il secondo libro fu considerato perduto per molto tempo, ma nel 1857 la sua traduzione in latino fu ritrovata nella biblioteca dell'Università di Cambridge. Descrive quattro regole delle operazioni aritmetiche, quasi le stesse che vengono utilizzate oggi. Le prime righe di questo libro sono state tradotte così: “Said Algorithm. Diamo la dovuta lode a Dio, nostro leader e protettore”. Quindi il nome Al-Khorezmi divenne Algorithm, da cui deriva la parola algoritmo. Il termine algoritmo venne utilizzato per designare quattro operazioni aritmetiche, e fu in questo significato che entrò in alcune lingue europee. Ad esempio, nell'autorevole dizionario inglese Dizionario del Nuovo Mondo Webster, pubblicato nel 1957, la parola algoritmo è etichettata come "obsoleta" e viene spiegata come l'esecuzione di operazioni aritmetiche utilizzando numeri arabi.

La parola “algoritmo” venne nuovamente utilizzata con l’avvento dei computer elettronici per denotare un insieme di azioni che compongono un determinato processo. Ciò implica non solo il processo di risoluzione di un determinato problema matematico, ma anche una ricetta culinaria e istruzioni per l'uso della lavatrice, e molte altre regole sequenziali che non hanno nulla a che fare con la matematica; tutte queste regole sono algoritmi. La parola "algoritmo" è nota a tutti in questi giorni; è entrata nel linguaggio colloquiale con tale sicurezza che ora le espressioni "algoritmo di comportamento", "algoritmo di successo", ecc. si trovano spesso sulle pagine dei giornali e nei discorsi di politici.

Turing A. Può una macchina pensare?? M., Mir, 1960
Uspensky V. L'auto di Posta. Scienza, 1988
Cormen T., Leiserson, Rives R. Algoritmi. Costruzione e analisi. M., MTsNMO, 1999

Trova "ALGORITMO" su

Sicuramente si può dire che molti hanno familiarità con il termine “algoritmo”. È ampiamente utilizzato e non solo nel campo della tecnologia e della programmazione informatica. È anche innegabile che molti abbiano formato una propria (anche se per lo più intuitiva) comprensione del significato di questo termine.

Il termine "algoritmo" deriva dal nome del matematico medievale Abu Ja'far ibn Musa al-Khwarizmi. La revisione dell'ultima parte del nome dello scienziato nei paesi europei ha portato alla formazione del termine "algoritmo" o "algoritmo". Gli europei, che iniziarono a padroneggiare il moderno sistema di numeri decimali nel XII secolo, conobbero le opere degli scienziati arabi, e il lavoro del suddetto residente di Khorezm, dedicato alle regole di conteggio nel sistema di numeri decimali, fu largamente risaputo. Pertanto, il contenuto del termine “algoritmo” era il seguente: operazioni sui numeri.

Nel corso dei secoli, la vecchia e precedente comprensione di questo termine cominciò ad andare perduta e questo termine cominciò ad essere applicato a un unico algoritmo: l'algoritmo euclideo, progettato per trovare il massimo comun divisore di una coppia di numeri interi.

4.1. Definizione di algoritmo

Il contenuto moderno del concetto di algoritmo può essere definito come segue.

Algoritmo– una descrizione esatta che definisce un processo algoritmico che inizia con un dato iniziale arbitrario (da un certo insieme di dati iniziali possibili per un dato algoritmo) ed è finalizzato a ottenere un risultato completamente determinato da questi dati iniziali.

Processo algoritmico– il processo di trasformazione sequenziale di oggetti costruttivi (parole, numeri, coppie di parole, coppie di numeri, frasi, ecc.), che avviene in “passi” discreti. Ogni passaggio consiste nel sostituire un oggetto strutturale con un altro.

Poiché gli algoritmi possono essere applicati a oggetti molto arbitrari (numeri, lettere, parole, grafici, espressioni logiche, ecc.), la definizione di un algoritmo utilizza un termine speciale - "oggetto costruttivo", che combina tutti questi casi possibili. Pertanto, nell'algoritmo descritto di seguito, gli oggetti costruttivi possono essere intesi come triple di numeri.

4.2. Proprietà dell'algoritmo

Qualsiasi algoritmo deve avere le seguenti proprietà:

discrezione(ciò significa che l'algoritmo è una sequenza finita di singoli passaggi, ognuno dei quali definisce un'azione completata);

determinismo(ciò significa che ogni passaggio dell'algoritmo deve essere comprensibile all'esecutore e non deve essere interpretato in modo ambiguo);

carattere di massa(ciò significa che l'algoritmo dovrebbe essere progettato per implementare un'intera classe di compiti simili e non per un compito specifico);

efficacia(questo significa che l'algoritmo deve portare allo stesso risultato con gli stessi dati iniziali, tranne quando l'algoritmo è parzialmente o completamente basato su azioni con numeri pseudo-casuali, e in un tempo finito).

Per specificare un algoritmo è necessario descriverne i seguenti elementi:

un insieme di oggetti che costituiscono la totalità dei possibili dati iniziali, risultati intermedi e finali;

regola di inizio;

regola per l'elaborazione diretta delle informazioni (descrizione della sequenza di azioni);

regola finale;

regola per l'estrazione dei risultati.

L'algoritmo è sempre progettato per un artista specifico. Nel nostro caso, un tale artista è un computer. Per garantire la possibilità di implementazione su un computer, l'algoritmo deve essere descritto in un linguaggio comprensibile al computer, cioè in un linguaggio di programmazione.

4.3. Modi fondamentali per descrivere gli algoritmi

I modi principali per descrivere gli algoritmi includono quanto segue:

verbale-formulare (passo dopo passo);

diagramma strutturale o a blocchi;

utilizzando diagrammi grafici;

utilizzando reti di Petri.

Prima di elaborare programmi, vengono spesso utilizzati metodi verbali-formulari e diagrammi di flusso.

Metodo passo passo (formula verbale).. L'algoritmo è scritto sotto forma di testo con formule punto per punto ( passi), che determina la sequenza delle azioni. Ciascuno dei passaggi rappresenta un'azione completata molto specifica.

Un esempio di descrizione di un algoritmo. Risoluzione di equazioni quadratiche. In modo verbale e stereotipato, l'algoritmo per risolvere questo problema può essere scritto nella seguente forma:

Passaggio 1: inserisci tre numeri UN,B,C.

Passaggio 2. Calcola il discriminante

Passaggio 3. Controllare la condizione: se D<0, то идти на шаг 8, иначе идти на шаг 4.

Passaggio 4. Calcola la prima radice

Passaggio 5. Calcola la seconda radice

Passaggio 6. Stampa due numeri X 1 ,X 2 .

Passaggio 7. Vai al passaggio 9.

Passaggio 8. Visualizza il testo "L'equazione non ha radici reali".

Passaggio 9. Fine.

Diagramma a blocchiè un grafo diretto, i cui vertici possono essere uno dei tre tipi mostrati in Fig. 6.1.

Parte superiore funzionale usato per rappresentare la funzione: X→Y.

Vertice predicativo utilizzato per rappresentare una funzione (o predicato) P:X→(T,F), ovvero un'espressione logica che trasferisce il controllo lungo uno dei due possibili rami.

Composizione (seguente)	Scelta (ramificazione)	Iterazione (ciclo)

Picco unificante rappresenta il trasferimento del controllo da una delle due filiali entranti a una filiale uscente.

Diagramma a blocchiè uno schema a blocchi che può essere espresso come una composizione di quattro schemi a blocchi elementari (Fig. 4.1).

Qualsiasi programma macchina può essere rappresentato da uno schema a blocchi.

Una caratteristica importante delle strutture di cui sopra è che hanno un input e un output.

Programmazione strutturata– il processo di sviluppo di algoritmi utilizzando diagrammi a blocchi strutturali.

Più in generale, la programmazione strutturata consente una maggiore varietà di strutture di controllo rispetto alle quattro proposte. La ragione per espandere la varietà delle strutture è il requisito di praticità e naturalezza.

Programmazione top-downè il processo di suddivisione passo passo di un algoritmo in parti sempre più piccole al fine di ottenere elementi per i quali è possibile scrivere comandi specifici. La programmazione strutturata top-down è un processo di programmazione top-down limitato all'uso di diagrammi a blocchi strutturati.

La programmazione strutturata è una delle tecnologie di programmazione più utilizzate. Si presta la massima attenzione alla fase di progettazione del programma, durante la quale si raccomanda di attenersi ai seguenti principi fondamentali, denominati principi della programmazione strutturata:

principio di modularità;

principio dello sviluppo del programma dall'alto verso il basso;

controllo strutturale end-to-end;

il principio della struttura semplice del programma.

Questi principi, proposti dagli specialisti americani alla fine del XX secolo, rimangono rilevanti anche ai nostri giorni, soprattutto quando si sviluppano sistemi software grandi e complessi.