Presentazione sul tema della struttura degli algoritmi. Strutture algoritmiche di base

Algoritmo e strutture algoritmiche

Mosina A.Yu.

Algoritmo è una sequenza di azioni rigorosamente definita durante la risoluzione di un problema.

L'algoritmo contiene diversi passaggi.

Passo dell'algoritmo è ogni singola azione dell'algoritmo.

“Un algoritmo è un ordine di azioni.”

Esecutore è un oggetto che esegue un insieme specifico di azioni.

L'esecutore può essere una persona, un robot, un animale o un computer.

Sistema di comando dell'esecutore (SCIARE) è un insieme di comandi che l'esecutore può eseguire.

Ambiente dell'artista – l’ambiente in cui opera l’esecutore.

• Sviluppa algoritmi: umani
• Gli algoritmi vengono eseguiti da: persone e dispositivi: computer, robot, macchine, satelliti, complessi Elettrodomestici, Giocattoli per bambini.
• L'esecutore risolve il problema secondo un determinato algoritmo, seguendo rigorosamente le istruzioni (programma) senza approfondire o discutere il motivo per cui lo sta facendo.

Esercizio: Nomina gli interpreti dei seguenti tipi di lavoro:

Ripulire la spazzatura nel cortile

Insegnare ai bambini a scuola

Guida in auto

La risposta è sulla lavagna

Cucinare il cibo

Stampare un documento su una stampante

Arto– ogni singola azione e l’algoritmo nel suo insieme devono poter essere completati

Efficienza– ottenere risultati in un numero finito di passaggi

Discrezione(discontinuità, separatezza) – dividendo l'algoritmo in passaggi

Determinismo(certezza, accuratezza) – ogni azione deve essere definita in modo rigoroso e inequivocabile

Carattere di massa– utilizzo di un algoritmo per risolvere problemi simili

Proprietà dell'ALGORITMO

Classificazione degli algoritmi per forma di presentazione :

Verbale

Tabellare

Grafica (diagrammi a blocchi)

Software

Diagramma a blocchi – grafico prestazione algoritmo sotto forma di sequenza di blocchi funzionali interconnessi ( elementi grafici standard ), ognuno dei quali corrisponde all'esecuzione di una o più azioni.

Convenzioni fondamentali negli schemi a blocchi

Simbolo

Scopo del blocco

Inizio o fine dell'algoritmo

Ingresso o uscita dati.

All'interno del blocco, i dati sono elencati separati da virgole.

Processi.

La matematica è scritta all'interno del blocco. formule e operazioni per l'elaborazione dei dati.

Verifica della condizione.

Le condizioni logiche sono scritte all'interno del blocco. Ha due uscite Sì (+) e No (-).

Direzione.

Classificazione degli algoritmi per struttura:

Lineare (seguente)

Ramificato (ramo, scelta, alternativa)

Ciclo (ripeti)

Ausiliario

Combinato

Algoritmo lineare

Algoritmo lineare è un algoritmo i cui passaggi vengono eseguiti in sequenza uno dopo l'altro.

(Esempio: algoritmo di raccolta del portafoglio).

Struttura di base dell'algoritmo lineare:

Serie a squadre 1

Serie a squadre 2

Serie N della squadra

Compito

Calcola il perimetro di un triangolo arbitrario in base ai suoi tre lati.

Soluzione:

Fase 1: Formulazione del problema.

Dati iniziali: A, B, C – lati di un triangolo arbitrario

Produzione: P – perimetro del triangolo.

Fase 2: Modello matematico.

P=A+B+C

Fase 3: elaborazione di un algoritmo

Inizio

accedere

Conclusione

FINE

№ 1 E utilizzando il diagramma di flusso dell'algoritmo , calcolare il valore della funzione Y in X=2,

Inizio

ingresso: X

Z=8*X

• SOLUZIONE:

• X=2
• Z = 8 * 2 = 16
• Z = √16 = 4
• Z = 4 – 1 = 3
• Y = 3 * 2 = 6
• Y = 6 / 3 = 2

Z = Z - 1

Y=3*X

Y=Y/Z

uscita: Y

