Il concetto di esecutore dell'algoritmo è un sistema di comandi dell'esecutore. Tipi di algoritmi - Ipermercato della conoscenza

Algoritmo e sue proprietà.

Algoritmo- un'istruzione comprensibile e precisa per l'esecutore per eseguire la sequenza finale di comandi che portano dai dati iniziali al risultato desiderato.

Esecutore di algoritmi- questo è l'oggetto o il soggetto per il quale è redatto l'algoritmo.

Il sistema di comando dell'esecutore (SKI) è l'intero insieme di comandi che l'esecutore può eseguire.

Proprietà dell'algoritmo: comprensibilità, accuratezza, finitezza.

Comprensibilità: l'algoritmo è composto solo dai comandi inclusi nello SKI dell'esecutore.

Precisione: ogni comando dell'algoritmo di controllo determina l'azione univoca dell'esecutore.

Finalità (o prestazione): l'esecuzione dell'algoritmo dovrebbe portare a un risultato in un numero finito di passaggi.

Ambiente dell'esecutore: l'ambiente in cui opera l'esecutore.

Una certa sequenza di azioni dell'esecutore si applica sempre ad alcuni dati di base... Ad esempio, per preparare un piatto secondo una ricetta, sono necessari i prodotti corrispondenti (dati). Per risolvere un problema matematico (risolvere un'equazione quadratica), sono necessari dati numerici iniziali (coefficienti di equazione).

Set di dati completo: un insieme di dati necessario e sufficiente per risolvere il problema (ottenere il risultato desiderato).

Metodi per la scrittura di algoritmi.

I metodi più comuni sono: grafico, verbale e nella forma programmi per computer.

Modo grafico presuppone l'uso di determinati simboli grafici - blocchi.

Nome blocco	Designazione del blocco	Contenuto
Processi		Elaborazione dati
Il processo decisionale		Unità logica per verificare la verità o la falsità di alcune condizioni
Trasferimento dati		Input o output di informazioni
Inizia, fermati		Inizio o fine del programma
Modifica		Organizzazione del processo ciclico - intestazione del ciclo

La raccolta di blocchi forma il cosiddetto diagramma di flusso.

notazione verbale Gli algoritmi si concentrano principalmente sull'esecutore umano e consentono registrazioni diverse delle istruzioni, ma la registrazione deve essere sufficientemente accurata.

Quando si scrivono algoritmi nella forma programmi per i computer vengono utilizzati linguaggi di programmazione: sistemi di codifica delle prescrizioni e regole per il loro utilizzo. La scrittura di algoritmi sotto forma di programmi è caratterizzata da un alto grado di formalizzazione.

Algoritmi per lavorare con le quantità. Strutture algoritmiche di base.

Una quantità è un oggetto informazioni separato che ha un nome, un valore e un tipo.

L'esecutore di algoritmi per lavorare con le quantità può essere una persona o un dispositivo tecnico speciale, come un computer. Un tale artista deve avere memoria per la memorizzazione dei valori.

Le quantità sono costanti e variabili.

Valore costante (costante) non cambia il suo valore durante l'esecuzione dell'algoritmo. Una costante può essere indicata dal proprio valore (numeri 10, 3.5) o da un nome simbolico (numero).

Variabile può modificare il valore durante l'esecuzione dell'algoritmo. Una variabile è sempre indicata da un nome simbolico (X, A, R5, ecc.).

Tipo di quantità definisce l'insieme di valori che un valore può assumere e un insieme di azioni che possono essere eseguite su questo valore. Tipi fondamentali di valori: intero, reale, simbolico, logico.

Espressione- un record che definisce la sequenza di azioni sui valori. Un'espressione può contenere costanti, variabili, segni di operazione, funzioni. Esempio:

A + B; 2 * X-Y; K + L - peccato (X)

Un comando di assegnazione è un comando di esecuzione, in conseguenza del quale una variabile ottiene un nuovo valore. Formato del comando:

nome variabile>: = espressione>

Il comando di assegnazione viene eseguito nel seguente ordine: prima viene calcolato, quindi il valore risultante viene assegnato a una variabile.

Esempio. Lascia che la variabile A abbia il valore 6. Quale valore riceverà la variabile A dopo aver eseguito il comando: A: = 2 * A - 1?
Soluzione. La valutazione dell'espressione 2 * A - 1 con A = 6 darà il numero 11. Quindi il nuovo valore della variabile A sarà uguale a 11.

In quanto segue, si assumerà che l'esecutore di algoritmi per lavorare con le quantità è un computer... Qualsiasi algoritmo può essere costruito dai comandi Compiti, ingresso, ritiro, ramificazione e ciclo.

Comando di input- un comando mediante il quale vengono impostati i valori delle variabili tramite dispositivi di input (ad esempio una tastiera).

Esempio: ingresso A - inserendo il valore della variabile A dalla tastiera del computer.

Comando di output: il comando mediante il quale viene visualizzato il valore di un valore sul dispositivo di output del computer (ad esempio, sul monitor).

Esempio: produzione X - il valore della variabile X viene visualizzato sullo schermo.

Comando di ramo- divide l'algoritmo in due percorsi a seconda di una certa condizione; quindi l'esecuzione dell'algoritmo passa ad una continuazione generale. La ramificazione è completa e incompleta. Descrizione della ramificazione negli schemi a blocchi e in linguaggio algoritmico:

