Diapositiva 1
Diapositiva 2
Che cos'è un modello algoritmico? Perché un algoritmo è chiamato modello e cosa modella? Un algoritmo è un'istruzione chiara e precisa a un esecutore specifico per eseguire la sequenza finale di azioni che portano a un obiettivo prefissato. L'obiettivo viene raggiunto attraverso l'attività di alcuni performer.
Diapositiva 3
Fasi dell'attività: Determinazione dell'obiettivo; Programmazione del lavoro dell'appaltatore; Il lavoro dell'esecutore; Ottenere il risultato. Dove si inserisce l'algoritmo qui? Un algoritmo è un piano dettagliato del lavoro dell'esecutore; è una descrizione della sequenza di azioni che l'esecutore deve eseguire.
Diapositiva 4
L'algoritmo è un modello informativo dell'attività dell'esecutore. Questo modello sarà chiamato algoritmico. Riso. Fasi di movimento dall'obiettivo al risultato. Determinazione dell'obiettivo Costruzione di un piano-algoritmo Lavoro dell'esecutore Ottenere il risultato Modello del lavoro dell'esecutore
Diapositiva 5
Sistema di comandi dell'esecutore Per costruire un vero e proprio piano-algoritmo, è necessario conoscere le capacità dell'esecutore. Queste capacità sono determinate dallo SKI. Quando si compone un algoritmo, non si deve andare oltre il framework SQI. È più facile costruire un algoritmo per un automa controllato da software che per un essere umano. Per un automa, SKI è un insieme rigorosamente definito di comandi in un linguaggio formalizzato per descrivere algoritmi. Tali linguaggi sono chiamati linguaggi di programmazione e l'algoritmo è chiamato programma. Lo SCI di una persona non può essere descritto completamente.
Diapositiva 6
Un esempio di modello algoritmico. Compito: indovinare un numero intero da un dato intervallo usando il metodo della mezza divisione. Il primo giocatore indovina un numero intero da un determinato intervallo di numeri, ad esempio da 1 a 100. Il secondo deve indovinare il numero utilizzando il minor numero di domande.
Diapositiva 7
Algoritmo per un esecutore umano. Algoritmo Indovinare il numero Dato: l'intervallo di numeri da A a B È necessario: indovinare il numero X concepito dal giocatore utilizzando l'algoritmo di mezza divisione Inizio 1. Poni la domanda: X è inferiore al valore medio tra A e B? 2. Se la risposta è "sì", prendi l'intera parte della media come valore di B. 3. Se la risposta è "no", prendi l'intero più vicino maggiore della media come valore di A. 4. Se i valori di A e B sono uguali, il loro valore totale è il numero richiesto X. 5. Se i valori di A e B non sono uguali, torna all'esecuzione del paragrafo 1. Fine
Diapositiva 8
Diapositiva 9
Algoritmo per un esecutore di computer. Linguaggio algoritmico Alg Mezza divisione Intero A, B, X Inizio Input A, B, X Mentre A B, ripeti Hc Se X≤ (A + B) / 2 Allora B: = CAL ((A + B) / 2) Altrimenti A: = SCOPO ((A + B) / 2) +1 Kts Conclusione A Fine
Diapositiva 10
Programmazione strutturata La struttura dell'algoritmo costruito è un ciclo con ramificazione annidata. Qualsiasi algoritmo può essere costruito da una combinazione di tre strutture algoritmiche di base: sequenza, ramo e ciclo. Questa affermazione è alla base di una tecnica chiamata programmazione strutturata. Se l'algoritmo è strutturato, allora è facile passare dalla descrizione dell'algoritmo al programma.
Diapositiva 11
La traccia dell'algoritmo è un modello del funzionamento del processore. Per testare la correttezza di un algoritmo, non è affatto necessario tradurlo in un linguaggio di programmazione. Una persona può anche testare l'algoritmo, tracciando. Quando si esegue la traccia manuale, una persona simula il lavoro del processore, eseguendo ciascun comando e inserendo i risultati dell'esecuzione del comando in una tabella di traccia. Scegliamo un intervallo di numeri indovinabili da 1 a 8. Lascia che il giocatore concepisca il numero 3.
Diapositiva 12
Numero passo Comando algoritmo Variabili Azioni eseguite X A B 1 Ingresso A, B, X 3 1 8 2 A ≠ B 1 ≠ 8, si 3 X ≤ (A + B) / 2 3 ≤ 4.5, si 4 B: = TARGET ((A + B) / 2) B: = 4 5 A ≠ B 1 ≠ 4, si 6 X ≤ (A + B) / 2 3 ≤ 2.5 Numero passo Comando algoritmo Variabili Azioni eseguite XAB 1 Ingresso A, B, X 3 1 8 2 A B 1 ≠ 8, sì 3 X ≤ (A + B) / 2 3 ≤ 4.5, sì 4 B: = CEL ((A + B) / 2) 3 1 4 V: = 4 5 A ≠ B 1 ≠ 4, sì 6 X ≤ (A + B) / 2 3 ≤ 2,5, no
Che cos'è un modello algoritmico Un algoritmo è un'istruzione chiara e precisa a un esecutore specifico per eseguire una sequenza finale di azioni che portano a un obiettivo prefissato. Le fasi dell'attività dalla definizione dell'obiettivo (impostazione del compito) all'ottenimento del risultato sono le seguenti: 1) Definire l'obiettivo 2) Programmare il lavoro dell'esecutore 3) Il lavoro dell'esecutore 4) Ottenere il risultato L'algoritmo è un modello informativo dell'attività dell'esecutore. Questo modello sarà chiamato algoritmico.
Sistema di comandi dell'esecutore Per costruire un vero piano - un algoritmo che risulta fattibile, è necessario conoscere esattamente le capacità dell'esecutore. Queste capacità sono determinate dal sistema di comando dell'esecutore (SKI). Quando si compone un algoritmo, non si deve andare oltre il framework SQI. Questa è la proprietà dell'intelligibilità dell'algoritmo. Per un automa, SKI è un insieme finito rigorosamente definito di comandi inseriti dai progettisti. Pertanto, l'algoritmo è una descrizione esatta del suo funzionamento e l'automa esegue il lavoro, seguendo formalmente le istruzioni dell'algoritmo. Per controllare un automa o un computer, non è difficile trovare un linguaggio formalizzato per descrivere gli algoritmi. Tali linguaggi sono chiamati linguaggi di programmazione e un algoritmo presentato in un linguaggio di programmazione è chiamato programma.
Un esempio di modello algoritmico Il primo giocatore indovina un numero intero da un determinato intervallo di numeri, ad esempio da 1 a 100. Il secondo deve indovinare questo numero utilizzando il minor numero di domande. Algoritmo per indovinare il numero con il metodo della mezza divisione, incentrato sull'esecutore umano. Algoritmo Indovinare il numero Dato: l'intervallo di numeri va da A a B È necessario: indovinare il numero X, concepito dal giocatore, utilizzando l'algoritmo della mezza divisione Inizio 1) Poni la domanda: X è minore del valore medio tra A e B? 2) Se la risposta è "SI", prendi la parte intera della media come valore B. 3) Se la risposta è "NO", prendi come valore A l'intero più vicino alla media. 4) Se i valori di A e B sono uguali, il loro valore totale è il numero X desiderato. 5) Se i valori di A e B non sono uguali, torna al passaggio 1. Fine Questo algoritmo è focalizzato su un artista umano, non su un computer.
Algoritmo "Mezza divisione" Alg Mezza divisione Intero A, B, X Inizio Input A, B, X Mentre AB, ripeti Hc Se X (A + B) / 2 Quindi B: = Intero ((A + B) / 2) Altrimenti , A: = Int ((A + B) / 2) +1 KV Kts Uscita A Fine Inizio Fine Ingresso A, B, X Uscita A AB X (A + B) / 2 B: = INT ((A + B ) / 2) A: = SCOPO ((A + B) / 2) +1 no si no si
Diagramma di flusso Un diagramma di flusso è un grafico orientato che indica l'ordine in cui un executor esegue le istruzioni di un algoritmo. I blocchi - i vertici di questo grafico - designano i singoli comandi che vengono dati all'esecutore e gli archi indicano la sequenza delle transizioni da un comando all'altro. Nei rettangoli degli schemi a blocchi sono scritti i comandi - azioni, nei rombi - le condizioni che determinano la direzione dell'ulteriore esecuzione dei comandi; in parallelogrammi - comandi per l'input o l'output di informazioni; in ovali - l'inizio o la fine dell'esecuzione dell'algoritmo. Qui puoi parlare del percorso del grafico durante l'esecuzione dell'algoritmo. Qualsiasi percorso inizia dall'alto "Inizio" e termina con un'uscita verso l'alto "Fine". Internamente il percorso può essere diverso a seconda dei dati iniziali e dei risultati del controllo delle condizioni. Un diagramma a blocchi è una forma grafica, un linguaggio algoritmico sono due diverse forme di rappresentazione di un modello algoritmico.
Programmazione strutturata La struttura dell'algoritmo costruito è un ciclo con ramificazione annidata. Qualsiasi algoritmo può essere costruito da una combinazione di tre strutture algoritmiche di base: sequenza, ramo e ciclo. Questa affermazione è alla base di una tecnica chiamata programmazione strutturata. I moderni linguaggi di programmazione semplificano il passaggio da una descrizione di un algoritmo a un programma se l'algoritmo è strutturato. Pertanto, il modello più razionale dell'attività dell'esecutore è il modello algoritmico strutturale.
Tracciamento dell'algoritmo: un modello del funzionamento del processore Per verificare la correttezza di un algoritmo, non è affatto necessario tradurlo in un linguaggio di programmazione ed eseguire test su un computer. Una persona può anche testare l'algoritmo, tracciando. Quando si esegue la traccia manuale, una persona simula il lavoro del processore, eseguendo ogni comando dell'algoritmo e inserendo i risultati dell'esecuzione del comando in una tabella di traccia. È un modello di come funziona il processore durante l'esecuzione di un programma. Il programma viene eseguito per passi (prima colonna della tabella). La colonna Comando algoritmo visualizza il contenuto del registro di comando del processore. Dove viene posizionato il comando successivo. La colonna "Variabili" visualizza il contenuto delle celle di memoria del computer (o registri di memoria del processore) riservate ai valori delle variabili. La colonna "Azione eseguita" riflette le azioni eseguite dall'unità logica aritmetica del processore.
Argomento della lezione: "Algoritmo come modello di attività".
Scopo: spiegare un nuovo argomento in modo interessante e comprensibile.
Far conoscere agli studenti l'argomento: “Il concetto di algoritmo. Tipi di algoritmi e loro proprietà”;
Gli studenti dovrebbero conoscere il concetto di algoritmo, le proprietà degli algoritmi;
Gli studenti dovrebbero essere in grado di fornire esempi di algoritmi.
Durante le lezioni:
1. Momento organizzativo.
2. Imparare un nuovo argomento.
Iniziamo a ripetere il concetto di algoritmo guardando un esempio. Supponiamo che tu voglia ritagliare un modellino di auto dalla carta. Il risultato dipenderà in gran parte dalla tua abilità ed esperienza. Tuttavia, raggiungere il tuo obiettivo sarà molto più facile se prima delinei un piano d'azione, come il seguente:
1. Studiare l'immagine dell'auto sul modello esistente.
2. Disegna porte, carrozzeria su carta.
3. Ritaglia gli schizzi.
4. Prova a cucire insieme gli schizzi, correggi gli errori.
5. Incolla le parti del modello.
Seguendo il piano preparato, qualsiasi persona, anche senza capacità artistiche, ma con pazienza, otterrà sicuramente un buon risultato. Un tale piano con una descrizione dettagliata delle azioni necessarie per ottenere il risultato atteso è chiamato algoritmo.
Il concetto di algoritmo. ( Fornire ulteriori informazioni)
L'emergere degli algoritmi è associato alla nascita della matematica. Più di 1000 anni fa (nell'825), uno scienziato della città di Khorezm Abdullah (o Abu Jafar) Muhammad bin Musa al-Khorezmi creò un libro sulla matematica, in cui descriveva i metodi per eseguire operazioni aritmetiche su numeri a più cifre. La stessa parola "algoritmo" è apparsa in Europa dopo la traduzione in latino del libro di questo matematico dell'Asia centrale, in cui il suo nome era scritto come "Algoritmi".
Algoritmo- una descrizione della sequenza di azioni (piano), la cui rigorosa attuazione porta alla soluzione del compito in un numero finito di passaggi.
Algoritmizzazione- il processo di sviluppo di un algoritmo (piano d'azione) per risolvere un problema.
Esempi di algoritmi:
Qualsiasi dispositivo acquistato in un negozio viene fornito con le istruzioni per il suo utilizzo.
Ogni autista deve conoscere le regole della strada.
La produzione di massa di automobili è diventata possibile solo quando è stato inventato l'ordine di assemblaggio dell'auto sul nastro trasportatore.
Proprietà degli algoritmi.
Ci imbattiamo in algoritmi ad ogni passo. Alcuni li eseguiamo meccanicamente, senza nemmeno pensarci. Durante l'esecuzione di alcune azioni, non sospettiamo nemmeno di eseguire un determinato algoritmo.
Questi esempi non sono altro che un algoritmo. Nonostante la significativa differenza nell'essenza delle azioni di questi esempi, si può trovare molto in comune. Queste caratteristiche generali sono chiamate proprietà dell'algoritmo. Consideriamoli.
Discrezione(dal lat. discretus - diviso, discontinuo) - questa è una scomposizione dell'algoritmo in una serie di azioni complete separate (passaggi). Gli algoritmi di cui sopra hanno in comune la necessità di attenersi rigorosamente alla sequenza delle azioni. Proviamo a invertire la seconda e la terza azione nel primo esempio. Ovviamente puoi eseguire questo algoritmo, ma è improbabile che la porta si apra. E se scambiamo, supponiamo, la quinta e la seconda azione nel secondo esempio, l'algoritmo diventa irrealizzabile.
Determinismo(dal latino determinato - certezza, accuratezza) - qualsiasi azione dell'algoritmo deve essere rigorosamente e inequivocabilmente determinata in ciascun caso.
Ad esempio, se gli autobus di percorsi diversi si fermano, l'algoritmo deve indicare un numero di percorso specifico - 5. Inoltre, è necessario specificare il numero esatto di fermate che devono essere percorse, ad esempio tre.
arto- ogni azione separatamente e l'algoritmo nel suo insieme devono essere in grado di completare. Negli esempi forniti, ogni azione descritta è reale e può essere eseguita. Pertanto, l'algoritmo ha un limite, cioè è finito.
Personaggio di massa- lo stesso algoritmo può essere utilizzato con dati di input diversi.
Efficacia- non ci sono stati errori nell'algoritmo.
Tipi di algoritmi.
Esistono 4 tipi di algoritmi: lineare, ciclico, branching, ausiliario.
Lineare Algoritmo (sequenziale): una descrizione delle azioni che vengono eseguite una volta in un determinato ordine.
Gli algoritmi per aprire le porte, fare il tè, fare un panino sono lineari. Un algoritmo lineare viene utilizzato per valutare un'espressione aritmetica se utilizza solo addizioni e sottrazioni.
Algoritmo ciclico- una descrizione delle azioni che devono essere ripetute un numero specificato di volte o fino a quando non viene soddisfatta una condizione specifica. L'elenco delle azioni ripetitive è chiamato corpo del ciclo.
Molti processi nel mondo circostante si basano sulla ripetizione ripetuta della stessa sequenza di azioni. Primavera, estate, autunno e inverno arrivano ogni anno. La vita delle piante segue gli stessi cicli durante tutto l'anno. Contando il numero di giri completi della lancetta dei minuti o delle ore, una persona misura il tempo.
Condizione- un'espressione che sta tra la parola "se" e la parola "allora" e assume il significato di "vero" o "falso".
Algoritmo di fork- un algoritmo in cui, a seconda della condizione, viene eseguita l'una o l'altra sequenza di azioni.
Esempi di algoritmi di ramificazione: se piove, è necessario aprire l'ombrello; se ti fa male la gola, la passeggiata dovrebbe essere annullata; se un biglietto per il cinema non costa più di dieci rubli, allora acquista un biglietto e prendi posto in sala, altrimenti (se il prezzo del biglietto è superiore a 10 rubli) torna a casa.
Nel caso generale, lo schema dell'algoritmo di ramificazione sarà simile al seguente: "se la condizione, quindi ..., altrimenti ...". Questa rappresentazione dell'algoritmo è chiamata la forma completa.
Forma incompleta, in cui vengono saltate le azioni: "se condizione, quindi ...".
Algoritmo di supporto- un algoritmo che può essere utilizzato in altri algoritmi specificandone solo il nome.
Compiti a casa. § sedici,
1. Trova i tuoi esempi per ogni tipo di algoritmo.
2. Crea un algoritmo per attraversare la strada con e senza semaforo.
Riassunto della lezione.
Bambini, che cosa avete imparato oggi?
Oggi abbiamo imparato cos'è un algoritmo, abbiamo imparato i tipi e le proprietà degli algoritmi
Che cos'è un modello algoritmico? Perché un algoritmo è chiamato modello e cosa modella? n Un algoritmo è un'istruzione chiara e precisa a un esecutore specifico per eseguire la sequenza finale di azioni che portano a un obiettivo prefissato. Cioè, l'obiettivo viene raggiunto attraverso l'attività di un determinato artista.
Fasi dell'attività: n n Definizione dello scopo; Programmazione del lavoro dell'appaltatore; Il lavoro dell'esecutore; Ottenere il risultato. Dove si inserisce l'algoritmo qui? Un algoritmo è un piano dettagliato del lavoro dell'esecutore; è una descrizione della sequenza di azioni che l'esecutore deve eseguire.
Di conseguenza, l'algoritmo è un modello informativo dell'attività dell'esecutore. Questo modello sarà chiamato algoritmico. Riso. Fasi di movimento dall'obiettivo al risultato. Determinazione dell'obiettivo Costruzione del piano dell'algoritmo Modello del lavoro del performer Lavoro del performer Ottenere il risultato
Sistema di comandi dell'esecutore Per costruire un vero e proprio piano-algoritmo, è necessario conoscere le capacità dell'esecutore. Queste capacità sono determinate dallo SKI. Quando si compone un algoritmo, non si deve andare oltre il framework SQI. È più facile costruire un algoritmo per un automa controllato da software che per un essere umano. Per un automa, SKI è un insieme rigorosamente definito di comandi in un linguaggio formalizzato per descrivere algoritmi. Tali linguaggi sono chiamati linguaggi di programmazione e l'algoritmo è chiamato programma. Lo SCI di una persona non può essere descritto completamente.
Un esempio di modello algoritmico. Compito: indovinare un numero intero da un dato intervallo usando il metodo della mezza divisione. Il primo giocatore indovina un numero intero da un determinato intervallo di numeri, ad esempio da 1 a 100. Il secondo deve indovinare il numero utilizzando il minor numero di domande.
Algoritmo per un esecutore umano. Algoritmo Indovinare il numero Dato: l'intervallo di numeri da A a B È necessario: indovinare il numero X concepito dal giocatore utilizzando l'algoritmo di mezza divisione Inizio 1. Poni la domanda: X è inferiore al valore medio tra A e B? 2. Se la risposta è "sì", prendi l'intera parte della media come valore di B. 3. Se la risposta è "no", prendi come valore A l'intero più vicino maggiore della media. 4. Se i valori di A e B sono uguali, il loro valore totale è il numero X desiderato. 5. Se i valori di A e B non sono uguali, torna all'esecuzione del paragrafo 1. Fine
Algoritmo per un esecutore di computer. Inizio schema a blocchi Entrata A, B, X no A ≠ B si no X≤ (A + B) / 2 B = CEL ((A + B) / 2) A = CEL ((A + B) / 2) + 1 Conclusione Una Fine
Algoritmo per un esecutore di computer. Linguaggio algoritmico Alg Mezza divisione Intero A, B, X Inizio Input A, B, X Mentre A B, ripeti Hc Se X≤ (A + B) / 2 Allora B: = CAL ((A + B) / 2) Altrimenti A: = SCOPO ((A + B) / 2) +1 Kts Conclusione A Fine
Programmazione strutturata La struttura dell'algoritmo costruito è un ciclo con ramificazione annidata. Qualsiasi algoritmo può essere costruito da una combinazione di tre strutture algoritmiche di base: sequenza, ramo e ciclo. Questa affermazione è alla base di una tecnica chiamata programmazione strutturata. Se l'algoritmo è strutturato, allora è facile passare dalla descrizione dell'algoritmo al programma.
La traccia dell'algoritmo è un modello del funzionamento del processore. Per testare la correttezza di un algoritmo, non è affatto necessario tradurlo in un linguaggio di programmazione. Una persona può anche testare l'algoritmo, tracciando. Quando si esegue la traccia manuale, una persona simula il lavoro del processore, eseguendo ciascun comando e inserendo i risultati dell'esecuzione del comando in una tabella di traccia. Scegliamo un intervallo di numeri indovinabili da 1 a 8. Lascia che il giocatore concepisca il numero 3.
Numero passo Comando algoritmo Variabili X A 3 1 Azioni eseguite B 1 Ingresso A, B, X 2 A ≠ B 1 ≠ 8, si 3 X ≤ (A + B) / 2 3 ≤ 4, 5, si 4 B: = SCOPO ( (A + B) / 2) 5 A B 1 ≠ 4, sì 6 X ≤ (A + B) / 2 3 ≤ 2, 5, no 3 1 8 4 B: = 4
7 A: = SCOPO ((A + B) / 2 + 1) 3 8 A ≠ B 3 ≠ 4, sì 9 X ≤ (A + B) / 2 3 ≤ 3, 5, sì 10 B: = SCOPO (( A + B) / 2) 11 A ≠ B 3 ≠ 3, no 12 Conclusione A Risposta: 3 3 4 3 A: = 3 B: = 3
La traccia dell'algoritmo è un modello del funzionamento del processore. n n Il programma viene eseguito per passi (prima colonna della tabella). La colonna Comando algoritmo visualizza il contenuto del registro dei comandi del processore, dove viene posizionato il comando successivo. La colonna "Variabili" mostra il contenuto delle celle di memoria allocate per i valori delle variabili. La colonna "Azione eseguita" riflette le azioni eseguite dall'unità logica aritmetica del processore.
Conclusione: n Pertanto, l'algoritmo insieme alla tabella di traccia simula completamente il processo di elaborazione delle informazioni nel computer.
Sistema di concetti di base Algoritmo - modello di attività L'oggetto della modellazione - attività intenzionale dell'esecutore. Esecutore umano Esecutore automatico (compreso un computer) Moduli di presentazione dell'algoritmo SKI non formalizzati Diagramma a blocchi Linguaggio algoritmico didattico Linguaggio di programmazione Il tracciamento dell'algoritmo è un'esecuzione passo passo di un algoritmo con una versione di prova dei dati iniziali. "Tracciamento manuale" - compilazione della tabella di traccia. La tabella di traccia è un modello del funzionamento del processore durante l'esecuzione dell'algoritmo.
Compiti § 16 leggi, rispondi alle domande 3, 4, 5, 8, 11 (qualsiasi 3 domande poste)
Presenta come diagramma a blocchi In ambiente Word Presenta questo algoritmo come diagramma a blocchi utilizzando l'autoshape alg start intero a, ba: = 2 b: = 0 nts mentre a 10 a: = a + 2 b: = b + 3 * a kc pin b con