• Gli algoritmi possono descrivere i processi di trasformazione di un'ampia varietà di oggetti. La stessa parola "algoritmo" deriva da "algorithmi" - l'ortografia latina del nome dell'eccezionale matematico del IX secolo al-Khwarizmi, che formulò le regole per eseguire operazioni aritmetiche.
• Algoritmo- un insieme di comandi che descrivono l'ordine delle azioni dell'esecutore per ottenere il risultato di risolvere un problema in un numero finito di azioni.

Proprietà degli algoritmi:

1. Discretezza- L'algoritmo deve rappresentare il processo di risoluzione di un problema come l'esecuzione sequenziale di determinati semplici passaggi. In cui ogni passaggio dell'algoritmo richiede un tempo finito per essere completato, ovvero la trasformazione dei dati di origine in risultati viene effettuata in modo discreto nel tempo.

2. Determinismo (certezza). In ogni momento, la fase successiva del lavoro è determinata in modo univoco dallo stato del sistema. Pertanto, l'algoritmo produce lo stesso risultato (risposta) per gli stessi dati iniziali.

3. Chiarezza- L'algoritmo dovrebbe includere solo i comandi disponibili all'esecutore e inclusi nel suo sistema di comando.

4. Completezza (estremità)- con i dati iniziali correttamente specificati, l'algoritmo deve completare il suo lavoro e produrre un risultato in un numero finito di passaggi.

5. Carattere di massa (universalità). L'algoritmo deve essere applicabile a diversi insiemi di dati di input.

6. Efficacia- completamento dell'algoritmo con risultati certi.

Modi per scrivere algoritmi:

1. Metodo di registrazione verbale

Il modo verbale di scrivere gli algoritmi è una descrizione delle fasi successive dell'elaborazione dei dati. L'algoritmo è specificato in una presentazione arbitraria nel linguaggio naturale .

Esempio

Come esempio di un modo verbale di scrivere un algoritmo, considera un algoritmo per trovare l'area di un rettangolo

dove S è l'area del rettangolo; a, b – la lunghezza dei suoi lati.

Ovviamente a, b devono essere specificati in anticipo, altrimenti il ​​problema non si risolve.

Modi di scrivere algoritmi

Il modo verbale di scrivere l'algoritmo è simile al seguente:

• L'inizio dell'algoritmo.
• Impostare il valore numerico del lato a.
• Impostare il valore numerico del lato b.
• Calcola l'area S del rettangolo utilizzando la formula S=a*b.
• Emette il risultato dei calcoli.
• Fine dell'algoritmo.

Modi di scrivere algoritmi

2. Metodo grafico

Quando presentato graficamente, l'algoritmo viene rappresentato come una sequenza di blocchi funzionali interconnessi, ciascuno dei quali corrisponde all'esecuzione di una o più azioni.