Qui, una serie fa riferimento a uno o più comandi sequenziali; kv - fine della ramificazione.

Comando ciclo prevede l'esecuzione ripetuta di una sequenza di comandi (loop body) secondo alcune condizioni.

Ciclo con precondizione- un ciclo, la cui esecuzione viene ripetuta finché la condizione del ciclo è vera:

Ciclo con parametro- esecuzione ripetuta del corpo del ciclo mentre il parametro intero percorre l'insieme di tutti i valori dall'iniziale (In) al finale (Ik):

Esempio. Si danno due semplici frazioni. Crea un algoritmo per ottenere la frazione che è il risultato della loro divisione.
Soluzione. In forma algebrica, la soluzione al problema si presenta così:
a/b: c/d = a * d/b * c = m/n
I dati iniziali sono quattro valori interi: a, b, c, d. Il risultato sono due interi m e n.

alga divisione di frazioni
intatto a, b, c, d, m, n
avviare l'input a, b, c, d
m: = a * d
n: = b * c
output "Numeratore =", m
output "Denominatore =", n
koi

Nota che per visualizzare il testo (qualsiasi sequenza di caratteri), deve essere scritto tra virgolette nel comando produzione.

1. Efimova O., Morozov V., Ugrinovich N. Il corso di tecnologia informatica con le basi dell'informatica. Libro di testo per le classi senior. - M.: OOO "Casa Editrice AST"; ABF, 2000
2. Libro dei problemi sull'informatica. In 2 volumi / Ed. I. Semakin, E. Henner. - M.: Laboratorio delle Conoscenze di Base, 2001
3. Ugrinovich N. Informatica e tecnologie dell'informazione. Grade 10-11 - M .: Laboratorio di conoscenze di base, JSC "Libri di testo di Mosca", 2001

Problemi e test sul tema "Algoritmi ed esecutori"

• Disegnatore per la gestione dell'esecutore - Algoritmi di grado 6

  Lezioni: 4 Compiti: 9 Prove: 1

• 2 Compiti: 9 Prove: 1

Caro studente!

La conoscenza dell'argomento "Algoritmi ed Esecutori" è necessaria prima di tutto per un approfondimento della programmazione. Il linguaggio di programmazione QBasic è stato scelto come base per l'apprendimento della programmazione. Abbiamo abbandonato l'idea di includere Visual Basic o qualsiasi altro linguaggio di programmazione orientato agli oggetti nel nostro corso, poiché questo approccio non è ancora stato ampiamente utilizzato nella maggior parte delle scuole secondarie della Federazione Russa. Inoltre, la programmazione orientata agli oggetti si basa sui principi della programmazione classica in Dos.

Il nostro corso è progettato per un programma di istruzione generale. Quando ti prepari per gli esami di ammissione in tecnologia dell'informazione alle università, devi familiarizzare con le specifiche dello studio della programmazione in questa università. In alcuni casi è necessario approfondire alcuni argomenti, come ad esempio "Array". Dovresti prestare attenzione a questo quando studi la letteratura sulla programmazione, forse dovresti usare le raccomandazioni metodologiche per la preparazione degli esami, che sono attualmente pubblicate nella maggior parte degli istituti di istruzione superiore.

In conclusione, notiamo che il raggiungimento di "acrobazie aeree" nella programmazione è possibile solo con la pratica costante e la risoluzione di problemi applicati specifici.

La parola "algoritmo" deriva dal nome del matematico arabo del IX secolo al-Khwarizmi, che formulò le regole per eseguire operazioni aritmetiche.

Algoritmo- un'istruzione accurata e comprensibile all'esecutore per eseguire la sequenza finale di comandi che portano dai dati iniziali al risultato iniziale.

Esempi: routine quotidiana, procedura di cottura, istruzioni, ecc.)

Esecutore di algoritmiÈ colui che esegue l'algoritmo (uomo, animale, macchina, computer).

Sistema di comando dell'esecutore- questo è l'intero insieme di comandi che l'esecutore sa eseguire (capisce). L'algoritmo può essere costruito solo dai comandi inclusi nel sistema di comandi dell'esecutore.

ad esempio, esecutore Il robot può eseguire comandi avanti, indietro, sinistra, destra, dipingere. Si muove intorno a un campo di celle, delimitato da un muro e contenente muri. Il robot non può attraversare il muro.

Proprietà dell'algoritmo:

1.Efficienza (arto)- la possibilità di ottenere il risultato dai dati iniziali in un numero finito di passaggi. (Ad esempio, quando si esegue l'algoritmo di addizione, 2 numeri dovrebbero ottenere la somma).

2.Personaggio di massa- la capacità di applicare l'algoritmo a un gran numero di dati di input diversi. (Ad esempio, puoi aggiungere 2 numeri qualsiasi, conoscendo l'algoritmo di addizione.)

3.Determinismo(certezza, accuratezza) - ogni squadra deve definire in modo univoco l'azione dell'esecutore.

4.Comprensibilità- il comando deve essere scritto in un linguaggio comprensibile al computer.

5.Discrezione- suddividere l'algoritmo in comandi separati.

Metodi di registrazione dell'algoritmo:

1) In linguaggio naturale: registrazione sotto forma di comandi separati in una lingua comprensibile a una persona.

