| § 2.1. Algoritmi ed esecutori

Lezione 14
§ 2.1. Algoritmi ed esecutori

Parole chiave:

Algoritmo
proprietà dell'algoritmo (discretezza; comprensibilità; certezza; efficacia; carattere di massa)
esecutore
caratteristiche dell'esecutore (gamma di compiti da risolvere; ambiente; modalità di funzionamento; sistema di comando)
esecuzione formale dell'algoritmo

2.1.1. Il concetto di algoritmo

Ogni persona nella vita di tutti i giorni, a scuola o al lavoro, risolve un numero enorme di compiti di complessità molto diversa. I problemi difficili richiedono molta riflessione per trovare una soluzione; compiti semplici e familiari che una persona risolve senza pensare, automaticamente. Nella maggior parte dei casi, la soluzione a ciascun problema può essere suddivisa in semplici passaggi (passaggi). Per molte di queste attività (installazione di software, montaggio di un armadio, creazione di un sito Web, utilizzo di un dispositivo tecnico, acquisto di un biglietto aereo tramite Internet, ecc.), sono già state sviluppate e vengono offerte istruzioni dettagliate, con sequenza esecuzione di cui è possibile ottenere il risultato desiderato.

Esempio 1 Il compito "Trova la media aritmetica di due numeri" viene risolto in tre passaggi:

1) pensa a due numeri;
2) sommare due numeri concepiti;
3) Dividere l'importo ricevuto per 2.

Esempio 2 L'attività "Deposita denaro sul conto telefonico" è suddivisa nei seguenti passaggi:

1) andare al terminale di pagamento;
2) scegliere un operatore di telecomunicazioni;
3) inserire un numero di telefono;
4) verificare la correttezza del numero inserito;
5) inserire una banconota nell'accettatore di banconote;
6) attendere un messaggio sull'accredito di denaro sul conto;
7) ottenere un assegno.

Esempio 3 Le fasi della risoluzione del problema "Disegna un riccio divertente" sono presentate graficamente:

Trovare la media aritmetica, depositare denaro su un conto telefonico e disegnare un riccio sono, a prima vista, processi completamente diversi. Ma hanno una caratteristica comune: ciascuno di questi processi è descritto da una sequenza di brevi istruzioni, il cui seguito esatto consente di ottenere il risultato desiderato. Le sequenze di indicazioni fornite negli esempi 1-3 sono algoritmi per risolvere i problemi corrispondenti. L'esecutore di questi algoritmi è una persona.

L'algoritmo può essere una descrizione di una sequenza di calcoli (esempio 1) o di passaggi non matematici (esempi 2-3). Ma in ogni caso, prima del suo sviluppo, devono essere chiaramente definite le condizioni iniziali (dati iniziali) e ciò che si vuole ottenere (risultato). Possiamo dire che un algoritmo è la descrizione di una sequenza di passaggi nella risoluzione di un problema che porta dai dati iniziali al risultato desiderato.

In generale, lo schema dell'algoritmo può essere rappresentato come segue (Fig. 2.1).

Riso. 2.1. Schema generale dell'algoritmo

Gli algoritmi sono le regole di addizione, sottrazione, moltiplicazione e divisione dei numeri studiate a scuola, molte regole grammaticali, regole di costruzioni geometriche, ecc.

