Esecutori di algoritmi. Esecuzione formale dell'algoritmo. Il computer come esecutore formale di algoritmi (programmi).

Tipo di lezione: combinato.

Obiettivi della lezione:

Introdurre il concetto di “oggetto esecutore”;

Presentare gli studenti alla terza fase dello sviluppo dell'algoritmo;

Introdurre il concetto di “Programma”;

Introdurre le regole per progettare e chiamare un programma;

Impara a risolvere problemi che coinvolgono la programmazione con un algoritmo lineare.

Obiettivi della lezione:

Cognitivo :

Organizzare il lavoro degli studenti per studiare e consolidare inizialmente le conoscenzeattività pratiche collettive e indipendenti.

Educativo:

Utilizzando un approccio integrato, mostrare agli studenti il ​​significato che il concetto di “oggetto-performer” ha nella natura, nella vita quotidiana, nella tecnologia e nella quotidianità.

Garantire che gli scolari sviluppino competenze che contribuiscono allo sviluppo della memoria, del pensiero logico e dell'uso delle conoscenze e abilità esistenti durante la creazione di programmi in un linguaggio di programmazione.

Educativo:

Formazione della cultura dell'informazione, competenze e capacità di acquisizione collettiva e indipendente della conoscenza;

Coltivare una cultura della parola quando si risponde alla lavagna, rispetto per tutti i partecipanti al processo educativo.

Durante le lezioni

Fase organizzativa

Saluti reciproci tra docente e studenti; registrazione degli assenti; verificare le condizioni esterne dell'aula; verificare la preparazione degli studenti alla lezione; organizzazione dell'attenzione e prontezza interna.

Annunciare l'argomento e gli obiettivi della lezione. Ripetizione del materiale

Oggi in classe continueremo a studiare la tecnologia per risolvere i problemi utilizzando un computer. Abbiamo già acquisito familiarità con il concetto di algoritmo e le sue proprietà. E prima di iniziare a studiare nuovo materiale, controlleremo la tua preparazione per la lezione.

Rilievo frontale:

Elencare le fasi della risoluzione di un problema utilizzando un PC (enunciazione del problema, definizione delle condizioni, costruzione di un modello del problema, descrizione dell'algoritmo per risolvere il problema, selezione dell'ambiente ottimale per la soluzione, descrizione dell'algoritmo utilizzando il software selezionato, testando la soluzione al problema, se necessario, correzione della soluzione al problema)

Elencare le principali proprietà dell'algoritmo (discretezza, accuratezza, comprensibilità, disponibilità di massa, efficacia)

Elencare le principali forme di presentazione degli algoritmi (verbale, grafica, software, tabellare)

Spiegazione del nuovo materiale:

Gli algoritmi per risolvere vari problemi devono essere fattibili nell'ambiente in cui è necessario ottenere il risultato. Deve esserci un oggetto in questo ambiente che eseguirà l'algoritmo. Diamo un'occhiata a un esempio. Petya voleva il tè. Fece bollire l'acqua in un bollitore, mise una bustina di tè in una tazza, vi versò dell'acqua bollente, aggiunse due cucchiaini di zucchero, li mescolò con un cucchiaio e bevve il suo tè con piacere. Elaboriamo l'algoritmo delle azioni di Petya sotto forma di un diagramma di flusso (l'insegnante chiama lo studente alla lavagna).

In questo esempio, tutte le azioni specificate vengono eseguite da Petya, quindi è lui l'oggetto che esegue l'algoritmo. Petya sa come e può eseguire le azioni specificate nell'algoritmo. Esegue queste azioni nell'ordine specificato. Viene chiamato l'oggetto che esegue l'algoritmoesecutore .

Ci sono artisti formali e informali. Un esecutore formale esegue lo stesso comando nello stesso modo. Un esecutore informale può eseguire un comando.

Gli esecutori formali sono estremamente diversi, ma per ciascuno di essi è possibile specificare le seguenti caratteristiche: la gamma di compiti da risolvere (scopo), l'ambiente, il sistema di comando e la modalità operativa.

Gamma di compiti da risolvere. Ogni artista è creato per risolvere una certa gamma di problemi: costruire catene di simboli, eseguire calcoli, costruire disegni su un piano e così via.

Ambiente dell'artista – condizioni alle quali l’algoritmo può essere eseguito.

Sistema di comando dell'esecutore (SCS) – un elenco di azioni che l'esecutore è in grado di comprendere ed eseguire.

Il sistema dei fallimenti degli artisti è un elenco di fallimenti che si verificano quando è impossibile eseguire l'algoritmo in condizioni specifiche.

Modalità operative dell'esecutore – modalità di controllo diretto e di programma. Controllo diretto: l'esecutore attende un comando da una persona ed esegue immediatamente ciascun comando. Controllo del programma: all'esecutore viene data una sequenza di comandi (programma), quindi esegue i comandi automaticamente. Alcuni artisti lavorano solo in una delle modalità.

Gli artisti presenti nei compiti sono "Cavalletta", "Calcolatrice", "Pendolo", "Tartaruga", "Freccia", "Tintore", "Freccia", "Tartaruga", "Acquario", ecc. eccetera.

Esempio: Performer La tartaruga si muove sullo schermo del computer, lasciando una traccia sotto forma di linea. Il sistema di comando è composto dai seguenti comandi:

InoltrareN(DoveN– intero) – provoca il movimento diNfa un passo nella direzione del movimento, nella direzione in cui sono rivolti la testa e il corpo.

GiustoM(DoveM– intero) – provoca un cambio di direzione del movimento diMgradi in senso orario.

Registra ripetizioneK [<Команда1> <Команда2> … <Команда N>] – significa che la sequenza di comandi tra parentesi verrà ripetutaKuna volta.

Pensa a quale forma apparirà sullo schermo dopo che la Tartaruga avrà eseguito il seguente algoritmo:

Ripeti 12[ Destra 45 Avanti 20 Destra 45]

Risposta:

Esempio: Il sistema di comando del computer è costituito da due comandi, a cui vengono assegnati numeri:

1 – sottrai 1

2 – moltiplicare per 3

Quando si scrive un algoritmo, per brevità, vengono indicati solo i numeri di comando. Ad esempio, l'algoritmo 21212 significa quanto segue

Moltiplicare per 3

Sottrai 1

Moltiplicare per 3

Sottrai 1

Moltiplicare per 3

Utilizzando questo algoritmo, il numero 1 viene convertito in 15: ((1*3-1)*3-1)*3=15

Esempio: Performer Robot agisce su un campo a scacchi, tra le celle adiacenti potrebbero esserci dei muri. Il robot si muove lungo le celle del campo e può eseguire i seguenti comandi: su, giù, destra, sinistra.

Quando si esegue ciascuno di questi comandi, il Robot si sposta in una cella adiacente nella direzione indicata. Se c'è un muro in questa direzione tra le celle, il robot viene distrutto.

Cosa accadrà al Robot se esegue una sequenza di comandi: destra, giù, destra, giù, destra. Aver iniziato a spostarsi dalla cella A. Quale sequenza di comandi deve eseguire il Robot per spostarsi dalla cella A alla cella B senza essere distrutto incontrando muri?

Viene chiamato un algoritmo presentato in un linguaggio comprensibile all'Esecutoreprogramma .

Programma – una sequenza ordinata di comandi (istruzioni) necessari affinché un computer risolva un determinato compito.

La principale difficoltà nello sviluppo di programmi per computer risiede nel creare o trovare un algoritmo. Compilare un programma utilizzando un algoritmo noto è chiamato codifica.

La programmazione (codifica) è il processo di creazione di un programma per un computer.

Ogni algoritmo presentato come programma deve avere un nome univoco che non coincide con le parole integrate nel linguaggio. Un programma ha un'intestazione che ne indica il nome. Il nuovo algoritmo viene salvato nella memoria del computer con il proprio nome e può essere richiamato (eseguito) inserendo il nome di questo programma. I programmi hanno le stesse proprietà degli algoritmi.

Riepilogo della lezione:

Dialogo:

Cosa hai imparato di nuovo durante la lezione?

Qual è il significato pratico della questione studiata?

Quali sono gli aspetti positivi della lezione?

Auguri

Grazie per il tuo lavoro in classe!

Esistono due tipi di artisti: formale e informale.

Un esecutore formale esegue sempre lo stesso comando nello stesso modo.

Un esecutore informale può eseguire un comando in diversi modi.

Ad esempio, quando ascolti ripetutamente un disco con la tua melodia preferita, puoi essere sicuro che verrà riprodotto dal lettore (esecutore formale) allo stesso modo. Ma è improbabile che qualcuno dei cantanti (esecutori informali) sia in grado di eseguire più volte una canzone del proprio repertorio esattamente nello stesso modo.

Di norma, una persona agisce come un artista informale.

Gli esecutori formali sono prevalentemente dispositivi tecnici.

Una persona nel ruolo di artista informale è responsabile delle proprie azioni.

L'oggetto che lo controlla è responsabile delle azioni dell'esecutore formale.

Consideriamo più in dettaglio l'insieme degli artisti formali. Gli esecutori formali sono estremamente diversi, ma per ciascuno di essi è possibile specificare la gamma di compiti da risolvere, l'ambiente, il sistema di comando, il sistema di guasto e le modalità operative.

1. Gamma di compiti da risolvere. Ogni esecutore è creato per risolvere una specifica classe di problemi.
2. Ambiente dell'artista. L'area, l'ambientazione, le condizioni in cui opera l'esecutore sono solitamente chiamate l'ambiente di un dato esecutore.
3. Sistema di comando dell'esecutore. Un'istruzione per eseguire un'azione completata separata dell'esecutore è chiamata comando. L'insieme di tutti i comandi che possono essere eseguiti da un qualche esecutore forma lo SKI - il sistema di comandi dell'esecutore.
4. Sistema di fallimento dell'esecutore. Il rifiuto “non capisco” avviene quando all’esecutore viene dato un comando che non fa parte del suo SCI. Il rifiuto “non posso” avviene quando un comando proveniente dallo SCI non può essere eseguito dallo stesso in determinate condizioni ambientali.
5. Modalità operative dell'esecutore. Per la maggior parte degli artisti, vengono fornite modalità di controllo diretto e di programma. Nel primo caso, l'esecutore attende i comandi di una persona ed esegue immediatamente ogni comando ricevuto. Nel secondo caso, all'esecutore viene prima fornita una sequenza completa di comandi (programma), quindi esegue automaticamente tutti questi comandi. Alcuni artisti lavorano solo in una delle modalità indicate.

Sviluppo di algoritmi - un compito ad alta intensità di manodopera che richiede che una persona abbia una conoscenza approfondita e molto tempo. Risolvere un problema utilizzando un algoritmo già pronto richiede solo che l'esecutore segua rigorosamente le istruzioni fornite. L'esecutore non approfondisce il significato di ciò che sta facendo e non spiega perché agisce in questo modo e non in altro modo: agisce in modo formale. A ciò si collega la possibilità di automatizzare le attività umane:

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

Appendice n. 1

ALGORITMO E PERFORMER

Scopo dello studio: padroneggiare i concetti di algoritmo, esecutore, avere un'idea dell'algoritmo come modello dell'attività dell'esecutore.

Algoritmo

Definizioni algoritmo

Un algoritmo è una descrizione precisa della sequenza di azioni volte a risolvere un determinato problema.

Un algoritmo è un modello dell'attività dell'esecutore dell'algoritmo.

Bersaglio

Un algoritmo viene sviluppato per risolvere uno specifico problema o classe di problemi.

Modulo di registrazione dell'algoritmo

Gli algoritmi possono essere scritti sotto forma di tabella, elenco numerato, programma o diagramma di flusso.

Un algoritmo viene compilato per un artista specifico, in una lingua che capisce.

Esecutori di algoritmi

L'esecutore dell'algoritmo può essere una persona, un gruppo di persone, un animale o dispositivi tecnici in grado di eseguire una determinata sequenza di comandi.

Fig. 1 Esecutore - dispositivo tecnico

Fig.2. L'esecutore è un animale

Fig.3. Esecutore - umano

Squadra

Un'istruzione per eseguire un'azione completata separata da un esecutore è chiamata comando. I comandi che uno specifico esecutore deve eseguire formano un sistema di comandi dell'esecutore.

Esecutori formali ed informali dell'algoritmo

Gli esecutori dell'algoritmo possono essere formali o informali.

Un esecutore informale può eseguire lo stesso comando in modi diversi. Il ruolo di un artista informale è interpretato da una persona o da un animale. L'esecutore informale è responsabile delle proprie azioni.

Riso. 4. Esecutore informale

Un esecutore formale esegue sempre lo stesso comando nello stesso modo. Gli esecutori formali sono prevalentemente dispositivi tecnici. Ad esempio, un forno a microonde, una lavatrice, ecc. L'oggetto che lo controlla è responsabile dell'azione dell'esecutore formale. Per ogni esecutore formale, è possibile specificare la gamma di compiti da risolvere, l'ambiente, il sistema di comando, il sistema di guasto dell'esecutore e le modalità operative.

Fig.5. Esecutore formale

L'ambiente dell'esecutore è solitamente chiamato l'area, l'ambientazione e le condizioni in cui l'esecutore opera. Ad esempio, l'ambiente dell'esecutore Disegnatoreè il piano delle coordinate.

Riso. 6. L'ambiente dell'artista è un disegnatore.

Fallimenti

Considerando l’ambiente e il sistema dei comandi dell’esecutore, è possibile creare un sistema di rifiuti: “non capisco”, “non posso”. Se all’esecutore viene dato un comando che non è compreso nel suo sistema di comandi dell’esecutore, allora si verifica un rifiuto “Non capisco”.

Comando: “Scalda il panino”

Riso. 7. Rifiuto “Non capisco”

Se all'esecutore viene dato un comando dal sistema di comando dell'esecutore, che non può eseguire in specifiche condizioni ambientali, si verifica un fallimento "Non posso".

Squadra: "Andare avanti"

Riso. 8. Rifiuto “Non posso”

Gestione degli artisti

La gestione è il processo di influenza diretta di alcuni oggetti su altri.

Gli artisti sono oggetti di gestione. Puoi gestirli creando un algoritmo per loro.

Due modalità di controllo

Per la maggior parte degli artisti, vengono fornite due modalità: controllo diretto e controllo del programma.

La modalità in cui l'oggetto di controllo controlla l'esecutore in un dato momento è chiamata modalità di controllo diretto.

Riso. 7. Modalità di controllo diretto

La modalità in cui una persona controlla l'esecutore utilizzando un programma preparato è chiamata modalità di controllo del programma.

Riso. 8. Modalità di controllo del programma

Per raggiungere l'obiettivo di studiare questo paragrafo, completa formazione e mettiti alla prova utilizzando il modulo compiti a casa .

Un esecutore è una persona, un gruppo di persone, un animale o un dispositivo tecnico in grado di eseguire un determinato insieme di comandi. Esempi: Oggetto - esecutore!! Pulsante di accensione/spegnimento sul case del computer Vai all'inizio Pausa Stop Vai alla fine Riproduzione Sistema di comandi per l'esecutore - Lettore CD

Un artista più complesso. Funziona secondo programmi creati dall'uomo. Il programma è scelto dalla persona. La macchina funziona automaticamente. Un artista più complesso. Funziona secondo programmi creati dall'uomo. Il programma è scelto dalla persona. La macchina funziona automaticamente. Esecutore - lavatrice

Esecutori informali e formali Il ruolo di un esecutore informale è spesso interpretato da una persona. Il ruolo di un esecutore formale è spesso interpretato da un dispositivo tecnico. L'esecutore informale è responsabile delle proprie azioni per le azioni di un esecutore formale.

Esecutore formale Un esecutore formale esegue sempre lo stesso comando nello stesso modo. Macchina riempitrice e confezionatrice automatica Per ogni esecutore formale è possibile specificare: la gamma di compiti da risolvere; ambiente; sistema di comando; sistema di fallimento; modalità operative.

Sistema di rifiuto dell'esecutore Il rifiuto del “non capisco” avviene se viene impartito un comando non compreso nello SKI. Un errore "Can not" si verifica se un comando dallo SKI non può essere eseguito in condizioni ambientali specifiche. ? La lavatrice non può eseguire il comando di risciacquo se non arriva l'acqua alla macchina. ?

L'automazione è la sostituzione di parte del lavoro umano con il lavoro delle macchine: il processo di risoluzione di un problema si presenta come una sequenza di semplici operazioni; viene creata una macchina in grado di eseguire queste operazioni in una determinata sequenza; l'esecuzione dell'algoritmo è affidata ad un dispositivo automatico; una persona è liberata dalle attività di routine. Automazione

La cosa più importante è che un esecutore sia una persona, un gruppo di persone, un animale o un dispositivo tecnico in grado di eseguire determinati comandi. Un esecutore formale esegue sempre lo stesso comando nello stesso modo. Per ciascun esecutore formale è possibile indicare: – la gamma di compiti da risolvere; -Mercoledì; – sistema di comando; – sistema di guasto; - modalità operative.

Fondamenti matematici dell'informatica

A.G. Gein

Programma

№_GIORNALI	Conferenza
	Lezione 1.Cosa sono i “fondamenti matematici dell’informatica”. Perché l'informatica è spesso considerata affine a madre della matematica? È vero? L’informatica è possibile senza la matematica? Quale matematica devi padroneggiare? informatica? La matematica scolastica può fornire una base per l’informatica? L'informazione e la sua codifica. Matematica dei codici. Codici di correzione degli errori. Codificazione economica.
	Lezione 2.Modelli matematici degli esecutori formali. Cos’è il trattamento formale delle informazioni? FINE- nuove macchine. Cosa viene prima: la lingua o l'interprete? Grammatica della lingua. Lingue riconosciute. Versioni universali teli (macchina di Turing, macchina postale).
	Lezione 3.Algoritmo e sue proprietà. Indecidibilità algoritmica. Calcolabilità. Complessità.
	Prova n. 1.
	Lezione 4. Grafici. Grafici e digrafi. In quali compiti sorgono? Varie proprietà dei grafi (Euleriano, Hamiltoniano) novità, planarità, bipartitismo). Reti. Flussi nelle reti. Rappresentazione grafica. Algoritmi grafici di base.
	Lezione 5. Modelli logici in informatica. Algebra delle proposizioni. Funzioni booleane. Forme normali. Pieno classi di funzioni booleane. Schemi dei contatti dei relè. Valvole. Modelli matematici del processore e della memoria del computer. Predicati e relazioni. Algebra relazionale. Fondamenti teorici dei DBMS relazionali. Linguaggi di programmazione logica e loro basi matematiche.
	Prova n.2.
	Lezione 6. Teoria dei numeri dei computer e geometria computazionale. Perché la teoria dei numeri è necessaria in informatica? scienze? Corsa ai numeri primi. Come fattorizzare un numero? Qual è la differenza tra geometria teorica e informatica? Perché è fluido sulla carta, ma goffo sul computer? Regole di base e algoritmi di calcolo geometria.
23/2007	Lezione 7. Protezione dati. Protezione dell'informazione simbolica. Cosa è necessario proteggere? Firma elettronica. Sistemi verifica. Crittosistemi a chiave pubblica. Protezione delle informazioni grafiche. La matematica delle filigrane elettroniche.
24/2007	Lezione 8. Fondamenti di metodi per l'insegnamento dei fondamenti matematici dell'informatica.
	Lavoro finale

Lezione 2.
Modelli matematici degli esecutori formali

“La grazia è fredda in questo mondo vano.” Questa frase è stata composta da un computer utilizzando uno dei primi programmi di generazione di testi in linguaggio naturale. Ma l'emozione trasmessa da questa frase è, ovviamente, inaccessibile a un computer. E il computer non riesce a capire il significato di questa frase. Perché è solo un artista formale.

Nella nostra coscienza pubblica, la parola “formale” ha solitamente una connotazione negativa. Noi diamo l'etichetta sprezzante di “formalista” a un funzionario che agisce esclusivamente sulla base delle istruzioni che gli sono state impartite, senza voler approfondire l'essenza del problema che gli viene posto.

Ma è sempre negativo essere un artista formale? Il proprietario del cane da pastore sarà felice quando il comando "Fas!" il suo amico a quattro zampe si chiederà se valga la pena di immischiarsi con il bandito. Oppure quando l’aereo, in risposta al movimento del timone del pilota, continua a volare sulla stessa rotta, perché non si vuole virare. E l'operatore del reattore nucleare, abbandonando le istruzioni, lo controllerà per capriccio. D'accordo sul fatto che anche per una persona a volte è semplicemente necessario essere un artista formale. Per quanto riguarda i dispositivi per l'elaborazione automatica delle informazioni, il percorso informale semplicemente non è possibile. Ricordiamo che, come osservato nella Lezione 1, l'informatica si occupa dello studio dei processi automatizzati di elaborazione delle informazioni.

L'elaborazione (trasformazione) delle informazioni è un processo informativo abbastanza ampio. Per elaborazione delle informazioni si intende l'ottenimento di nuove informazioni da informazioni esistenti o la trasformazione della forma di presentazione delle informazioni.

L'investigatore ha raccolto prove e identificato chi ha commesso il crimine. Il matematico confrontò le affermazioni a lui note e dimostrò un nuovo teorema. DI. Mendeleev, sulla base delle informazioni sulle proprietà chimiche degli elementi, formulò la legge periodica. In tutti questi esempi, nuove informazioni sono emerse come risultato dell'elaborazione delle informazioni.

Anche il calcolo della somma di due numeri dovrebbe essere riconosciuto come elaborazione delle informazioni: dopo tutto, da due dati noti se ne ottiene uno nuovo, precedentemente sconosciuto. L'elaborazione delle informazioni è, ad esempio, la traduzione di una frase dal russo in una lingua straniera.

A prima vista, c’è una grande differenza tra i processi di elaborazione delle informazioni identificati nei due paragrafi precedenti. La differenza principale qui è che per trovare un criminale o dimostrare un nuovo teorema, non esistono e non possono essere specificate regole rigide su come dovrebbero essere elaborate le informazioni iniziali. Come si suol dire, in questi casi una persona agisce euristicamente. Quando aggiungiamo due numeri, siamo già guidati da regole rigorosamente specificate. Tale lavoro può essere affidato ad un dispositivo tecnico in grado di comprendere ed eseguire le istruzioni ad esso assegnate. I dispositivi controllati da istruzioni ed eseguono il loro lavoro automaticamente sono chiamati programmabili e si dice che svolgano il loro lavoro in modo formale.
In particolare si può parlare di trattamento formale delle informazioni. L'esecutore che esegue tale elaborazione non deve approfondire il significato delle azioni che esegue; pertanto, il trattamento formale delle informazioni, di norma, riguarda la modifica della forma della sua presentazione, piuttosto che del suo contenuto.

Pertanto, mediante l'elaborazione delle informazioni è conveniente comprendere qualsiasi trasformazione del suo contenuto o forma di presentazione.

Tuttavia, qualunque sia il metodo di elaborazione delle informazioni, formale o euristico, c'è qualcosa o qualcuno che esegue questa elaborazione. Di solito viene chiamato esecutore.

Gli artisti formali possono essere strutturati in modi molto diversi. Per studiarli, come in ogni scienza, viene utilizzata la modellazione. In questa lezione vi diremo quali modelli matematici vengono utilizzati per studiare gli artisti formali.

§ 3. Esecutore formale: automa

L'uomo ha avuto molto successo nel creare una varietà di dispositivi che svolgono questo o quel lavoro secondo istruzioni chiare. Allo stesso tempo, non dovrà più trovarsi costantemente vicino a questo dispositivo per controllarlo. In questo caso, dicono che il dispositivo esegue il lavoro automaticamente e viene chiamato tale dispositivo stesso automaticamente.

In realtà, le slot machine sono molto diverse. Potrebbe trattarsi di una macchina per la vendita di biglietti per i treni pendolari, o una macchina per l'imballaggio di prodotti finiti, o una macchina per la produzione di qualsiasi parte. Vengono spesso chiamati automi di quest'ultimo tipo robot industriali.

Dal punto di vista informatico, non importa di cosa è fatta la macchina. L'unica cosa importante è che percepisca alcuni segnali come comandi e, per ogni comando, esegua un'azione, passando da uno stato all'altro. Pertanto, possiamo supporre che ogni automa sia descritto da un insieme di possibili stati, un elenco di comandi validi e un elenco di quale stato l'automa va a quale sotto l'influenza di ciascun comando. Ad esempio, se ci sono solo due comandi, possono essere designati con lettere, ad esempio: UN E B o in numeri, stati della macchina - in lettere Q 1, Q 2, ..., mq, ed è possibile elencare le opzioni per la transizione da uno stato all'altro utilizzando una tabella (vedere Tabella 1).

Tabella 1

La cella posta all'intersezione di una riga e di una colonna indica lo stato in cui si porta l'automa se si trovava nello stato indicato nell'intestazione della stessa colonna e ha ricevuto il comando indicato nell'intestazione della stessa riga. È chiaro a tutti che tale tabella rappresenta un modello informativo di una macchina reale.

L'automa può anche essere descritto da un altro modello informativo: un digramma*. I vertici del digrafo sono gli stati dell'automa e gli archi sono le transizioni da uno stato all'altro. Ogni arco ha un segno che indica quale comando viene utilizzato per la transizione. Quindi la macchina descritta nella Tabella. 2, verrà visualizzato come mostrato in riso. 1.

Tavolo 2

Uno degli stati è chiamato stato iniziale: è in esso che si trova la macchina prima dell'inizio del funzionamento. Accettiamo di denotare sempre lo stato iniziale Q 1. Alcuni stati sono definitivi: portare la macchina in questo stato è l'obiettivo del controllo della macchina utilizzando l'una o l'altra sequenza di comandi. Ad esempio, se si tratta di una macchina per la vendita di biglietti ferroviari, nello stato iniziale la macchina si aspetta che le monete inizino a fluire nella gettoniera. Ci sono due stati finali: emettere un biglietto e restituire il denaro. Inoltre, ci sono stati intermedi: il conteggio della quantità di denaro trasferita alla macchina in questo momento. I comandi che trasferiscono la macchina da uno stato all'altro sono l'immissione di una moneta nella gettoniera, la pressione del pulsante di emissione del biglietto o la pressione del pulsante di restituzione del denaro. Indicheremo il fatto che questo stato è definitivo con la lettera K tra parentesi accanto alla designazione di questo stato. Per esempio, Q 2(K).

È chiaro che lo scopo del controllo di un automa è di impartirgli una sequenza di comandi che lo trasferiscano da uno stato iniziale a uno stato finale. Poiché ogni comando è contrassegnato da una lettera, l'insieme dei comandi compresi da questa macchina può essere considerato un certo alfabeto UN. Quindi la sequenza di comandi, ad es. programma verrà scritto come una parola in questo alfabeto. Ad esempio, la parola aba traduce la macchina descritta in Tabella. 2, dallo stato iniziale Q 1 nello stato Q 4 . aba Possiamo dire che la parola Q definisce sul digramma di un dato automa un certo percorso dallo stato Q 4 .

1 nello stato L'insieme di tutte quelle parole che trasferiscono l'automa dallo stato iniziale a uno degli stati finali forma un certo linguaggio formale. Questa lingua si chiama lingua riconosciuta da questa macchina . Se per una determinata lingua esiste almeno un automa riconosciuto da questa lingua, viene chiamata tale lingua.

riconoscibile riso. SU Q 2 mostra un automa avente due stati: Q 2 - e comprende due comandi, designati dai numeri 0 e 1. È facile capire che il linguaggio riconosciuto da questa macchina è costituito da quelle e solo quelle parole che contengono un numero pari di uno e un numero qualsiasi di zeri. In altre parole, questa macchina calcola la somma delle cifre di un numero scritto nel sistema numerico binario.

Consideriamo ora un alfabeto fisso UN, E l- un certo insieme di parole composto da simboli di un dato alfabeto. È sempre possibile costruire un automa tale che il set l era un linguaggio riconoscibile per lui? La risposta è no.

Teorema. Permettere UN = {UN, B}, l = {a n b n, Dove N attraversa l'insieme di tutti i numeri naturali). Un mucchio di l non è una lingua riconosciuta.

Documentazione UN, che compare nella formulazione di questo teorema, significa che la lettera UN ripetuto N una volta.

La dimostrazione del teorema utilizza uno dei metodi matematici più importanti - per contraddizione. Quindi supponiamolo l- lingua riconosciuta. Ciò significa che esiste un automa che può essere tradotto in uno stato finale da qualsiasi parola di questa lingua. Lascia che questa macchina abbia K stati. Considera la parola akbk l. Appartiene alla lingua Q e, quindi, trasferisce questo automa dallo stato iniziale Q 1 a qualche stato finale UN S. Q Dalla lettera K viene ripetuto un numero di volte non inferiore al numero di stati dell'automa, esiste un tale stato UN t , che è per il primo riso. domande di lettere Q sarà superato due volte (vedi 3). Lascia che la macchina entri nello stato per la prima volta t come risultato dell'applicazione 3). Lascia che la macchina entri nello stato per la prima volta + un u e la prossima volta sarà nello stesso stato dopo l'applicazione v + un u . Considera la parola un k Q bk Q. È chiaro che applicare questa parola allo stato iniziale l 1 lo metterà nello stesso stato finale l S. Ciò significa che questa parola viene riconosciuta anche da questa macchina e, quindi, deve appartenere alla lingua

. Ma in abbondanza Q non esiste una parola del genere. La contraddizione risultante mostra che l’ipotesi fatta è errata, cioè Non esiste un automa per il quale questo insieme possa servire come linguaggio riconoscibile. Q Riso. 3. Percorso sul digramma dell'automa dallo stato iniziale Q 1 allo stato finale UN s (allo Stato lettera t poggia su archi un u tu

una volta, in ciclo - di nuovo

una volta)