2) Grafica - nel linguaggio degli schemi a blocchi, utilizzando forme geometriche (ovale, rettangolo, parallelogramma, rombo).

3) In un linguaggio algoritmico - un linguaggio per scrivere algoritmi per l'insegnamento della programmazione. Le squadre sono registrate in russo.

4) In un linguaggio di programmazione - un programma. Linguaggi di programmazione: Basic, Pascal, C, Visual Basic.

B7 Strutture algoritmiche di base: following, branching, loop; l'immagine negli schemi a blocchi. Suddivisione delle attività in sottoattività. Algoritmi ausiliari.

Costruzioni algoritmiche. All'interno degli algoritmi, si possono distinguere gruppi di passaggi che differiscono nella loro struttura interna - costruzioni algoritmiche.

Costrutti algoritmici di base sono sequenza lineare di passaggi (o sequenziamento), ramificazione e loop.

Viene chiamato un algoritmo in cui i comandi vengono eseguiti in sequenza uno dopo l'altro algoritmo lineare.

Ecco come appare un algoritmo lineare nel linguaggio dei diagrammi a blocchi:

Esempio: algoritmo per l'accensione del computer:

1. Accendere il computer (premere il pulsante sul limitatore di sovratensione).
2. Accendi il monitor, la stampante.
3. Premere il pulsante di accensione sull'unità di sistema.
4. Attendi fino a quando il sistema operativo viene caricato e viene visualizzato il desktop.
5. Andare al lavoro.

In questo algoritmo, tutte le azioni devono essere eseguite in sequenza una dopo l'altra: non è possibile iniziare a lavorare se l'alimentazione o il monitor non sono accesi.

La struttura algoritmica" ramificazione"È incluso condizione, a seconda della verità della condizione, viene eseguita l'una o l'altra sequenza di comandi (serie).

Una condizione è un'affermazione che può essere vera o falsa. Nella condizione, due numeri, due stringhe, due variabili o espressioni stringa vengono confrontati tra loro mediante operazioni di confronto (>,<, =, >=, <=).

Scrittura in linguaggio algoritmico: If Condition Then Series 1 (If Condizioneè vero, allora Serie 1, Se Condizioneè falso, quindi non viene eseguito nulla). Esempio: se oggi è domenica, non è necessario che tu vada a scuola. Modulo di diramazione completo

Nelle strutture algoritmiche ciclo include una serie di comandi che vengono eseguiti più volte. Questa sequenza di comandi è chiamata corpo del ciclo.

Le strutture algoritmiche cicliche sono di due tipi:

• contacicli, in cui il corpo del ciclo viene eseguito un certo numero di volte;
• cicli condizionali, in cui il corpo del ciclo viene eseguito finché la condizione è soddisfatta.

Ciclo con contatore- si usa quando si sa in anticipo quante ripetizioni del corpo ciclo devono essere eseguite.

Il concetto di algoritmo. Esecutori di algoritmi. Proprietà dell'algoritmo

Il concetto di algoritmo è fondamentale per l'informatica quanto il concetto di informazione. Esistono molte definizioni diverse di un algoritmo, poiché questo concetto è piuttosto ampio e viene utilizzato in vari campi della scienza, della tecnologia e della vita quotidiana.

L'algoritmo è una sequenza di azioni comprensibile e precisa che descrive il processo di trasformazione di un oggetto da uno stato iniziale a uno stato finale.

Un algoritmo è una descrizione precisa di una sequenza di azioni volte a risolvere un determinato problema, destinate a uno specifico esecutore.

Esecutore l'algoritmo può essere una persona (ricette, istruzioni varie, algoritmi per calcoli matematici) o un dispositivo tecnico. Varie macchine (computer, robot industriali, moderni elettrodomestici) sono esecutori formali algoritmi. L'esecutore formale non è tenuto a comprendere l'essenza del problema da risolvere, ma è richiesta l'esatta esecuzione della sequenza di comandi.

L'algoritmo può essere scritto in vari modi (descrizione verbale, descrizione grafica - diagramma a blocchi, programma in uno dei linguaggi di programmazione, ecc.). Un programma è un algoritmo scritto inlinguaggio di programmazione .

Per creare un algoritmo (programma), devi sapere:

un set completo di dati iniziali del problema (lo stato iniziale dell'oggetto);

lo scopo della creazione dell'algoritmo (lo stato finale dell'oggetto);

il sistema di comando dell'esecutore (ovvero un insieme di comandi che l'esecutore comprende e può eseguire).

L'algoritmo (programma) risultante deve avere il seguente insieme di proprietà:

discrezione (l'algoritmo è diviso in passaggi separati - comandi);

univocità (ogni comando determina l'unica azione possibile dell'esecutore);

intelligibilità (tutti i comandi dell'algoritmo sono inclusi nel sistema di comando dell'esecutore);

efficienza (l'esecutore deve risolvere il problema in un numero finito di passaggi).

La maggior parte degli algoritmi ha anche la proprietà carattere di massa (usando lo stesso algoritmo si possono risolvere molti problemi simili).

Metodi per descrivere gli algoritmi

È stato notato sopra che lo stesso algoritmo può essere scritto in modi diversi. L'algoritmo può essere scritto linguaggio naturale. Pertanto, utilizziamo ricette, istruzioni, ecc. Per algoritmi di registrazione destinati a esecutori formali, speciali linguaggi di programmazione... Qualsiasi algoritmo può essere descritto graficamente sotto forma di diagramma a blocchi... Per questo, è stato sviluppato un sistema di notazione speciale:

Designazione	Descrizione	Note (modifica)
	Inizio e fine dell'algoritmo
	Input e output di dati.	L'output dei dati è talvolta indicato in modo diverso:
	Azione	Negli algoritmi di calcolo, questo è l'assegnamento
	Forchetta	Fork: un componente necessario per implementare rami e loop
	Inizio ciclo con parametro
	Processo tipico	In programmazione, procedure o sottoprogrammi
	Transizioni tra i blocchi

Facciamo un esempio di descrizione di un algoritmo per sommare due quantità sotto forma di diagramma a blocchi:

Questo modo di descrivere l'algoritmo è il più grafico e comprensibile per gli umani. Pertanto, gli algoritmi degli esecutori formali vengono solitamente sviluppati prima sotto forma di diagramma a blocchi e solo dopo creano un programma su uno deilinguaggi di programmazione .

Strutture algoritmiche tipiche

Il programmatore ha la capacità di progettare e utilizzare strutture algoritmiche atipiche, tuttavia ciò non è necessario. Qualsiasi algoritmo arbitrariamente complesso può essere sviluppato sulla base di tre strutture tipiche: successione, ramificazione e ripetizione. In questo caso, le strutture possono essere disposte in sequenza una dopo l'altra o annidate l'una nell'altra.

Struttura lineare (segue)

La struttura algoritmica più semplice è lineare. In esso, tutte le operazioni vengono eseguite una volta nell'ordine in cui sono scritte.

ramificazione

V ramificazione completa ci sono due opzioni per le azioni dell'esecutore, a seconda del valore dell'espressione logica (condizione). Se la condizione è vera, verrà eseguito solo il primo ramo, altrimenti verrà eseguito solo il secondo ramo.

Il secondo ramo può essere vuoto. Questa struttura si chiama ramificazione o attraversamento incompleto.

Da più rami è possibile costruire la struttura” scelta"(Multiple branching), che sceglierà non tra due, ma tra un numero maggiore di opzioni per le azioni dell'esecutore, a seconda di diverse condizioni. È essenziale che venga eseguito un solo ramo: in una tale struttura, l'ordine delle condizioni diventa importante: se vengono soddisfatte più condizioni, solo una funzionerà, la prima dall'alto.

Ciclo (ripetizione)

Ciclopermette di organizzare più ripetizioni della stessa sequenza di comandi- si chiama corpo del ciclo. In vari tipi di algoritmi di looping, il numero di ripetizioni può dipendere dal valore di un'espressione logica (condizione) o può essere codificato nella struttura stessa. Ci sono cicli: " prima di», « Ciao», cicli con un contatore. Nei cicli "before" e "while" un'espressione logica (condizione) può precedere il corpo del ciclo ( ciclo di precondizioni) o terminare il ciclo ( ciclo di postcondizione).

Cicli« prima di"- ripetizione del corpo del ciclo finché la condizione non è soddisfatta:

Cicli « Ciao"- ripetizione del corpo del ciclo mentre la condizione è soddisfatta(vero):

Cicli contatore(con parametro)- ripetizione del corpo del ciclo un dato numero di volte:

Algoritmo ausiliario (sottoprogramma, procedura)

Algoritmo di supporto è un modulo a cui è possibile accedere più volte dall'algoritmo principale. L'uso di algoritmi di supporto può ridurre significativamente le dimensioni dell'algoritmo e semplificarne lo sviluppo.

Metodi per lo sviluppo di algoritmi complessi

Esistono due metodi per sviluppare algoritmi complessi:

Metodo di dettaglio dell'attività sequenziale("Top-down") è che il problema complesso originale è diviso in sottoattività. Ciascuno dei sottoproblemi viene considerato e risolto separatamente. Se una qualsiasi delle attività secondarie è difficile, viene suddivisa anche in attività secondarie. Il processo continua fino a quando i compiti secondari non si riducono a quelli elementari. Le soluzioni dei singoli sottoproblemi vengono quindi raccolte in un unico algoritmo per risolvere il problema originale. Il metodo è ampiamente utilizzato perché consente a più programmatori di sviluppare contemporaneamente un algoritmo generale che risolva attività secondarie locali. Questo è un prerequisito per il rapido sviluppo di prodotti software.

Metodo di assemblaggio("Bottom-up") consiste nel creare un insieme di moduli software che implementano la soluzione di attività tipiche. Quando risolve un problema complesso, il programmatore può utilizzare i moduli sviluppati come algoritmi ausiliari (procedure). In molti sistemi di programmazione Esistono già insiemi simili di moduli, che semplificano e velocizzano notevolmente la creazione di un algoritmo complesso.

Algoritmi e processi di controllo

Controllo - interazione mirata di oggetti, alcuni dei quali sono di controllo, altri sono controllati.

Nel caso più semplice, ci sono due di questi oggetti:

Da un punto di vista informatico le azioni di controllo possono essere considerate come informazioni di controllo. Le informazioni possono essere trasmesse sotto forma di comandi. La sequenza di comandi per controllare l'oggetto, che porta a un obiettivo predeterminato, si chiama algoritmo di controllo... Di conseguenza, l'oggetto di controllo può essere chiamato l'esecutore dell'algoritmo di controllo. Nell'esempio sopra, l'oggetto di controllo funziona "senza guardare" ciò che accade all'oggetto di controllo ( controllo ad anello aperto aprire... Un altro schema di controllo può prendere in considerazione le informazioni sui processi che si verificano nell'oggetto di controllo:

In questo caso, l'algoritmo di controllo deve essere sufficientemente flessibile per analizzare queste informazioni e prendere una decisione sulle sue ulteriori azioni a seconda dello stato dell'oggetto di controllo ( controllo del feedback). Questo schema di controllo è chiamato Chiuso.

Più in dettaglio, vengono studiati i processi di controllo. cibernetica... Questa scienza sostiene che i più diversi processi di gestione nella società, nella natura e nella tecnologia si verificano in modo simile, obbediscono agli stessi principi.

All'inizio dell'argomento

Si prega di sospendere AdBlock su questo sito.

In questa lezione analizzeremo alcuni dei concetti teorici che formalizza il concetto di programmazione. Allo stesso tempo, formuleremo in modo più preciso il compito principale della tua formazione.

Per cominciare, ti suggerisco di giocare un po' con il seguente giocattolo per bambini. Completa i primi cinque compiti, torna indietro e continua a leggere la lezione.

Fig. 1 Schermata del campo di gioco su code.org

Spero che tu abbia successo. Ora, usando questo esempio, descriveremo alcuni concetti di base:

• esecutore;
• sistema di comandi esecutori;
• algoritmo.

Nel giocattolo controlliamo un uccello rosso. Il compito di ogni fase: portare l'uccello al maiale. L'uccello può eseguire determinati comandi, ad esempio: andare avanti, girare a sinistra, girare a destra, ecc.

Una persona, una macchina o un dispositivo in grado di eseguire determinati comandi è chiamato esecutore. In questo giocattolo, ovviamente, l'esecutore è un uccello. Viene chiamato l'insieme di comandi che l'esecutore comprende e sa eseguire il sistema di comando dell'esecutore.

La sequenza di comandi che l'esecutore deve eseguire per risolvere il problema è chiamata algoritmo.

È necessario concentrarsi su diversi punti.

L'esecutore può eseguire solo quei comandi che sono inclusi nel suo sistema di comando.

Ciò significa, ad esempio, che non puoi scrivere all'interprete di uccelli: "Vai dal maiale!" Più precisamente, puoi scrivere, ma non succederà nulla, tk. l'esecutore di tali comandi non lo sa.

Puoi scrivere i comandi esistenti nell'ordine che ritieni corretto. Il tuo compito come programmatore è dividere un compito grande e complesso in piccoli passaggi separati, ognuno dei quali sarà chiaro all'esecutore. Divide et impera di nuovo funziona.

L'esecutore fa esattamente ciò che l'algoritmo gli dice di fare.

L'artista degli uccelli è molto fiducioso. Non mette in discussione ciò che scrivi nel programma. Se, ad esempio, dimentichi di aprire l'uccello, si schianterà contro il muro. Pertanto, devi occuparti di tutto da solo.

I tuoi programmi futuri spesso non funzioneranno come volevi. Gli errori capitano a tutti. È importante capire che questo non è uno sciocco del computer, ma hai commesso un errore nell'algoritmo. Non essere come i cattivi programmatori che hanno sempre la colpa del programma.

Ora, da un esempio illustrativo, passiamo alle realtà informatiche. Scriviamo programmi per un computer, il che significa che il computer nel nostro caso è un esecutore. Sistema di comando - funzioni standard e costrutti del linguaggio C.

Qual è il compito principale del tuo insegnamento delle basi della programmazione? Padroneggia l'abilità del pensiero algoritmico. Cioè, impara come scrivere la soluzione a vari problemi sotto forma di un algoritmo per un artista specifico (nel nostro caso, un computer).

Quindi, per riassumere:

Programma per computer- un algoritmo per risolvere un problema, scritto in un linguaggio di programmazione.

Algoritmo: una descrizione esatta dell'ordine delle azioni che devono essere eseguite dall'esecutore per risolvere il problema.

Esecutore: una persona o un dispositivo in grado di comprendere ed eseguire un determinato insieme di comandi.

ARGOMENTO 8. FONDAMENTI DI ALGORITMIZZAZIONE E PROGRAMMAZIONE

8.1. Il concetto di algoritmo e l'esecutore degli algoritmi. Proprietà dell'algoritmo

"Algoritmo" è un concetto fondamentale in informatica. La sua comprensione è necessaria per l'applicazione efficace della tecnologia informatica alla risoluzione di problemi pratici. Un algoritmo è una prescrizione per un esecutore (una persona o un automa) per eseguire una sequenza ben definita di azioni volte al raggiungimento di un determinato obiettivo. Un algoritmo è una regola formulata in un linguaggio che indica azioni, la cui esecuzione sequenziale porta dai dati iniziali al risultato desiderato. Significato della parola algoritmo molto simile al significato delle parole ricetta, procedimento, metodo, modo... Tuttavia, qualsiasi algoritmo, a differenza di una ricetta o di un metodo, ha necessariamente le seguenti proprietà.
Proprietà dell'algoritmo (distinguendolo da qualsiasi altra prescrizione): intelligibilità(per un esecutore specifico); discrezione(i comandi sono sequenziali, con fissazione esatta dei momenti di inizio e fine esecuzione del comando); precisione(dopo l'esecuzione di ogni comando, si sa con certezza se l'esecuzione dell'algoritmo è terminata o quale comando deve essere eseguito successivamente); efficienza(dopo un numero finito di passaggi, il problema è risolto o diventa chiaro che il processo di soluzione non può essere continuato): carattere di massa(l'algoritmo viene applicato uniformemente a qualsiasi specifica formulazione del problema per il quale è stato sviluppato).
1. Discretezza: suddivisione dell'algoritmo in una serie di azioni complete separate - passaggi. L'esecuzione dell'algoritmo è suddivisa in una sequenza di azioni completate - passaggi. Ogni azione deve essere completata dall'esecutore dell'algoritmo prima di procedere all'esecuzione dell'azione successiva.
2. Precisione: istruzioni univoche. Ad ogni passo viene determinata in modo univoco la trasformazione degli oggetti dell'ambiente dell'executor ottenuti nei passi precedenti dell'algoritmo. Se un algoritmo viene applicato ripetutamente allo stesso set di dati di input, ottiene ogni volta lo stesso risultato. La registrazione dell'algoritmo dovrebbe essere tale che ad ogni passo della sua esecuzione sia noto quale comando dovrebbe essere eseguito successivamente.
3. Comprensibilità: comprensione ed esecuzione inequivocabili di ogni passaggio dell'algoritmo da parte del suo esecutore. L'algoritmo deve essere scritto in un linguaggio comprensibile all'esecutore.
4. Efficacia - la ricezione obbligatoria del risultato in un numero finito di passaggi. Ogni passaggio (e l'algoritmo nel suo insieme) dopo il suo completamento fornisce un ambiente in cui tutti gli oggetti sono definiti in modo univoco. Se ciò è impossibile per qualche motivo, l'algoritmo dovrebbe segnalare che non esiste una soluzione al problema. L'algoritmo deve essere completato in un numero finito di passaggi. L'informatica opera solo con oggetti finiti e processi finiti, quindi la questione di considerare algoritmi infiniti rimane al di fuori del quadro della teoria degli algoritmi. 5. Carattere di massa: l'applicazione dell'algoritmo alla soluzione di un'intera classe di problemi dello stesso tipo.
Il sistema di comando dell'esecutore è una situazione descritta con precisione, compresa la formulazione del problema da risolvere, un elenco di oggetti coinvolti nella condizione del problema e nella sua soluzione e le capacità dell'esecutore: proprietà degli oggetti che può riconoscere e le azioni che può compiere. L'esecuzione formale dell'algoritmo viene eseguita dal compilatore o dall'interprete, controllando la semantica.

8.2. Metodi di registrazione dell'algoritmo

In pratica, le seguenti forme di algoritmi di scrittura sono le più comuni:
1) registrazione grafica (schemi a blocchi);
2) notazione verbale (pseudocodici);
3) linguaggio di programmazione.
La forma verbale dell'algoritmo è una descrizione in linguaggio naturale delle successive fasi di elaborazione dei dati. Il metodo verbale non è molto diffuso, poiché tali descrizioni non sono strettamente formalizzate, consentono ambiguità nell'interpretazione delle singole prescrizioni. Un algoritmo scritto utilizzando lo pseudocodice è una descrizione semi-formalizzata in un linguaggio algoritmico condizionale, che include sia gli elementi di base del linguaggio di programmazione che le frasi del linguaggio naturale, la notazione matematica generalmente accettata e altri.
Una notazione grafica, chiamata anche diagramma di algoritmo, è un'immagine di un algoritmo sotto forma di una sequenza di blocchi funzionali interconnessi, ciascuno dei quali corrisponde all'esecuzione di una o più azioni. La notazione grafica è più compatta e visiva rispetto a quella verbale. Nello schema dell'algoritmo, ad ogni tipo di azione corrisponde una figura geometrica. Le forme sono collegate con linee di transizione che determinano l'ordine in cui vengono eseguite le azioni.
La forma grafica di registrazione, detta anche diagramma a blocchi o diagramma a blocchi di un algoritmo, è un'immagine di un algoritmo sotto forma di una sequenza di blocchi funzionali interconnessi, ciascuno dei quali corrisponde all'esecuzione di una o più azioni.
In quanto segue, useremo algoritmo dei diagrammi di flusso v. Consentono di presentare gli algoritmi in una forma più visiva, questo rende possibile analizzare il loro lavoro, cercare errori nella loro implementazione, ecc. I diagrammi di flusso hanno sempre Inizio e la fine, denotato da ellissi, tra di loro - la sequenza passi algoritmo collegato frecce.