Le animazioni "Lavorare con l'algoritmo" (193576), "Greatest common divisore" (170363), "Least common multiple" (170390) ti aiuteranno a ricordare alcuni degli algoritmi appresi nelle lezioni di lingua russa e matematica (http: //sc.edu.ru /).

Esempio 4 Alcuni algoritmi portano al fatto che da una stringa di caratteri si ottiene una nuova stringa come segue:

1. Viene calcolata la lunghezza (in caratteri) della stringa di caratteri originale.
2. Se la lunghezza della catena originale è dispari, il numero 1 viene assegnato alla catena originale sulla destra, altrimenti la catena non cambia.
3. I simboli vengono scambiati a coppie (il primo - con il secondo, il terzo - con il quarto, il quinto - con il sesto, ecc.).
4. Sulla destra, il numero 2 è assegnato alla catena ricevuta.

La catena risultante è il risultato dell'algoritmo.

Quindi, se la catena originale era A # B, il risultato dell'algoritmo sarà la catena # A1B2 e se la catena originale era ABC @, il risultato dell'algoritmo sarà la catena BA @ B2.

2.1.2. Esecutore di algoritmi

Ogni algoritmo è progettato per un esecutore specifico.

Un esecutore testamentario è un oggetto (una persona, un animale, un dispositivo tecnico) in grado di eseguire un determinato insieme di comandi.

Distinguere interpreti formali e informali. Un esecutore formale esegue sempre lo stesso comando allo stesso modo. Un esecutore informale può eseguire un comando in diversi modi.

Consideriamo più in dettaglio l'insieme degli esecutori formali. Gli esecutori formali sono estremamente diversi, ma per ciascuno di essi possono essere indicate le seguenti caratteristiche: la gamma di compiti da risolvere (appuntamento), l'ambiente, il sistema di comando e la modalità di funzionamento.

Gamma di compiti da risolvere. Ogni esecutore è creato per risolvere una certa gamma di compiti: costruire catene di simboli, eseguire calcoli, disegnare immagini su un piano, ecc.

Ambiente esecutore. L'area, l'ambiente, le condizioni in cui opera l'esecutore sono solitamente chiamati l'ambiente dell'esecutore. I dati di input e i risultati di qualsiasi algoritmo appartengono sempre all'ambiente dell'executor a cui è destinato l'algoritmo.

Sistema di comando dell'esecutore. L'istruzione all'esecutore di eseguire un'azione separata completata è chiamata comando. L'insieme di tutti i comandi che possono essere eseguiti da un determinato esecutore costituisce un sistema di comando di questo esecutore (CIS). L'algoritmo viene compilato tenendo conto delle capacità di un particolare esecutore, in altre parole, nel sistema di comando dell'esecutore che lo eseguirà.

Modalità di funzionamento dell'esecutore. Per la maggior parte degli artisti, vengono fornite le modalità di controllo diretto e di controllo del programma. Nel primo caso, l'esecutore si aspetta comandi da una persona ed esegue immediatamente ogni comando in arrivo. Nel secondo caso, all'esecutore viene prima data una sequenza completa di comandi (programma), quindi esegue tutti questi comandi in modalità automatica. Un certo numero di artisti lavora solo in una di queste modalità.

Considera esempi di artisti.

Esempio 5 L'esecutore Turtle si muove sullo schermo del computer, lasciando una traccia sotto forma di linea.

Il sistema di comando della Tartaruga è composto dai seguenti comandi:

1. Avanti n (dove n è un numero intero) - fa sì che la tartaruga muova n passi nella direzione del movimento - nella direzione in cui sono girati la testa e il corpo;
2. Right m (dove m è un numero intero) - fa sì che la tartaruga cambi direzione di m gradi in senso orario.
Registrazione Ripetere k[<Команда1> <Команда2> ... <Командаn>] significa che la sequenza di comandi tra parentesi verrà ripetuta k volte.

Pensa a quale figura apparirà sullo schermo dopo che la tartaruga avrà eseguito il seguente algoritmo.
Ripeti 12 [Destra 45 Avanti 20 Destra 45]

Esempio 6 Sistema di comando dell'esecutore La calcolatrice è composta da due comandi, a cui sono assegnati dei numeri:

1 - sottrarre 1
2 - moltiplica per 3

Il primo riduce il numero di 1, il secondo aumenta il numero di 3 volte. Quando si scrivono algoritmi, per brevità, vengono indicati solo i numeri dei comandi. Ad esempio, l'algoritmo 21212 indica la seguente sequenza di comandi:

Moltiplica per 3
sottrarre 1
moltiplicare per 3
sottrarre 1
moltiplicare per 3

Con questo algoritmo, il numero 1 verrà convertito in 15:

((1 3 - 1) 3 - 1) 3 = 15.

Esempio 7 Il Robot Esecutore opera su un campo a scacchi, tra celle adiacenti di cui possono esserci dei muri. Il robot si muove attraverso le celle del campo e può eseguire i seguenti comandi, a cui sono assegnati dei numeri:

1 - su
2 - giù
3 - giusto
4 rimanenti

Quando ciascuno di questi comandi viene eseguito, il Robot si sposta alla cella successiva nella direzione specificata. Se c'è un muro tra le celle in questa direzione, il Robot viene distrutto.

Cosa accadrà al Robot se esegue la sequenza di comandi 32323 (qui i numeri indicano i numeri di comando) a partire dalla cella A? Quale sequenza di comandi deve eseguire il Robot per spostarsi dalla cella A alla cella B senza urtare le pareti?

Quando si sviluppa un algoritmo:

1) si distinguono gli oggetti che compaiono nell'attività, si stabiliscono le proprietà degli oggetti, le relazioni tra gli oggetti e le possibili azioni con gli oggetti;
2) vengono determinati i dati iniziali e il risultato richiesto;
3) viene determinata la sequenza di azioni dell'esecutore, che garantisce il passaggio dai dati iniziali al risultato;
4) la sequenza delle azioni viene registrata utilizzando i comandi inclusi nel sistema di comando dell'esecutore.