1. Quali due modelli informativi possono essere rappresentati da un automa?

2. Qual è la lingua riconosciuta da questa macchina?

3. Quale linguaggio è chiamato riconoscibile?

4. Per la macchina mostrata in riso. 1, determina in quale stato si troverà dopo aver eseguito la sequenza di comandi

UN) abba; V) babaabaaa;

B) ababbabbb; G)* a n b n.

5. Per la macchina mostrata in riso. 2, fare una descrizione sotto forma di tabella.

6. Costruisci sotto forma di grafico un modello informativo della macchina specificata nella Tabella. 3.

Tabella 3

7. Quale lingua oltre l'alfabeto a due caratteri (0, 1) viene riconosciuta dalla macchina mostrata in riso. 4?

Riso. 4

8. Quale lingua è sopra l'alfabeto a due caratteri ( UN, B) viene riconosciuto dalla macchina specificata nella tabella. 3?

9. Disegna sotto forma di grafico il modello informativo di un automa che riconoscerebbe una lingua sull'alfabeto (0, 1), costituito da tutte le parole contenenti esattamente 5 parole consecutive.

10. Disegna come grafico il modello informativo di un automa che riconoscerebbe una lingua sull'alfabeto (0, 1), costituito da tutte le parole contenenti esattamente 5 unità.