Ci sono passaggi incondizionato(raffigurato da rettangoli, parallelogrammi) e condizionale(raffigurato da rombi). Dal rombo escono sempre due frecce: una indica il percorso ulteriore, se la condizione è soddisfatta (di solito indicata dalla parola "sì" o "+"), l'altra - il mancato adempimento (la parola "no" o "- "). L'immissione da tastiera o la visualizzazione del valore di un'espressione è rappresentata da un parallelogramma. Il comando che esegue l'elaborazione dell'azione (comando di assegnazione) è mostrato in un rettangolo.

Se la soluzione al problema è complessa e sufficientemente lunga, l'algoritmo può rivelarsi molto grande. Ciò può essere evitato sostituendo alcune sequenze complete di passaggi dell'algoritmo con blocchi, che saranno algoritmi ausiliari. Il blocco di solito non è elementare, le sue dimensioni vengono scelte a seconda delle necessità, tuttavia, se correttamente composto, ha tutti i segni necessari di un passaggio algoritmico: ha un punto di ingresso (un inizio ben definito) e può essere condizionale o incondizionato. Diversi blocchi dell'algoritmo sono collegati tra loro solo attraverso i punti di ingresso e di uscita, quindi se il blocco risolve correttamente il suo problema, la sua struttura interna è insignificante per il resto dell'algoritmo. Tale rappresentazione dei blocchi è particolarmente conveniente nelle prime fasi della risoluzione di problemi complessi, quando i dettagli dei blocchi vengono eseguiti in seguito e, possibilmente, da altri sviluppatori.
Un linguaggio di programmazione è un linguaggio utilizzato per scrivere formalmente algoritmi. La maggior parte dei linguaggi di programmazione sono classificati come linguaggi algoritmici. Scrivere un algoritmo in un linguaggio algoritmico si chiama programma.
Il linguaggio usato per scrivere formalmente gli algoritmi si chiama linguaggio algoritmico... Quando si descrive qualsiasi lingua (incluso naturale, ad esempio russo, inglese, ecc.), Vengono utilizzati i seguenti concetti: alfabeto, sintassi e semantica.
Alfabeto la lingua è un insieme dei segni più semplici che possono essere utilizzati nei testi di questa lingua. La sequenza di caratteri nell'alfabeto si chiama parola... Le regole secondo le quali le parole sono formate dall'alfabeto sono chiamate grammatica. Lui stesso linguaggioè un insieme di tutte le parole scritte in un dato alfabeto secondo una data grammatica.
Sintassiè un insieme di regole che determinano possibili combinazioni (costruzioni) dalle lettere dell'alfabeto. Per descrivere la sintassi di una lingua, di norma, utilizzare un'altra lingua (metalinguaggio) o diagrammi di sintassi.
Semanticaè un insieme di regole che determinano il significato (significato) dei costrutti linguistici individuali.
Uno dei linguaggi algoritmici più comuni è il Pascal, utile sia per i principianti che per i programmatori esperti. L'educazione alla programmazione si basa molto spesso su questo linguaggio.