Possiamo dire che un algoritmo è un modello dell'attività di un esecutore di algoritmi.

2.1.3. Proprietà dell'algoritmo

Non qualsiasi istruzione, sequenza di prescrizioni o piano d'azione può essere considerato un algoritmo. Ogni algoritmo ha necessariamente le seguenti proprietà: discrezione, comprensibilità, certezza, efficienza e carattere di massa.

Proprietà discreta significa che il modo per risolvere il problema è suddiviso in fasi separate (azioni). Ogni azione corrisponde a una prescrizione (comando). Solo dopo aver eseguito un comando, l'esecutore può iniziare a eseguire il comando successivo.

proprietà di comprensibilità significa che l'algoritmo è costituito solo da comandi inclusi nel sistema di comando dell'esecutore, cioè da tali comandi che l'esecutore può percepire e sui quali può eseguire le azioni richieste.

Proprietà di definizione significa che non ci sono comandi nell'algoritmo, il cui significato può essere interpretato in modo ambiguo dall'esecutore; Le situazioni sono inaccettabili quando, dopo aver eseguito il comando successivo, non è chiaro all'esecutore quale comando eseguire successivamente. Per questo motivo, il risultato dell'algoritmo è determinato in modo univoco dall'insieme di dati di input: se l'algoritmo viene applicato più volte allo stesso insieme di dati di input, l'output è sempre lo stesso risultato.

proprietà prestazionale significa che l'algoritmo deve garantire che il risultato sia ottenuto dopo un numero finito, possibilmente molto grande, di passaggi. In questo caso, il risultato è considerato non solo la risposta dovuta alla formulazione del problema, ma anche la conclusione che è impossibile continuare per qualsiasi motivo la soluzione di questo problema.

Proprietà di massa significa che l'algoritmo deve fornire la possibilità della sua applicazione di risolvere qualsiasi problema da una certa classe di problemi. Ad esempio, un algoritmo per trovare le radici di un'equazione quadratica dovrebbe essere applicabile a qualsiasi equazione quadratica, un algoritmo di attraversamento stradale dovrebbe essere applicabile a qualsiasi punto della strada, un algoritmo di preparazione del medicinale dovrebbe essere applicabile alla preparazione di qualsiasi importo, ecc. .

Esempio 8 Si consideri uno dei metodi per trovare tutti i numeri primi che non eccedano un numero naturale n. Questo metodo è chiamato il "setaccio di Eratostene" dal nome dell'antico scienziato greco Eratostene (3° secolo aC) che lo propose.

Per trovare tutti i numeri primi non maggiori di un dato numero n, seguendo il metodo di Eratostene, è necessario eseguire i seguenti passaggi:

1) scrivi in ​​fila tutti i numeri naturali da 2 a n (2, 3, 4, ..., n);
2) racchiudere in una cornice 2 - il primo numero primo;
3) eliminare dall'elenco tutti i numeri divisibili per l'ultimo numero primo trovato;
4) trova il primo numero non contrassegnato (i numeri contrassegnati sono numeri barrati o racchiusi in una cornice) e racchiudelo in una cornice: questo sarà il numero primo successivo;
5) ripetere i passaggi 3 e 4 finché non rimangono numeri non contrassegnati.

Puoi avere un'idea migliore del metodo per trovare i numeri primi con l'aiuto dell'animazione "Sieve of Eratostene" (180279) pubblicata nella Collezione unificata di risorse educative digitali.

La sequenza di azioni considerata è un algoritmo, poiché soddisfa le seguenti proprietà:

discrezione- il processo di ricerca dei numeri primi è suddiviso in fasi;
intelligibilità- ogni comando è comprensibile a uno studente di terza media che esegue questo algoritmo;
certezza- ogni comando è interpretato ed eseguito dall'esecutore in modo inequivocabile; ci sono istruzioni sull'ordine di esecuzione dei comandi;
prestazione- dopo un certo numero di passaggi, il risultato è raggiunto;
carattere di massa- la sequenza degli atti è applicabile per qualsiasi n.

Le proprietà considerate dell'algoritmo ci consentono di dare una definizione più precisa dell'algoritmo.

Un algoritmo è una descrizione di una sequenza di azioni destinate a un esecutore specifico, che porta dai dati iniziali al risultato desiderato, che ha le proprietà di discrezione, comprensibilità, certezza, efficacia e carattere di massa.

2.1.4. Capacità di automatizzare le attività umane

Lo sviluppo di un algoritmo è, di regola, un'attività che richiede tempo che richiede una profonda conoscenza, ingegnosità e molto tempo da parte di una persona.

Risolvere il problema utilizzando un algoritmo già pronto richiede all'esecutore solo di seguire rigorosamente le istruzioni fornite.