11. Disegna come un grafico il modello informativo di un automa che riconoscerebbe una lingua sull'alfabeto (0, 1), costituito da tutte le parole che iniziano con uno (cioè, questo automa distingue i numeri naturali scritti nel sistema numerico binario da sequenze arbitrarie caratteri 0 e 1).

12. Tra le lingue elencate di seguito l 1 , l 2 , l 3 , l 4 definiti su un alfabeto di due caratteri (1; 2), indicano quali sono riconoscibili. Per ciascuna delle lingue riconosciute, costruire un automa che la riconosca; per ciascuna delle lingue irriconoscibili, dimostrare che è irriconoscibile.

UN) l 1 è composto da tutte le parole che rappresentano anche i numeri naturali che iniziano con il numero 1;

B) l 2 è costituito da tutte le parole il cui numero di unità è un numero naturale che termina con il numero 3;

V) l 3 è costituito da tutte le parole in cui il numero di due è un numero primo;

G) l 4 è formato da tutte le parole che sono numeri naturali divisibili per 3.

13. Dal punto di vista dell'informatica, qual è la differenza tra “vivere secondo leggi” e “vivere secondo concetti”?

§ 4. Esecutore universale

Giochi per computer... Probabilmente chiunque abbia avuto a che fare almeno una volta con un computer ha visto, e forse anche giocato, una specie di gioco per computer. Sullo schermo, alcuni oggetti sotto forma di esseri viventi o dispositivi tecnici obbediscono ai comandi del giocatore, altri sono controllati da un computer che esegue un determinato programma. Tutti questi oggetti sono esecutori formali, ciascuno con il proprio insieme di azioni consentite. Solo che questi oggetti non sono reali, ma simulati da un computer. Si scopre che con l'aiuto di un artista formale ne vengono imitati altri.