Questa rappresentazione grafica è chiamata diagramma di flusso o diagramma di flusso. Nel diagramma di flusso, ogni tipo di azione (immissione dei dati iniziali, calcolo dei valori delle espressioni, verifica delle condizioni, controllo della ripetizione delle azioni, completamento dell'elaborazione, ecc.) corrisponde a una figura geometrica rappresentata come simbolo di un blocco. I simboli dei blocchi sono collegati da linee di transizione che determinano l'ordine in cui vengono eseguite le azioni. Di seguito sono riportati i simboli più comunemente utilizzati.

Modi di scrivere algoritmi

Elemento del diagramma di flusso

Nome

Blocco di calcolo (blocco computazionale)

Azioni computazionali o sequenza di azioni

Blocco logico (blocco condizione)

Blocco di ingresso/uscita dati

Scelta della direzione di esecuzione dell'algoritmo in base ad alcune condizioni

Designazione generale per l'input (output) dei dati (indipendentemente dal supporto fisico)

Inizio (fine)

Inizio o fine di un algoritmo, entrata o uscita in una subroutine

Modi di scrivere algoritmi

Elemento del diagramma di flusso

Nome

Processo utente (subroutine)

Calcolo utilizzando un programma standard o una subroutine

Blocco di modifica

La funzione esegue azioni che modificano i punti (ad esempio, l'intestazione del ciclo) dell'algoritmo

Connettore

Indicare il collegamento mediante linee spezzate tra flussi informativi

Modi di scrivere algoritmi

Esempio

Algoritmo per il calcolo dell'area di un rettangolo

Modi di scrivere algoritmi

3. Pseudocodici

descrizioni semi-formalizzate di algoritmi in un linguaggio algoritmico condizionale, inclusi sia elementi di un linguaggio di programmazione che frasi in linguaggio naturale, notazioni matematiche generalmente accettate, ecc.

Non esiste una definizione unica o formale di pseudocodice, quindi sono possibili vari pseudocodici, che differiscono nell'insieme delle parole funzione e nelle costruzioni di base (di base).

Modi di scrivere algoritmi

Esempio

• Inizio. Vai al punto 2.
• Immissione dei numeri a e b. Vai al punto 3.
• Calcola S=a*b. Vai al punto 4.
• Conclusione S. Vai al punto 5.
• FINE.

Modi di scrivere algoritmi

4. Metodo software

Registrazione dell'algoritmo nel linguaggio di programmazione selezionato.

Esempio

Writeln('');

Writeln('S=', S);

Tipi di algoritmi

1. Algoritmo lineare

Questo è un algoritmo in cui esiste solo una struttura successiva.

Seguente- Questa è la disposizione delle azioni una dopo l'altra.

Tipi di algoritmi

2. Algoritmo di ramificazione (se... allora... altrimenti...)

Questo è un algoritmo che ha una struttura ramificata.

Ramificazione- questa è la scelta dell'azione in base all'adempimento di alcune condizioni.

Tipi di algoritmi

3. Algoritmo ciclico

Questo è un algoritmo che ha una struttura ad anello.

Ciclo- Questa è la ripetizione ripetuta di qualsiasi azione.

Tipi di algoritmi

4. Algoritmo combinato

Un algoritmo che contiene più strutture contemporaneamente.

Larghezza del blocco px

Copia questo codice e incollalo sul tuo sito web

Didascalie delle diapositive:

Algoritmi e strutture dati Letteratura:

• D.Knut. L'arte della programmazione informatica. T. 1-3, M.: Mir, 1978, 1995, ecc.
• N. Wirth. Algoritmi e strutture dati. M.: Mir, 1989.

Concetto di tipo di dati

• Informazione che deve essere elaborato sul computer è astrazione, mostrando qualche frammento del mondo reale. Vale a dire, il frammento che è l'oggetto del problema da risolvere. Per risolverlo, prima costruiamo informativo, e nel caso generale matematico modello studiato argomento e ne viene selezionato uno esistente o ne viene costruito uno nuovo algoritmo risolvendo il problema.

• Informazioni sempre si materializza, è rappresentato nella forma messaggi. In generale, un messaggio ne rappresenta alcuni registrato segnale fisico . Segnale- Questo cambiamento nel tempo o nello spazio di qualche oggetto, in particolare, un parametro di una certa quantità fisica, ad esempio l'induzione del campo magnetico (quando si memorizzano informazioni, più precisamente messaggi su supporti magnetici) o il livello di tensione nel circuito elettrico (nei chip del processore o nella RAM).

• Discreto un messaggio è una sequenza segni(valori del segnale) da alcuni finale alfabeto(un insieme finito di valori dei parametri del segnale), in particolare, per un computer questo è una sequenza di caratteri dell'alfabeto binario, cioè una sequenza di bit.

• Dati informatici si tratta di messaggi discreti presentati in una forma utilizzabile da un computer, comprensibile al computer. Per un processore di computer, qualsiasi dato è non strutturato sequenza di bit (a volte viene usato il termine fluire bit).

• L'interpretazione specifica di questa sequenza dipende dal programma, da forme di presentazione e strutture dati, che sono selezionati programmatore. Questa scelta dipende in ultima analisi dal problema da risolvere e dalla comodità di eseguire azioni sui dati.

• Significati immediati Questo immutabile oggetti del programma che rappresentano se stessi: numeri (25, 1.34E-20), simboli ('A', '!'), stringhe ('Inserisci elementi della matrice');
• Costanti sono nomi assegnati a determinati valori (const pi=3.1415926).
• Variabili si tratta di oggetti che possono assumere un valore, salvarlo senza modificarlo e modificarlo quando vengono eseguite determinate azioni (var k:integer, x:real, a:array).
• Valori di espressione e funzione. Espressioni e funzioni sono regole per calcolare valori scritti in un certo modo: k*x+ sqrt(x).

• I dati nei programmi includono:

• Il tipo di dati è la caratteristica più importante che determina:

• insieme di valori validi;
• molte operazioni che possono essere eseguite su un valore;
• struttura del valore (scalare, vettoriale, ecc.);
• un metodo di rappresentazione meccanica del significato.

• Per visualizzare le caratteristiche della rappresentazione informatica di dati di varia natura in informatica, le discipline informatiche utilizzano le più importanti concetto di tipo di dati.

• Il tipo di costante, variabile o espressione può essere determinato da aspetto(dall'immagine) o dalla descrizione senza eseguire alcun calcolo.
• Qualsiasi operazione o funzione richiede argomenti e restituisce un risultato di un tipo molto specifico. I tipi di argomenti e i risultati delle operazioni sono determinati secondo regole ben definite del linguaggio.

• Principi di base del concetto di tipo di dati
• nei linguaggi di programmazione:

• Varietà di tipi e strutture di dati

• L'informatica utilizza un gran numero di metodi diversi tipi, vari strutture dati, per cui vengono utilizzati modellazione oggetti incontrati nei problemi in esame.

• Se la struttura di un determinato algoritmo non cambia durante l'esecuzione, viene presa in considerazione tale struttura statico , Strutture dati statiche esistere invariato durante tutto il tempo di esecuzione dell'algoritmo.

• Senso scalare(semplice, atomico) tipologia presentata liscio uno componente (esempio: tempo, temperatura).

• Strutture dinamiche vengono creati, modificati e distrutti come necessario in qualsiasi momento durante l'esecuzione dell'algoritmo.

• Senso strutturato(composito) tipologia presentata Di più Come uno componente (esempio: vettore, matrice, tabella, ecc.).

• Esistono tipi predefiniti (predefiniti): standard e definiti dal programma. Per standard i tipi nella descrizione di un linguaggio di programmazione specificano tutte le sue caratteristiche: un insieme di valori, un insieme di operazioni, struttura e rappresentazione macchina di un valore. Per appena definito tipi, il linguaggio fornisce un meccanismo per specificare un insieme di valori in un programma e la struttura del valore. Di solito un nuovo tipo viene costruito sulla base di quelli standard esistenti. Pertanto, molte operazioni e la rappresentazione macchina di tali tipi sono fissate nella descrizione del linguaggio.

• tipi scalari (semplici, atomici):
• Totale;
• vero;
• logico (booleano);
• simbolico;
• tipi strutturati (compositi):
• vettore;
• registrazione;
• file(sequenza);
• un mucchio di;
• tipo di oggetto (classe);
• tutte le possibili combinazioni di tipi scalari e strutturati;
• tipologia di riferimento.

• Tipi statici (strutture dati)

• I tipi scalari predefiniti più comunemente utilizzati sono: intero ( numero intero), vero ( vero), simbolico ( car), booleano( booleano).

• Valori interi esatti. Esempi: 73, -98, 5, 19674.
• Rappresentazione della macchina: formato in virgola fissa. L'intervallo di valori è determinato dalla lunghezza del campo. Operazioni: +, -, *, div, mod,=,<, и т.д.

• Tipo numero intero

• Approssimazioni non intere. Esempi: 0,195, -91,84, 5,0
• Rappresentazione macchina: formato in virgola mobile. L'intervallo e la precisione dei valori sono determinati dalla lunghezza del campo. Operazioni: +, -, *, /, =,<, и т.д.

• Tipo vero

• Caratteri di testo singoli. Esempi: 'a', '!', '5'.
• Rappresentazione della macchina: formato ASCII. L'insieme di valori è determinato dalla tabella dei codici e dalle funzionalità della tastiera. Operazioni: +, =,<, и т.д.

• Tipo car

• Due valori booleani falso e vero. Inoltre, falso
• Rappresentazione macchina ─ valore zero e un bit: falso è codificato 0, vero ─ 1. Operazioni: , , , =,< и т.д.

• Tipo booleano

• Meccanismi di base per la costruzione di nuovi tipi scalari discreti: enumerazione, restrizione. In definizione trasferibile tipi, un elenco di tutti i valori possibili è fisso, molte operazioni sono definite in anticipo nel linguaggio. In definizione limitato tipi come insieme di valori validi è fisso sottoinsieme un insieme di valori di tipo discreto, che in questo caso è chiamato tipo base rispetto a quello definito.

• Esistono tipi scalari discreti e continui. Significati multipli discreto tipo finito o numerabile. Significati multipli continuo tipo più che numerabile. I tipi standard discreti includono intero, carattere e logico. I tipi standard continui includono real.

• I tipi strutturati (compositi) sono caratterizzati da: il numero e il possibile tipo di componenti di valore, nonché il modo in cui si accede a una singola componente di valore.

• Di solito vengono chiamate strutture simili ai vettori e alle matrici in informatica matrici. Tutti gli elementi dell'array devono essere preciso identico tipo.

• Tipo array o normale

• Per accedere (fare riferimento a) un singolo elemento dell'array vengono utilizzati uno o più indici (w; w; A). Gli indici possono essere espressioni i cui valori possono variare arbitrariamente entro limiti predefiniti. Pertanto, dicono che gli elementi dell'array hanno accesso diretto.

• Vengono chiamate strutture simili alle righe della tabella record. I componenti dei record vengono solitamente chiamati campi. Possono essere vari campi (colonne della tabella). diverso tipi. Per accedere ai singoli campi di un record, questi sono fissi e immutabili nomi. Per esempio: Giornata della vittoria. Mese:= maggio. I campi possono essere selezionati per l'elaborazione in qualsiasi ordine, quindi si dice che lo sia l'accesso ai componenti del record Dritto.

• Tipo record o combinato

• Giornata della vittoria:

• File (sequenza)

• La struttura dati principale utilizzata per archiviare informazioni su dispositivi esterni (dischi magnetici, nastri, ecc.) è File O sequenze. Il file viene considerato sempre presente sul dispositivo esterno. In questo caso il numero dei componenti del file è sconosciuto; tutti i componenti devono essere dello stesso tipo. Accesso ai componenti ─ coerente.

• Il volo di Gagarin:

• Un mucchio di

• In molti problemi matematici e informativi è necessario utilizzare direttamente o indirettamente l'oggetto matematico principale imposta. Il tipo di dati corrispondente a un insieme è per definizione strutturato, poiché nel caso generale un insieme può essere costituito da più di un elemento e allo stesso tempo le operazioni devono essere eseguite con tutti gli elementi dell'insieme come un unico insieme. Il numero di elementi in un set non è determinato in anticipo e nel tempo potrebbe cambiare. Tutti gli elementi del set devono essere dello stesso tipo. Accesso ai singoli elementi dell'insieme NO. Puoi solo scoprire se un elemento appartiene o meno a un insieme, includere un elemento nell'insieme o escluderlo dall'insieme. Sono inoltre previste operazioni standard sugli insiemi: unione, intersezione, sottrazione, ecc.

• X1X5X4

• Strutture dati dinamiche

• Dati con struttura dinamica nel tempo i cambiamenti se stessa struttura e non solo il numero di elementi, come file o sequenze. Le strutture dati dinamiche di base sono:

• un oggetto;
• elenco lineare;
• albero;
• grafico.

• In un elenco lineare ogni elemento è correlato a quello precedente. Per una lista lineare, sappiamo quale elemento si trova all'inizio della lista, quale alla fine e anche quale elemento viene prima di quello corrente. In un elenco lineare è possibile spostarsi dall'elemento corrente a quello successivo solo utilizzando le connessioni specificate tra gli elementi vicini.

• Elenco lineare

• In generale si ottiene una catena di elementi in cui è possibile effettuare la ricerca, in cui è possibile inserire elementi o escluderli.

• Molti altri tipi di strutture dinamiche sono organizzate sulla base di un elenco lineare. Questo è in particolare: anelli, code, mazzi E pile.

• Struttura ad anello

• La differenza tra un anello e una lista lineare è che un anello ha una connessione tra l'ultimo elemento della lista e il suo primo elemento.

• Per una lista lineare e un anello è possibile l'accesso a qualsiasi elemento della struttura. Per fare ciò, è necessario spostarsi in sequenza da un elemento all'altro. In molte situazioni del mondo reale, tale accesso assente. Puoi interagire solo con il primo e l'ultimo elemento, oppure solo con uno di essi. Code, mazzi e pile vengono utilizzati per modellare tali oggetti.

• Struttura della coda

• La fine della coda è disponibile per l'inclusione e l'inizio è disponibile per l'esclusione (selezione). L'elemento arrivato prima nella coda e sottoposto a manutenzione per primo. Dicono che la coda è una struttura con disciplina di servizio FIFO (F primo IO N, F primo O ut) ─ “il primo a venire, il primo ad andare”.

• Struttura del ponte

• Il mazzo ha entrambe le estremità disponibili, sia per l'inclusione che per il campionamento. Quindi, possiamo dire che Dec ─ lo è coda bidirezionale.

• Struttura dello stack

• Una pila ha solo un'estremità della struttura disponibile per l'interazione: la parte superiore della pila. Sia l'inclusione di un nuovo elemento nello stack che la selezione dell'ultimo elemento precedentemente incluso passano dalla parte superiore dello stack. Pertanto, l'articolo arrivato per ultimo viene elaborato per primo. Dicono che una catasta è una struttura con una disciplina di manutenzione LIFO (l ast IO N, F primo O ut) ─ “ultimo a venire, primo a partire”.

• GRAZIE PER L'ATTENZIONE!

Strutture di base degli algoritmi Imponiamo alcune restrizioni
struttura del diagramma di flusso.
Costruiremo un algoritmo utilizzando solo
tre frammenti di un certo
configurazioni.
Chiamiamole strutture di base
algoritmi.

La prima struttura di base è la seguente
è costituito da una catena di blocchi senza
ramificazioni.

Ramificazione

SÌ
NO
condizione

Un caso particolare di ramificazione
condizione

La ramificazione viene utilizzata nei casi in cui
quando devi sceglierne uno
due modi per risolvere il problema.

Ciclo

Il ciclo viene utilizzato nei casi in cui
per risolvere il problema è necessario
ripetere le stesse cose più e più volte
Azioni.

Ciclo con postcondizione

Ciclo con precondizione

Ciclo parametrico

Ciclo parametrico controllato
parametro.
Un parametro di loop è una variabile
che cambia monotonicamente nel ciclo,
e il criterio di uscita dipende da questo
ciclo.

io:= dentro
Corpo
ciclo
io:= io+di
NO
SÌ
io > non lo so

io:=in
io>ik
Corpo
ciclo
i:=i+di

Progettazione di algoritmi complessi

Metodo di progettazione dell'algoritmo top-down

Il metodo consiste nei seguenti passaggi:
l'attività originale è divisa in sottoattività,
collegato da qualche algoritmo;
è in corso il debug di questo algoritmo;
ogni sottoattività è considerata come
compito;
il processo continua fino a quando
l'attività originale non sarà completamente
risolto.

Esempio

Data l'equazione ax2 + bx + c = 0 e la funzione
f(x).
Se un'equazione ha due reali
radici x1 e x2, crea una tabella di valori
funzione sul segmento costituito da n
punti.

Algoritmo di primo livello
Ingresso a,b,c
Soluzione
equazioni
NO
x1,x2
trovato
SÌ
Inserisci n
Costruzione
tavoli
Non c'è alcuna decisione
FERMARE

Algoritmo che implementa la soluzione del sottoproblema
equazione quadrata
d:=b2 – 4ac
NO
D>0
SÌ
X1=(- b + √ d)/2/a
X2= (- b - √ d)/2/a

Algoritmo per costruire una tabella di valori
funzioni
h=(x2-x1)/(n-1)
x = x1
io=1
Uscita x, f(x)
x=x+h
io = io+1
SÌ
NO
i>n

Quindi, la soluzione al problema
il problema consiste in un algoritmo superiore
livello e due sottoattività.
Algoritmo che collega le sottoattività
Soluzione
equazioni
Costruzione
tabelle f(x)