Esempio 9 Da una pila contenente un numero qualsiasi, superiore a tre, di qualsiasi oggetto, due giocatori a turno prendono uno o due oggetti ciascuno. Il vincitore è colui che può raccogliere tutti gli oggetti rimanenti con la sua prossima mossa.

Consideriamo un algoritmo, a seguito del quale il primo giocatore si assicurerà sicuramente una vittoria.

1. Se il numero di oggetti nella pila è un multiplo di 3, lascia il posto all'avversario, altrimenti inizia il gioco prendendo 1 o 2 oggetti in modo che il numero di oggetti rimasti sia un multiplo di 3.
2. Con la tua prossima mossa, somma ogni volta il numero di oggetti presi dall'avversario a 3 (il numero di oggetti rimanenti deve essere un multiplo di 3).

L'esecutore potrebbe non approfondire il significato di ciò che sta facendo, e non il motivo per cui agisce in questo modo e non altrimenti, cioè può agire formalmente. La capacità dell'esecutore di agire formalmente offre la possibilità di automatizzare le attività umane. Per questo:

1) il processo di risoluzione del problema è rappresentato come una sequenza di semplici operazioni;
2) viene creata una macchina (un dispositivo automatico) in grado di eseguire queste operazioni nella sequenza specificata nell'algoritmo;
3) una persona viene esonerata dalle attività di routine, l'esecuzione dell'algoritmo è affidata a un dispositivo automatico.

LA COSA PIÙ IMPORTANTE

Esecutore- qualche oggetto (umano, animale, dispositivo tecnico) in grado di eseguire un determinato insieme di comandi.

Un esecutore formale esegue sempre lo stesso comando allo stesso modo. Per ogni esecutore testamentario formale è possibile specificare: gamma di compiti da risolvere, ambiente, sistema di comando e modalità di funzionamento.

Algoritmo- una descrizione della sequenza di azioni destinate a uno specifico esecutore, che conduce dai dati iniziali al risultato richiesto, che ha le proprietà di discrezione, comprensibilità, certezza, efficacia e carattere di massa.

La capacità dell'interprete di recitare formalmente offre la possibilità di automatizzare le attività umane.

Domande e compiti

1. Familiarizzare con i materiali di presentazione del paragrafo contenuto nel supplemento elettronico al libro di testo. La presentazione integra le informazioni contenute nel testo del paragrafo? Quali diapositive vorresti aggiungere alla tua presentazione?

2. Cosa si chiama algoritmo?

3. Raccogli i sinonimi della parola "prescrizione".

4. Fornisci esempi di algoritmi che studi a scuola.

5. Chi può essere l'esecutore dell'algoritmo?

6. Fornisci un esempio di esecutore formale. Fai un esempio quando una persona si comporta come un artista formale.

7. Cosa determina la gamma di compiti che devono essere risolti dall'esecutore "computer"?

8. Considera un elaboratore di testi sul tuo computer come un esecutore. Descrivi la gamma di attività risolte da questo esecutore e dal suo ambiente.

9. Che cos'è un team, un sistema di comandi per un esecutore?

10. Quali comandi deve eseguire il robot per le seguenti funzioni:

a) un cassiere in un negozio;
b) bidello;
c) una guardia giurata?

11. Elenca le proprietà principali dell'algoritmo.

12. A cosa può portare l'assenza di qualsiasi proprietà di un algoritmo? Dare esempi.

13. Qual è l'importanza della possibilità di esecuzione formale dell'algoritmo?

14. La sequenza dei numeri è costruita secondo il seguente algoritmo: i primi due numeri della sequenza sono presi uguali a 1; ogni numero successivo nella sequenza è considerato uguale alla somma dei due numeri precedenti. Annota i primi 10 termini di questa sequenza. Scopri come si chiama questa sequenza.

15. Alcuni algoritmi ottengono una nuova stringa da una stringa di caratteri come segue. Innanzitutto, viene scritta la catena di caratteri originale, dopo di essa viene scritta la catena di caratteri originale in ordine inverso, quindi viene scritta la lettera che segue nell'alfabeto russo la lettera che era all'ultimo posto nella catena originale. Se la lettera "I" è all'ultimo posto nella catena iniziale, la lettera "A" viene scritta come lettera successiva. La catena risultante è il risultato dell'algoritmo. Ad esempio, se la stringa di caratteri originale era "HOME", il risultato dell'algoritmo sarà la stringa "DOMMODN". Data una stringa di caratteri "KOM". Quante lettere "O" ci saranno nella catena di caratteri che risulterà se applichiamo l'algoritmo a questa catena e quindi applichiamo nuovamente l'algoritmo al risultato del suo lavoro?