Se proviamo a formulare cosa significa che un artista viene imitato con l'aiuto di un altro, otterremo quanto segue. Dicono che l'esecutore formale UN imita un esecutore formale IN, Se

Ogni oggetto su cui l'esecutore esegue azioni IN, corrisponde univocamente all'oggetto su cui l'esecutore esegue azioni UN(imitazione dell’ambiente dell’esecutore);

Ogni azione consentita dell'esecutore IN l'azione consentita dell'esecutore è abbinata in modo univoco all'uno o all'altro oggetto dell'ambiente UN sull'oggetto corrispondente del suo ambiente (imitazione di azioni);

Ogni istruzione redatta per l'esecutore IN e che conducono, quando eseguiti, a un certo risultato (cioè a un certo stato dell'ambiente dell'esecutore e di se stesso), possono essere trasformati mediante l'imitazione di azioni consentite in istruzioni per l'esecutore UN, la cui esecuzione porta al risultato corrispondente nell'ambiente dell'esecutore UN.

Tuttavia, il presupposto che gli artisti UN E IN il diverso ambiente in cui esistono non è fondamentale dal punto di vista informativo. Ad esempio, esecutore UN si occupa di numeri e IN converte le immagini grafiche. Ma già sapete che in ognuno di questi casi si tratta infatti di trasformare informazioni opportunamente codificate. Inoltre si può presumere che venga utilizzato lo stesso codice binario. In questo senso, possiamo considerare che l'ambiente dell'esecutore è semplicemente lo stesso: l'informazione presentata sotto forma di messaggio codificato.