8.3. Costrutti algoritmici di base

La struttura dell'algoritmo può essere rappresentata più chiaramente utilizzando uno schema a blocchi in cui vengono utilizzate figure geometriche (blocchi), collegate da frecce che indicano la sequenza di azioni. Sono stati adottati alcuni standard per le rappresentazioni grafiche dei blocchi. Ad esempio, un comando per l'elaborazione delle informazioni viene inserito in un blocco che assomiglia a un rettangolo, un controllo delle condizioni - in un rombo, un comando di input o output - in un parallelogramma e un ovale indica l'inizio e la fine dell'algoritmo.
L'unità elementare strutturale dell'algoritmo è un semplice comando che designa una fase elementare dell'elaborazione o della visualizzazione delle informazioni. Un semplice comando in linguaggio schematico è rappresentato come un blocco funzione.

	Questo blocco ha un ingresso e una via d'uscita... Da semplici comandi e condizioni di controllo, si formano comandi composti che hanno una struttura più complessa e anche un ingresso e un'uscita. L'approccio strutturale allo sviluppo degli algoritmi determina l'uso delle sole strutture algoritmiche di base (costruzioni): inseguimento, ramificazione, ripetizione, che dovrebbero essere formalizzate in modo standard.
	Consideriamo le strutture principali dell'algoritmo. Squadra seguenti consiste solo di semplici comandi. Nella figura, i comandi semplici hanno un simbolo S1 e S2... Gli algoritmi lineari sono formati dai comandi follow. Un esempio di algoritmo lineare sarebbe trovare la somma di due numeri immessi dalla tastiera.
	Squadra ramificazioneè un comando composto dell'algoritmo, in cui, a seconda della condizione P, uno S1, o altro S2 azione. Gli algoritmi di fork (algoritmi di ramificazione) sono composti da comandi follow e comandi di ramificazione. Un esempio di un algoritmo di ramificazione sarebbe trovare il più grande di due numeri immessi dalla tastiera.
	Il comando branch può essere completo o incompleto. La forma incompleta del comando branch viene utilizzata quando è necessario eseguire un'azione S solo se la condizione è soddisfatta P... Se la condizione P non viene rispettato, il comando branch esce senza eseguire alcuna azione. Un esempio di un comando di ramificazione incompleto sarebbe dimezzare solo un numero pari.
	Squadra ripetizioniè un comando composto dell'algoritmo, in cui, a seconda della condizione Rè possibile l'esecuzione multipla dell'azione S... Gli algoritmi ciclici (algoritmi di ripetizione) sono composti da comandi di inseguimento e comandi di ripetizione. La figura mostra un comando di ripetizione con una precondizione. Si chiama così perché viene verificata prima la condizione e solo dopo viene eseguita l'azione. Inoltre, l'azione viene eseguita finché la condizione è soddisfatta. Un esempio di algoritmo ciclico può essere il seguente. Mentre i numeri positivi vengono inseriti dalla tastiera, l'algoritmo trova la loro somma. Il comando di ripetizione con una precondizione non è l'unico possibile. Una variazione del comando di ripetizione della precondizione è il comando di ripetizione del parametro. Viene utilizzato quando è noto il numero di ripetizioni di un'azione. Nello schema a blocchi di un comando di ripetizione con un parametro, la condizione non è scritta in un rombo, ma in un esagono. Un esempio di algoritmo ciclico con un parametro sarebbe trovare la somma dei primi 20 numeri naturali.
	In un comando di ripetizione con una postcondizione, l'azione viene eseguita per prima S e solo allora è la condizione P... Inoltre, l'azione viene ripetuta fino a quando la condizione non è soddisfatta. Un esempio di un comando di ripetizione con una postcondizione sarebbe quello di diminuire un numero positivo finché non è non negativo. Non appena il numero diventa negativo, il comando di ripetizione termina il suo lavoro. Collegando solo queste strutture elementari (in sequenza o per annidamento), è possibile "assemblare" un algoritmo di qualsiasi grado di complessità.