16. Trova su Internet un'animazione dei passaggi dell'algoritmo di Eratostene. Usa l'algoritmo di Eratostene per trovare tutti i numeri primi minori di 50.

17. Quale sarà il risultato dell'esecuzione dell'algoritmo da parte della Tartaruga (vedi esempio 5)?

18. Scrivere un algoritmo per l'executor Calcolatrice (vedi esempio 6), contenente non più di 5 comandi:

a) ricevere dal numero 3 il numero 16;
b) ottenere dal numero 1 il numero 25.

19. Sistema di comando dell'esecutore Il costruttore è composto da due comandi, a cui sono assegnati dei numeri:

1 - assegnare 2
2 - dividi per 2

Secondo il primo, 2 è assegnato al numero a destra, secondo il secondo, il numero è diviso per 2. Come verrà convertito il numero 8 se l'esecutore esegue l'algoritmo 22212? Crea un algoritmo nel sistema di comando di questo esecutore, in base al quale il numero 1 verrà convertito nel numero 16 (non dovrebbero esserci più di 5 comandi nell'algoritmo).

20. In quale cella dovrebbe trovarsi il Robot esecutore (esempio 7) per ritornarvi dopo l'esecuzione dell'algoritmo 3241?

Software gratis:

Sistema KuMir - Un insieme di mondi educativi (scarica l'archivio del programma dal sito) o visita la pagina KuMir ((http://www.niisi.ru/kumir/)

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 esatta e comprensibile all'esecutore per eseguire una sequenza finale di comandi che portano dai dati iniziali al risultato iniziale.

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

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

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

Per esempio, il Robot esecutore può eseguire comandi avanti, indietro, sinistra, destra, sopra. Si muove attraverso un campo cellulare delimitato da un muro e pareti di contenimento. Il robot non può passare attraverso il muro.

Proprietà dell'algoritmo:

1.Efficienza (finitezza)– la possibilità di ottenere un 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.carattere di massa– la possibilità di applicare l'algoritmo a un numero elevato di dati iniziali differenti. (Ad esempio, puoi aggiungere 2 numeri qualsiasi, conoscendo l'algoritmo di addizione.)

3.determinismo(determinatezza, accuratezza) - ogni squadra deve determinare in modo univoco l'azione dell'esecutore.

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

5.discrezione– suddividere l'algoritmo in comandi separati.

Metodi di scrittura dell'algoritmo:

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

2) Grafico - nel linguaggio dei diagrammi a blocchi, utilizzando forme geometriche (ovale, rettangolo, parallelogramma, rombo).

3) In un linguaggio algoritmico - un linguaggio per la scrittura di algoritmi per l'insegnamento della programmazione. Le squadre sono scritte 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; immagine su 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.

Costruzioni algoritmiche di base sono una sequenza lineare di passaggi (o successivi), un ramo e un ciclo.

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 del diagramma di flusso:

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 alimentazione sull'unità di sistema.
4. Attendi il caricamento del sistema operativo e la visualizzazione del desktop.
5. Andare al lavoro.

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

in una 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. In una condizione, due numeri, due stringhe, due variabili o espressioni di stringa vengono confrontati tra loro utilizzando gli operatori di confronto (>,<, =, >=, <=).

Notazione algoritmica: IfCondition Then Series 1 (If Condizione true, quindi viene eseguito Serie 1, Se Condizione falso, non si fa nulla). Esempio: se oggi è domenica, non devi andare a scuola. Modulo di ramificazione completo

Nelle strutture algoritmiche ciclo include una serie di comandi che vengono eseguiti ripetutamente. Questa sequenza di comandi viene chiamata corpo ad anello.

Le strutture algoritmiche cicliche sono di due tipi:

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

Passante con contatore- si usa quando si sa in anticipo quante ripetizioni del loop body devono essere eseguite.

Si prega di mettere in pausa AdBlock su questo sito.

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

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

Fig.1 Screenshot del campo da gioco su code.org

Spero che tutto abbia funzionato per te. Ora, usando questo esempio, descriveremo alcuni concetti di base:

• esecutore;
• sistema di comando dell'esecutore;
• 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 un comando è chiamato esecutore. In questo giocattolo, ovviamente, l'esecutore è un uccello. Viene chiamato un insieme di comandi che un esecutore comprende ed è in grado di eseguire sistema di comando dell'esecutore.

La sequenza di comandi che un esecutore deve eseguire per risolvere un problema è chiamata algoritmo.

È necessario concentrarsi su più punti.

Un esecutore può eseguire solo quei comandi che sono inclusi nel suo sistema di comandi.