Una delle domande più importanti nell'informatica teorica è: esiste un esecutore formale con cui si possa imitare qualsiasi esecutore formale? È naturale chiamare un artista del genere universale. È facile capire che un esecutore universale non esiste come dispositivo fisico: dopo tutto, le informazioni possono essere codificate in messaggi arbitrariamente lunghi e qualsiasi mezzo fisico è limitato. Se parliamo dell'esecutore universale come oggetto ideale, risulta che la risposta alla domanda posta è positiva. Ed è stato ottenuto quasi contemporaneamente e indipendentemente da due eminenti scienziati: A. Turing (nel 1936) ed E. Post (nel 1937). Gli artisti proposti differivano l'uno dall'altro, ma si è scoperto che potevano imitarsi a vicenda e, soprattutto, imitare qualsiasi artista formale in generale.

L'esecutore universale è solitamente chiamato macchina. È anche comune chiamare le macchine con il nome dei loro inventori. Quindi l'esecutore universale inventato da A. Turing è chiamato macchina di Turing; l'esecutore descritto da E. Post - La macchina di Post. Successivamente apparvero altri artisti universali, ad esempio la macchina Minsky.

Quindi, possiamo supporre di avere un messaggio scritto in qualche alfabeto e che deve essere convertito in un altro messaggio. Naturalmente, scrivere istruzioni a un esecutore formale per elaborare una coppia specifica di messaggi non è una questione complicata. Ma sai già che il vero interesse è nelle istruzioni (cioè negli algoritmi) che ti permettono di risolvere un’intera classe di problemi simili – la cosiddetta “proprietà di massa di un algoritmo”. Ad esempio, questa attività: aggiungi un altro simbolo predeterminato a destra di qualsiasi messaggio. Se, ad esempio, una sequenza di simboli identici funge da codice per un numero naturale - il numero di simboli nella sequenza è il numero naturale codificato - allora in realtà stiamo parlando di creare un algoritmo per aumentare il numero di 1.