Ogni costruzione indicata può essere implementata senza modifiche nella struttura in qualsiasi linguaggio di programmazione, ad esempio in Pascal e BASIC. Pertanto, è necessario comporre correttamente un algoritmo utilizzando uno schema a blocchi e solo allora, sapendo come sono scritti i comandi in un linguaggio di programmazione specifico, digitare il programma su un computer e ottenere il risultato eseguendolo per l'esecuzione.

8.4. Algoritmo lineare

Facciamo un esempio di scrittura di un algoritmo sotto forma di diagramma a blocchi, pseudocodici e in Pascal. Il test manuale e la selezione del sistema di test vengono eseguiti nello stesso modo dell'attività precedente.

8.5. Algoritmo di fork

Ecco un esempio di scrittura di un algoritmo di ramificazione per trovare il più grande di due numeri.

8.6. Algoritmo ciclico

Consideriamo un algoritmo per trovare la somma dei primi numeri dispari naturali fino a n... Rappresentiamo la registrazione dell'algoritmo in tre modi: sotto forma di diagramma a blocchi, un linguaggio algoritmico scolastico e nel linguaggio di programmazione Pascal.

Lo schema a blocchi è costituito dalle seguenti strutture di base: due comandi composti (un comando di inseguimento e un comando di ripetizione con una precondizione), quindi un comando semplice. Tutti i comandi sono collegati in serie. I costrutti sono progettati in modo standard, quindi sono facili da riconoscere e da tradurre nel linguaggio di programmazione. Ogni struttura ha un ingresso e un'uscita.
Le frecce tratteggiate nella tabella mostrano la sequenza della catena tecnologica. Dopo aver scritto l'algoritmo sotto forma di diagramma a blocchi, ogni squadra viene tradotta nel linguaggio algoritmico della scuola e solo successivamente nel linguaggio di programmazione.
Scriviamo un algoritmo per calcolare la somma dei primi n numeri naturali. Per fare ciò, utilizzeremo un ciclo con un parametro, poiché è noto in anticipo quante volte verrà eseguito il comando per trovare la somma. In tutti i collegamenti della catena, cambieremo il ciclo "ciao" nel ciclo "per" e forniremo un esempio di traduzione dell'algoritmo dal linguaggio del diagramma di flusso al linguaggio algoritmico della scuola e al linguaggio di programmazione Pascal.