Ciò significa, ad esempio, che non puoi scrivere a un artista di uccelli: "Vai dal maiale!". Puoi scriverlo in modo più preciso, ma non accadrà nulla, perché. l'esecutore di tali comandi non lo sa.

Puoi scrivere i comandi disponibili nell'ordine che ritieni corretto. Il tuo compito come programmatore è dividere una grande attività complessa in piccoli passaggi separati, ognuno dei quali sarà comprensibile per l'esecutore. Il principio del "divide et impera" funziona di nuovo.

L'esecutore esegue esattamente ciò che l'algoritmo gli prescrive.

L'uccello interprete è molto fiducioso. Non mette in discussione ciò che scrivi nel programma. Se, ad esempio, ti dimentichi di girare l'uccello, si schianterà contro il muro. Quindi devi occuparti di tutto da solo.

I tuoi programmi futuri spesso non funzioneranno nel modo previsto. Gli errori capitano a tutti. È importante capire qui che questo non è un idiota del computer, ma hai commesso un errore nell'algoritmo. Non essere come i cattivi programmatori che incolpano sempre il programma di tutto.

Passiamo ora da un esempio visivo alle realtà informatiche. Scriviamo programmi per il computer, il che significa che il computer nel nostro caso è l'esecutore. Il sistema di comando è costituito dalle funzioni e dai costrutti standard del linguaggio C.

Qual è l'obiettivo principale del tuo apprendimento delle basi della programmazione? Padroneggia l'abilità del pensiero algoritmico. Cioè, imparare a scrivere la soluzione di vari problemi sotto forma di un algoritmo per un esecutore specifico (nel nostro caso, un computer).

Quindi ricapitoliamo:

programma per computer- un algoritmo per la risoluzione di un problema, scritto in un linguaggio di programmazione.

Un algoritmo è una descrizione precisa dell'ordine delle azioni che un esecutore deve eseguire per risolvere un problema.

Un esecutore è una persona o un dispositivo in grado di comprendere ed eseguire un determinato insieme di comandi.

Il concetto di algoritmo. Implementatori di algoritmi. Proprietà degli algoritmi

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

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

Un algoritmo è una descrizione esatta della sequenza di azioni volte a risolvere un determinato problema destinato a uno specifico esecutore.

Contraente Un algoritmo può essere una persona (ricette di cucina, istruzioni varie, algoritmi per calcoli matematici) o un dispositivo tecnico. Varie macchine (computer, robot industriali, moderni elettrodomestici) sono esecutori testamentari formali algoritmi. Non è necessario un esecutore formale per comprendere l'essenza del problema da risolvere, ma è richiesta l'esatta esecuzione di una 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 scrittolinguaggio di programmazione .

Per creare un algoritmo (programma), devi sapere:

un set completo di dati iniziali dell'attività (lo stato iniziale dell'oggetto);

lo scopo di creare l'algoritmo (lo stato finale dell'oggetto);

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

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

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

unicità (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).

Anche la maggior parte degli algoritmi ha la proprietà carattere di massa (usando lo stesso algoritmo, puoi risolvere molti problemi dello stesso tipo).

Modi per descrivere gli algoritmi

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

Designazione	Descrizione	Appunti
	Inizio e fine dell'algoritmo
	Input e output di dati.	L'output dei dati viene talvolta definito in modo diverso:
	Azione	Negli algoritmi di calcolo, questo è il compito
	Forchetta	Forcella: un componente necessario per l'implementazione di rami e anelli
	Avvio di un ciclo con un parametro
	Processo di esempio	In programmazione, procedure o sottoprogrammi
	Transizioni tra blocchi

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

Questo modo di descrivere l'algoritmo è il più chiaro e comprensibile per una persona. Pertanto, gli algoritmi degli esecutori formali vengono solitamente sviluppati prima sotto forma di diagramma a blocchi e solo successivamente viene creato un programma su uno deilinguaggi di programmazione .

Strutture algoritmiche tipiche

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

Struttura lineare (seguente)

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

ramificazione

IN completa ramificazione 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 solo il secondo ramo.

Il secondo ramo potrebbe essere vuoto. Tale struttura è chiamata ramificazione o attraversamento incompleto.

Da più rami, puoi costruire la struttura " scelta” (ramificazione multipla), che sceglierà non tra due, ma tra più opzioni per l'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 di esse funzionerà, la prima dall'alto.

Ciclo (ripetizione)

Ciclopermette di organizzare la ripetizione ripetuta della stessa sequenza di comandi- è chiamato il corpo del ciclo. In vari tipi di algoritmi ciclici, il numero di ripetizioni può dipendere dal valore dell'espressione logica (condizione) o può essere rigidamente specificato nella struttura stessa. Ci sono cicli: prima», « fino», cicli con un contatore. Nei cicli "fino al" e "while", un'espressione logica (condizione) può precedere il corpo del ciclo ( ciclo con presupposto) o terminare il ciclo ( ciclo con postcondizione).

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

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