È naturale supporre che il messaggio sia registrato su nastro. Inoltre, è conveniente immaginare questo nastro diviso in celle uguali, e ciascuna cella contiene esattamente un carattere del messaggio. Poiché i messaggi possono essere lunghi quanto si desidera, concorderemo nell'immaginare il feed come infinito. Le celle vuote verranno considerate riempite con il simbolo “spazio”. Pertanto, abbiamo annunciato che qualsiasi alfabeto che utilizzeremo per registrare i messaggi su questo nastro dovrà contenere uno “spazio”. Accettiamo di designarlo UN 0 . I restanti caratteri dell'alfabeto utilizzati per registrare i messaggi su nastro saranno indicati con UN 1 , UN 2 , ..., UN N. Se, ad esempio, dobbiamo scrivere il problema del calcolo della somma di due numeri, allora l'alfabeto può essere preso come segue: UN 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 0; ,; +; =. Per una determinata coppia di dati (ovvero due numeri), la voce sul nastro potrebbe apparire, ad esempio, come mostrato in riso. 5.

Riso. 5

Ovviamente non scriveremo un simbolo sul nastro nelle celle vuote UN 0, il che implica che è lì. Inoltre, concordiamo che il primo carattere del messaggio, diverso dallo spazio, appaia sempre nella stessa cella - on riso. 4 è contrassegnato con Ї. Chiameremo questa cella quella iniziale.

Il messaggio registrato sul nastro viene elaborato da qualche dispositivo e il risultato viene riscritto sul nastro. Poiché l'esecutore è formale, non approfondisce il significato del messaggio, ma, secondo le istruzioni redatte per lui, sostituisce alcuni simboli con altri. Non siamo interessati a come viene eseguita fisicamente tale sostituzione, quindi possiamo immaginare che lungo il nastro si muova una sorta di automa, che legge un simbolo da una cella sul nastro, elabora le informazioni ricevute, stampa un altro carattere nella cella (se prescritto dalle istruzioni) e si sposta nella cella adiacente, destra o sinistra.

Sai già che ogni automa è descritto da un insieme di stati. È consuetudine designare con lettere gli stati della macchina da lettura-stampa specificata Q 0 , Q 1 , Q 2 , ..., Q M. Allo stesso tempo, siamo d'accordo che quando la macchina è accesa, ad es. all'inizio del lavoro è sempre nello stesso stato, che indicheremo Q 0 e si trova di fronte alla cella di partenza.

Pertanto, una macchina di Turing è formalmente descritta da un insieme di due alfabeti: UN = {UN 1 , UN 2 , ..., UN) E Q = {Q 0 , Q 1 , Q 2 , ..., Q M). Alfabeto UN chiamato esterno e serve per registrare i messaggi iniziali, l'alfabeto Q chiamato interno e descrive un insieme di stati del dispositivo lettore-stampa. Rappresenteremo una macchina di Turing come mostrato in riso. 6.

Riso. 6

riconoscibile riso. La Figura 6 mostra il momento di funzionamento della macchina di Turing, quando il dispositivo di lettura-stampa rileva la terza cella da quella iniziale (in questo momento c'era un simbolo COME 3) ed è in uno stato qk.

Quindi le azioni ammissibili di una macchina di Turing sono:

Scrivere qualsiasi simbolo dell'alfabeto esterno nella sezione del nastro (il simbolo che c'era prima viene cancellato);

Passare alla sezione successiva;

Cambiare lo stato in uno di quelli indicati dal simbolo dell'alfabeto interno;

Smettere di lavorare (stop).

Naturalmente, in questa enumerazione, ogni riga indica non un'azione, ma un gruppo di azioni dello stesso tipo: ci sono tante azioni "scrivi un simbolo dell'alfabeto esterno" quanti sono questi simboli, puoi spostarti su quella adiacente sezione a destra o a sinistra, ci sono tante azioni per cambiare stato quanti sono questi stati (cioè quanti caratteri dell'alfabeto interno).

Ora dobbiamo dire come vengono scritti i comandi per eseguire le azioni specificate. Ogni comando macchina contiene al massimo un'azione da ciascun gruppo di azioni e ha la forma

I comandi effettivi sono simili a questi:

un io Q j - scrivere alla sezione monitorata UN i , spostati a destra (alla sezione successiva) ed entra nello stato Q J ;

un io Q j - scrivere alla sezione monitorata UN i , spostati a sinistra e vai allo stato Q J ;

un io S Q j - scrivere alla sezione monitorata ai, fermati e vai allo stato Q J.

Per eseguire azioni, una macchina di Turing è dotata di un'unità logica-operativa. Questo blocco ha due input: attraverso uno di essi si ricevono informazioni su quale simbolo si trova nella cella monitorata, attraverso l'altro - informazioni sullo stato in cui si trova la macchina in una determinata fase del suo lavoro. Queste informazioni determinano in modo univoco quale comando la macchina dovrà eseguire. Poiché un comando può contenere un'istruzione per eseguire tre azioni - scrivere un carattere sul nastro, spostare e cambiare stato - il blocco logico-operazionale ha tre uscite: scrivere un carattere UN, compensare M e cambio di stato Q(cm. riso. 7).