Considera di trovare il numero di numeri naturali la cui somma non è maggiore di uno dato. Per fare ciò, useremo il comando ripeti con una postcondizione.

Domande per l'autocontrollo

1. Il concetto di algoritmo. Proprietà dell'algoritmo. Un esempio di algoritmo. Il concetto di "variabile".
2. Operatore di assegnazione. Esempi.
3. Stili di programmazione (logico, funzionale).
4. Comprendere una subroutine, un modulo e un oggetto
5. Che cos'è una variabile? Regole di denominazione delle variabili in Pascal. Esempi.
6. Operatore di assegnazione. Scrivere espressioni in Pascal. Esempi. Spiega come funziona l'operatore x: = x + 1;
7. Operatori di input e output in Pascal. Esempi. Uscita formattata.
8. Operatore condizionale ( Se). Esempio. Confronta con operatore Astuccio.
9. Operatore di selezione. Esempio. Confronta con operatore Se.
10. Espressioni logiche. operazioni o, e e non... Esempi. Tavolo della verità.
11. Tipi numerici di variabili in Pascal. Regole di conversione dei tipi. Esempi.
12. Tipo di dati booleano. Un esempio di utilizzo nel programma. Tipo di dati carattere. Esempio. Funzioni chr e ordina, successo e pred.
13. matrici. Definizione. Indici di matrice. Dichiarazioni di matrice. Accesso agli elementi dell'array. Matrici unidimensionali e bidimensionali. Esempi. Somiglianze e differenze tra array e stringhe.
14. Procedure. Definizione. Perché sono necessarie procedure? Esempi. Regole per la descrizione delle procedure. Confronta procedure e funzioni.