Cicli con un contatore(con parametro)– ripetizione del corpo del loop un determinato numero di volte:

Algoritmo ausiliario (subroutine, procedura)

Algoritmo di aiuto è un modulo a cui è possibile accedere ripetutamente dall'algoritmo principale. L'uso di algoritmi ausiliari 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 sequenziale del problema("top-down") è che l'attività complessa originale è suddivisa in sottoattività. Ciascuna delle attività secondarie viene considerata e risolta separatamente. Se una delle attività secondarie è complessa, viene anche suddivisa in attività secondarie. Il processo continua fino a quando le attività secondarie non vengono ridotte a quelle elementari. Le soluzioni dei singoli sottocompiti vengono quindi assemblate in un unico algoritmo per risolvere il problema originale. Il metodo è ampiamente utilizzato, in quanto consente a più programmatori di sviluppare un algoritmo comune contemporaneamente, risolvendo sottoattività locali. Questa è una condizione necessaria 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 compiti tipici. Quando risolve un problema complesso, un programmatore può utilizzare i moduli sviluppati come algoritmi ausiliari (procedure). In molti sistemi di programmazione Esistono già insiemi di moduli simili, il che semplifica e velocizza notevolmente la creazione di un algoritmo complesso.

Algoritmi e processi di controllo

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

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