Riso. 7. Blocco logico-operazionale della macchina di Turing

Poiché questo blocco ha solo due ingressi, la sua risposta ai simboli fornitigli può essere convenientemente rappresentata sotto forma di una tabella rettangolare in cui le righe e le colonne sono contrassegnate rispettivamente con i simboli dell'alfabeto esterno e di quello interno (vedi Tabella 4). . I comandi vengono scritti nelle celle della tabella. Se l'auto è di fronte alla piazza dove dice un io, e il suo stato è q j, viene eseguito il comando all'intersezione della linea contrassegnata con il simbolo ai e la colonna contrassegnata dal simbolo q j.

Tabella 4

Questa tabella si chiama diagramma funzionale questa macchina; svolge il ruolo di un'istruzione (programma) per una macchina di Turing. Da esso, in particolare, risulta chiaro quali siano gli alfabeti esterni ed interni della macchina.

Supponiamo, ad esempio, che una sequenza di un certo numero dello stesso simbolo "*" venga registrata su un nastro. Poi lo schema funzionale riportato in tabella. 5 fa sì che la macchina di Turing aumenti di uno il numero di stelle in questa sequenza.

Tabella 5

È impossibile dimostrare che una macchina di Turing sia un esecutore universale. Così come, ad esempio, è impossibile dimostrare la legge di conservazione dell'energia in fisica. Ma la pratica della creazione di algoritmi mostra che qualsiasi problema che una persona può risolvere oggi può essere programmato su una macchina di Turing. Questo fatto sperimentale, chiamato tesi di Turing, è formulato come segue: per un problema esiste un algoritmo per risolverlo se e solo se esiste una macchina di Turing adatta con cui risolvere questo problema.

Domande e compiti

1. Quale esecutore formale è chiamato universale?

2. Cos'è una macchina di Turing?

3. In cosa differisce una macchina di Turing da un'altra?

4. Cos'è chiamato diagramma funzionale di una macchina di Turing?

5. È vero che una macchina di Turing con un diagramma funzionale scritto per essa è una macchina a stati finiti?

6. Disegna sotto forma di una sequenza di disegni come cambiano le informazioni sul nastro durante il funzionamento della macchina di Turing, descritta dal diagramma funzionale nella tabella. 5.

7. Seguendo lo schema funzionale descritto nella tabella. 5, la macchina di Turing assegna ad una data sequenza di asterischi un asterisco in più a sinistra. Elaborare uno schema funzionale in base al quale verrà assegnato l'asterisco a destra della sequenza data.

8. Il funzionamento di una macchina di Turing è descritto dal seguente diagramma funzionale:

Determina quale messaggio sarà sul nastro dopo che la macchina avrà finito di funzionare e indica quale cella si troverà davanti al suo blocco di scrittura in quel momento.

Riso. 8

Riso. 9

9. Il nastro della macchina di Turing contiene una stringa composta da diversi simboli "*" consecutivi, seguiti da diversi simboli "#", e alla fine della riga c'è un simbolo "e" (una delle possibili varianti di tale stringa è mostrato in riso. 5).

Riso. 10

Per ciascuno dei diagrammi funzionali seguenti, determinare quale problema è progettato per risolvere. (Suggerimento: per ottenere una risposta convincente, applicare il diagramma funzionale a diverse opzioni per riempire il flusso di informazioni con sequenze di caratteri dell'alfabeto esterno.)

10. Lascia che l'alfabeto esterno sia costituito dal simbolo " UN 0 "e i numeri 0, 1, 2, ..., 9. Sul nastro viene registrato un numero naturale. Inventa una macchina di Turing e disegnane un diagramma funzionale, in base al quale questo numero verrà aumentato di 1.

11. Lascia che l'alfabeto esterno sia costituito dal simbolo " UN 0 "e i numeri 0, 1, 2, ..., 9. Sul nastro è scritto un numero naturale. Disegna un diagramma funzionale per una macchina di Turing che registrerà la somma delle cifre di questo numero su un nastro. La risposta deve essere scritta a destra del numero originale, separata da esso con uno spazio.

Riso. 11

PS Sentirsi una macchina di Turing è utile, ma faticoso. Si consiglia di completare manualmente le attività 8 e 9. Per quanto riguarda le attività 10 e 11, il test manuale degli schemi funzionali compilati potrebbe non essere efficace. A questo proposito, proponiamo di utilizzare un'implementazione informatica di una macchina di Turing creata da R. Zartdinov. Può essere ottenuto sul sito web del quotidiano “Informatica” ( inf.1settembre.ru). Ecco come appare, ad esempio, il diagramma funzionale dell'attività 8 c) su questa macchina: le differenze sono che al posto della lettera S c'è un segnale stradale e al posto del simbolo " UN 0” si scrive “_” (quando si inserisce un comando in una cella della tabella, però, è necessario premere il tasto “spazio”, non “_”). Il programma viene fornito con una guida dettagliata su come utilizzarlo. L'interfaccia di questo programma è molto semplice. Inoltre potete trovare una descrizione di questa implementazione della macchina di Turing nel giornale “Informatica” n. 8, 2006. Qui troverete anche l'analisi di molti altri problemi relativi alla programmazione della macchina di Turing; devi solo tenere presente che usano un sistema di comando leggermente diverso (che è completamente senza principi).

* Ricordiamo che un grafico è un insieme di punti chiamati picchi e linee che collegano alcuni dei vertici. Se la direzione è indicata sulle linee che collegano i vertici, viene chiamato il grafico orientata(abbreviato digramma), e le battute si chiamano sue archi. In un grafico regolare, ad es. non orientate, si chiamano le linee che collegano i vertici costolette. I grafici saranno discussi più dettagliatamente nella Lezione 4.