Dal punto di vista informatico le azioni di controllo possono essere considerate come informazioni di controllo. Le informazioni possono essere trasmesse sotto forma di comandi. Viene chiamata una sequenza di comandi per controllare un oggetto, che porta a un obiettivo predeterminato algoritmo di controllo. Pertanto, l'oggetto di controllo può essere chiamato l'esecutore dell'algoritmo di controllo. Nell'esempio considerato, l'oggetto di controllo funziona "senza guardare" ciò che sta accadendo con l'oggetto di controllo ( controllo ad anello aperto aprire. Un altro schema di controllo può tenere conto delle informazioni sui processi che si verificano nell'oggetto di controllo:

In questo caso, l'algoritmo di controllo deve essere sufficientemente flessibile da analizzare queste informazioni e decidere le sue ulteriori azioni in base allo stato dell'oggetto di controllo ( controllo del feedback). Questo schema di controllo è chiamato Chiuso.

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

Inizio argomento

MBOU "Scuola secondaria Glinnovskaya"

distretto di Novooskolsky

regione di Belgorod

Piano - riepilogo della lezione

(grado 9)

“Algoritmi, concetti di un algoritmo, proprietà di un algoritmo. Esecutori di algoritmi»

Preparato da:

Impara l'informatica

Tarasova NG

2011

Argomento: Il concetto di algoritmi, proprietà dell'algoritmo. Esecutori di algoritmi, sistema di comando dell'esecutore. Modalità di scrittura degli algoritmi. Esecuzione formale di algoritmi.

tipo di lezione: introduzione a nuovo materiale.

Obiettivi:

1. Contribuire allo sviluppo del pensiero algoritmico;
2. Dare il concetto di algoritmo, parlare delle sue proprietà, fornire una classificazione degli algoritmi;
3. Conoscere la forma di scrittura degli algoritmi: un diagramma di flusso.

Attrezzatura : proiettore, presentazione.

Durante le lezioni

1 org. Momento

Saluto, atterraggio, appello.

2 Aggiornamento del materiale di riferimento

Ragazzi, ditemi per favore, come capite la parola algoritmo? Dove incontriamo questo concetto?

3 Presentazione del materiale

L'origine del termine "algoritmo" è legata alla matematica. La storia della sua origine è la seguente. Nel IX secolo, lo scienziato al(al)-Khorezmi visse a Baghdad (nome completo - Mohammed bin Musa al-Khorezmi, cioè Maometto figlio di Musa di Khorezm), matematico, astronomo, geografo. In una sua opera descrisse il sistema dei numeri decimali e formulò per la prima volta le regole per eseguire operazioni aritmetiche su interi e frazioni ordinarie. L'originale arabo di questo libro andò perso, ma rimase la traduzione latina del XII secolo, secondo la quale l'Europa occidentale conobbe il sistema dei numeri decimali e le regole per eseguire operazioni aritmetiche.

Al-Khwarizmi ha cercato di garantire che le regole da lui formulate fossero comprensibili. Era difficile raggiungere questo obiettivo nel IX secolo, quando i simboli matematici (segni di operazioni, parentesi, designazioni di lettere, ecc.) non erano ancora stati sviluppati. Tuttavia, riesce a sviluppare uno stile chiaro di rigorosa prescrizione verbale che non dà al lettore l'opportunità di eludere la prescrizione o saltare qualsiasi azione.

Le regole nei libri di cm-Khorezmi nella traduzione latina iniziavano con le parole "Ha detto Algorizmi". In altre traduzioni latine, l'autore veniva chiamato Algoritmus. Nel corso del tempo, è stato dimenticato che l'algoritmo (Algoritmo) è l'autore delle regole e queste regole hanno iniziato a essere chiamate algoritmi. Per molti secoli sono stati sviluppati algoritmi per risolvere sempre più nuove classi di problemi, ma il concetto stesso di algoritmo non aveva una definizione matematica esatta.

Attualmente, il concetto di algoritmo è stato perfezionato e realizzato nel 20° secolo nell'ambito di una scienza chiamata teoria degli algoritmi.

Algoritmo - istruzioni precise e comprensibili all'esecutore per eseguire una sequenza di azioni volte a risolvere il compito.

Algoritmo - azioni sequenziali chiaramente organizzate che portano a un certo risultato.

Un esecutore di un algoritmo è astratto o realeun sistema in grado di compiere un'azione prescritta da un algoritmo (tecnico, biologico o biotecnico).

Esecutore tecnico- bancomat;

Biologico - una persona, un organismo vivente;

Biotecnologia - intelligenza artificiale.

Proprietà degli algoritmi

discrezione (separazione, discontinuità) - l'algoritmo deve essere scritto come una sequenza di passaggi o fasi.

Chiarezza L'esecutore dell'algoritmo deve sapere come eseguire questo algoritmo.

Certezza (determinismo) ogni regola dell'algoritmo deve essere chiara, non ambigua e non lasciare spazio all'arbitrarietà.

A causa di questa proprietà, l'esecuzione dell'algoritmo è di natura meccanica e non richiede istruzioni aggiuntive.

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

carattere di massa l'algoritmo è sviluppato in forma generale in modo da poter essere applicato a risolvere problemi dello stesso tipo. In questo caso, i dati iniziali vengono selezionati da alcune aree, che sono chiamate scope degli algoritmi.

Modi per scrivere algoritmi

Se le proprietà di certezza e discrezione sono conservate con un certo grado di accuratezza, ad es. il programma può riorganizzare i passaggi o contiene passaggi desiderabili, ma non obbligatori, quindi questo non è un algoritmo, maprescrizione algoritmica.

Ogni algoritmo è progettato per un certo esecutore. Può essere una persona, un robot, un computer, ecc. ogni esecutore ha il proprio sistema di comando. Quando si compila un algoritmo, è necessario prendere in considerazione per quale esecutore è stato progettato. L'esecutore può eseguire l'algoritmo senza approfondire il significato di ciò che sta facendo, perché lo sta facendo, e tuttavia otterrà il risultato desiderato. In questi casi, l'algoritmo si dice eseguito formalmente.

Forme di scrittura di algoritmi:

Verbale è una descrizione delle fasi successive del trattamento dei dati. L'algoritmo è una presentazione arbitraria in linguaggio naturale

Grafico - una sequenza di blocchi interconnessi, ognuno dei quali corrisponde all'esecuzione di una o più azioni.

Tale rappresentazione grafica è chiamata diagramma a blocchi - grafico diretto che indica l'ordine di esecuzione dei comandi dell'algoritmo.

Forme grafiche di algoritmi di scrittura:

Strutture algoritmiche di base

Successivi (algoritmo lineare) Loop

ramificazione

a seguire – i comandi vengono eseguiti uno dopo l'altro nell'ordine in cui sono scritti nell'algoritmo.((Esempio. L'algoritmo per aprire la porta dell'appartamento: prendi la chiave, inseriscilabuco della serratura, girare il numero di volte richiesto, prendere la chiave, aprire la porta. chiudi la porta)

ramificazione - i dati influiscono sull'andamento dell'algoritmo, ad es. a seconda della condizionevengono eseguite determinate azioni dell'algoritmo.(Esempio, Algoritmo per "entrare" nel tuo appartamento: chiama l'appartamento; se c'è qualcuno in casa, aspetta che la porta si apra eentra nell'appartamento, se non c'è nessuno in casa prendi la chiave; ...)

Ciclo (ripetizione)- nel processo di esecuzione dell'algoritmo, un certoset di comandi. (Esempio.(Lavare 10 piatti: prendi un piatto, lava, asciuga, prendipiatto, lavare, asciugare, ecc. finché i piatti non si esauriscono.)

4 Applicazione delle conoscenze acquisite

Un compito eseguire i comandi dell'algoritmo con a=1, b=2, c=3