Appunti di Fondamenti teorici e programmazione

Studio A

Fasi della programmazione

1. Algoritmo → Processo Risolutivo
2. Codifica

Linguaggio JS → Linguaggio

• Scritto
• Interpretato

Interpretazione

Istruzioni

• Semplici → writeLN → Invocazione, sposta il cursore
• Composte → Non terminano → Contengono
• Script = Un Lavoro per ottenere programmi eseguibili all'interno di altri programmi.

Costanti

• Stringhe → Insieme di Caratteri
• Concatenare 2 Stringhe "2" + "3" = "23"
• Numeri
• Booleani: 0 = Falso
• Operatori di confronto

Funzioni

• Function → Indirizza Funzione
• Return = Chiave e ciò che esegue
• Argomenti = Parametri formali
• Invocazione = Parametri attuali

Programma = Nel linguaggio di programmazione il programma è una funzione che ha come argomento i dati digitali in input e opportunamente convertiti.

Studio A

Fasi della programmazione

• Algoritmo = processo risolutivo

• Codifica

• Compilazione

Linguaggio OS

• Linguaggio

Scrpt

Linguaggio che permette di utilizzare script

istruzioni che si interpretano al momento dell'esecuzione di programma

• Operazione a segno terminale

• Operazione in ordine

Istruzioni

• Semplici

• WRITEIN = invocazione, sposta il cursore

• Composte = non terminano

• x ferma con

Script = un linguaggio per ottenere programmi eseguibili all'interno di altri programmi

Costanti

• Stringhe = insieme di caratteri

• Concatenazione

• Con + concateno 2 stringhe "2" + "3" = "23"

Numeri

• Lazj

Booleani

• 0 = false, 1 = true

• Letterali logici

• Booleani

• true = false

Operatori di confronto

• Stringhe =

• "abeto" > "abate"

• 121 > 12

Function

• Individua funzione

Funzioni

• return = è una parola chiave e ciò che esegue è l'espressione

• il cui valore è il risultato della funzione

Argomenti = parametri formali

Invocazione = parametri attuali

Programma = nel linguaggio di programmazione il programma è una funzione

che ha come argomenti, dati digitati in INPUT e opportunamente convertiti.

Variabili

Permettono di introdurre dei nomi simbolici a cui sono associati dei valori. Il valore associato ad una variabile può cambiare durante l'esecuzione.

• Var: serve ad identificare
• 3 Proprietà
  • Valore: valore associato
  • Locazione di memoria: in cui il valore è memorizzato
  • Tipo

Note ➔ Identificatore ➔ sequenza di lettere cifre e caratteri speciali / lettere minuscole e maiuscole distinte

Dichiarazioni di variabili

Sintassi:

• Var identificatore = espressione

In OS non è necessario inizializzare le variabili ➔ var x ➔ NaN

Stato

• Ambiente : insieme di variabili e funzioni.
• Specifica di un problema consiste nella definizione di uno stato iniziale (assenza dati) e di uno stato finale.
• Costituito dal contenuto delle locazioni.

Assegnamento

• Sintassi: identificatore = espressione
• Semantica: modifica nello stato risultante del valore della variabile di nome (identificatore) dando il valore espressione.

Prossima

Serie di istruzioni che fanno riferimento allo stato corrente delle "macchine".

NaN

= NaN ➔ false | NaN => false | !NaN=true

Condizionali

7 Bovegna

Sintassi:

if (ESPR) ISTR-1; -> GOTO THEN else ISTR-2

Semantica:

Viene valutata ESPR, se è vera eseguita ISTR-1, sennò ISTR-2

Sintassi:

if (ESPR) ISTR-1

Semantica:

Valutata ESPR, se è vera ISTR-1 sennò non fa nulla.

Ambiguità -> un else else si sempre riferimata all'if più vicino. Però a riffera ad un if incassata bisogna mettere quest'ultimo in blocco.

if [a>0] { if [b>0] ISTR-1; } else ISTR-2;

Approcci

• Top-Down -> si parte dell'altro camolodica il problema nel suo insieme.
• Bottom-Up -> si ci scopo al nucleare singite fitri sensa avere una umona.

Definizione di Funzione

• Predicate -> funzione che restituisce un valore booleanno
• Anonime -> funzione sensa uname

Sintassi: Intestazione Blocco

Invocazione

Sintassi: identificatore (parametri attuati) corrispondono ai parametri forali

Return (return ESPR-1) questa diviene la veste cap tecaricare i valori puboli dalla funzione die puturen ed alimentate:

• dichito del valor di esperienza
• azione del castrello alla funzione alimontate -> return fa finira la funzione

ITERAZIONI CHE ESEGUONO AZIONI PIÙ VOLTE

DETERMINATE

WHILE

SINTASSI:

var ident = espr;while (espressione) { istruzioni } corpo

SEMANTICA:

• SI VALUTA ESPR
• VERA SI ESEGUE ISTR -
• FALSA NON CALCOLA

FOR

SINTASSI:

for (ESPR-1, ISTR-1, ESPR-2)for (ISTR-1; ESPR-1; ESPR-2)ISTRUZIONE

• ISTR-1: inizializza la variabile di controllo
• ESPR-1: verifica di fine ciclo
• ESPR/ISTR-2: incremento la variabile
• ISTRUZIONE: corpo

INDETERMINATE

ESEMPIO

function LeggiSommatore(n){ var x = Readnum1();if x==n return 0;else return x + LeggiSommatore(n);}

DO-WHILE

• SIMILE AL WHILE, MA LA CONDIZIONE VIENE CONTROLLATA ALLA FINE DI OGNI CICLO.

SINTASSI:

do ISTRwhile (espressione);

SEMANTICA

ISTRUZIONE

while(ESPR.)

ISTRUZIONE

SWITCH

SINTASSI

switch (ESPR.)

• case espressione-1: istruzioni-1break;
• case espressione-n: istruzioni-nbreak;
• default: istruzioni-default;

SEMANTICA

1. Viene calcolata espr. ottenendo un valore V
2. Vengono esaminate le varie espressioni e il valore è uguale a V e segue la istruzione corrispondente.
3. Se una di esse è non comparabile si esegue esegue default

N.B. → se non è presente break si eseguono in ordine le varie istruzioni.

break può essere sostituito da return

variabili globali → esterne alla funzione

nascoosta → da una locale alla stessa, non accessibile.

locali → interne alla funzione, visibili solo a certe parti del programma

ARRAY

Permette di rappresentare dati strutturati tipo matrice, tabella (ecc.) - composto da elementi

• ogni elemento è indicato da un numero unico
• il numero di elementi compone la lunghezza
• può diminuire, il loro numero di elementi è variabile

SINTASSI

• var nomeArray = []
• var nomeArray = new Array ();
• elementi separati dalla virgola
• vet[5] = elemento in posizione 5, è il 6° elemento
• vet[i] = i > 0 necessariamente

HEAP → luogo in cui sono memorizzati gli array.

REFERENCE → indirizzo di memoria che individua il luogo della heap in cui e memorizzato l'array.

CONFRONTO ARRAY → FALSE

nomeArray.length = lunghezza array

ORDINAMENTO A BOLLE → gli elementi più leggeri all'inizio

PROCEDURE

• grazie ai puntatori ed ai costruttori e le modifiche dello stato, di solito non contengono RETURN o se lo contengono esso non è seguito da un'espressione.
• ASTRAZIONE DI STROZZINI
• MODIFICHE SUL PARAMETRO FORMALE MODIFICANO IL PARAMETRO ATTUALE
• IN O.S le funzioni possono anche restituire array come risultato passando solamente lo sia dimensione.
• ARRAY VUOTO è ORDINATO × DEFINIZIONE E ANCHE L'ARRAY DI 1 ELEMENTO.
• nomeArray.splice (p,x)
• p → posizione
• x → valore inseriti al posto di quelli rimossi

* nomeArray.push(5), inserisce nell'ultima posizione 5.* nomeArray.pop(), rimuove l'ultimo elemento.

ARRAY MULTIDIMENSIONALI

* Array i cui elementi sono a loro volta array.* Si possono creare utilizzando un ciclo annidato:

Iniziare un elemento vuol dire inizializzare un array vuoto: es: m=new Array

ARRAY ASSOCIATIVI

* Indici sono stringhe, WRITE non stampa array associativi.

* Non è significativo l'ordine in cui sono posti gli elementi.

FOR-IN

Sintassi:

* Si può usare anche sugli altri tipi di array.

Semantica:

Modulo B

Grafo orientato → è una coppia (V, E) dove V è un insieme finito ed E una relazione binaria su V.

• V = insieme di nodi

E = insieme di archi (coppie V₁, V₂)

Grafo non orientato → sorgente e destinazione

• Cammino → insieme di archi e vertici
• Sentiero → vertici distinti
• Ciclo → dati un cammino (V₀, V₁, ..., V_k) se V₀ ≡ V_k = ciclo

Non orientato → se V₀ ≡ V_k, k > 3

Connesso → se per ogni coppia di vertici (u, v) “entra un cammino” da u a v

Fortemente connesso → grafo orientato

Albero libero → grafo non orientato connesso aciclico

• 2 vertici in V sono connessi da un cammino semplice

Proprietà

• Un qualunque arco rimosso da S causa albero dentro una foresta
• |E| = |V| - 1 → numero archi uguale n° vertici - 1
• E + 1 = grafo ciclico

Alberi radicati

• Albero libero in cui un vertice viene designato come radice dell'albero
• Altri vertici = nodi

• Preso un qualunque nodo vi in un albero la cui radice è vr esiste un cammino unico da (v_r, v_i1, v_i2, vk)

v_i e v_i2, vk = antenati di vk padre

v discendente dei nodi

- Nodi figli di uno stesso nodo = fratelli

- Nodi senza discendenti = nodi esterni

- Grado = nº figli

- Lunghezza cammino = profondità

- Altezza = lunghezza del cammino più lungo dalla radice al nodo

- Foglie: nodi che non hanno archi uscenti

- Frontiera: insieme delle foglie

Alberi

• Ordinati
  • Alberi in cui figli sono ordinati

  • _k+1 ∑_i=0 V_i Kⁿ⁺¹ -1

    n = ————— = ————

    nodi_est. K - 1

• Poisizionali

  • Alberi con di più 'k' posiz. in cui ogni figlio ha una posizione

  • Binari → ogni nodo ha al più 2 figli

Bin. indistinta

• Base
  • Alberi vuoti che non contengono nodi
• Passo induttivo
  • Struttura
    • Nodo radice
      • Un figlio sinistro
      • Un figlio destro

Albero binario di ricerca

• Ad ogni nodo associate delle informazioni
• x ogni nodo
• Il figlio sinistro ha un valore che lo precede
• Il figlio destro ha un valore che segue

Ricerca → si confronta il valore del nodo con l'elemento e da viene e si opera ricorsivamente

LINGUAGGIO

• 3 CARATTERISTICHE
  • SINTASSI
  • SEMANTICA
  • PRAGMATICA

STRINGHE

insieme di caratteri

• OPERAZIONI
  • CONCATENAZIONE ⇒ ꓯS₁ S₂ = simboli di S₁ seguiti da S₂
  • LUNGHEZZA ⇒ numero di simboli
• INSIEMI ⇒ dati due insiemi A e B, X dice PRODOTTO CARTESIANO A x B, l'insieme di tutte le stringhe che si ottiene concatenando un elemento di A con uno di B.
  • A x B =
  • S₁ S₂ | S₁ Ɐ A S₂ Ɐ B
• PROPRIETÀ
  • A⁰ = { ε }
  • A¹ = A
  • Aⁿ⁺¹ = Aⁿ A^n-1
  • A^* = { e, A, aa, ... }
  • A⁺ = A, aa, aaa, ...

LINGUAGGIO

dati un alfabeto ∧ dice ∨ come l'insieme orale (insieme di) stringhe costruite da simboli di A

PER STABILIRE FRASI E STRINGHE APPARENTI SI USANO AUTOMI E GRAMMATICHE

DI PROGRAMMAZIONE

TRADOTTI IN LINGUAGGIO → COMPILATORI

TACCHINA

AUTOMI

strutture semplici che permettono di spiegare un concetto

• INSIEME DI STATI OFF/ON
• GRAFO ORIENTATO ETICHETTATO
  • TRANSIZIONI DI STATO SEGUITO DA PUSH
  • STATI, VERITA
  • TRANSIZIONI, ORACLE

LETTURA INPUT

• SIMPBOLO X CU ESISTE ARCO ⇒ CAMBIO STATO
• SIMPBOLO X CU NON ESISTE ARCO ⇒ FALLIMENTO

AUTOMA ⇒ QUINTUPLA (Λ, Σ, S, F, δ)

• Λ = insieme dei simboli, alfabeto del L
• Σ = insieme stati
• S∈Σ = stato iniziale
• F⊆Σ = sottoinsieme degli stati in cui l'automa si arresta
• δ⊂(Σ×Λ)×Σ = transizione relazione

RICONOSCIMENTO STRINGA

detto uuna coppia di (E, A) il con

• E = nodi i cui simboli a, aresta una e una solo coppia e giungli un solo elemento del cosi composizione

le ente ehe comincia dallo stato iniziale che troa finale tutti nodo lo

comportante se si simboli di E uguale alla stringa.

L(G)={t∈E ∧*T^h Accetto δ([t])

AUTOMA DETERMINISTICO ⇒specifiche unico total di deterministico

EQUIVALENTI⇒ ne riconoscenza che nome duplicaggio

ASSEGNAZIOA DETERMINISTICO (Λ, Σ_D, S_D, F_D, δ_D)

• S_D1 →<S₀₀₁
• E_D={S₁₁}⊆P(Σ_N ∧ S∩F≠∅)

operatori → algebra

ROMANTICA CONSOESPALA

• Λ → sistema ^{as sola presentano}

POSE DESCORSE

INSUORGO AZZDRAGA

SINTATIVA E IL L'ANGOIENG

CALCICATO ESMPRESSIONE

OPERBANTE IN DERATA A DESMA DRELA SITUAZIONE INEGLIA A SINTAVA IL SIMSSIM

GRATMATICA

REGOLARE

• VANTAGGI: permette linguaggi con un numero di passaggi infinito
• LIMITAZIONI:
  • NO RICORSIVITÀ
  • NO X LINGUAGGI PROGRAMMABILI
• DEFINISCONO UNA CLASSE DI LINGUAGGI INCLUSA NELLE GRAMMATICHE LIBERE

LIBERA

• + VERSATILITÀ: SEMPLICI, TEOFALLO? NON
• PIÙ POTENTE
• DEFINIZIONE:
  • G = , IN di una categoria A è
  • il insieme di simboli terminali
  • da produrre derivarsi da A
• Z(A) = α|α ∈Σ* ∧ A ⇒ ∗αβ

ADS

FORMATO DI PRODUZIONI DI GRAMMATICHE LIBERE

SE SI POSSONO COSTRUIRE PIÙ DI UN ADS

GRAMMATICA AMBIGUA

ANNO BISESTILE

function bisestile(anno)

MINPOS

function minPos(vet,from,to){

var min=from;

for(from++;from<to;from++){

• if(vet[from]<=vet[min]){ min=from; }

}

return min;

}

SEL SORT

function selSort(vet){

var temp,k;

for(i=0;i<vet.length;i++){

• k=minPos(vet,i,vet.length)
• temp=vet[i];
• vet[i]=vet[k];
• vet[k]=temp;

}

}

BUBBLE SORT

function BubbleSort(vet){

var temp,i,j;

for(i=0;i<vet.length-1;i++){

• for(j=vet.length-1;j>o;j--){
• if(vet[j]<vet[j-1]){
• temp=vet[j];
• vet[j]=vet[j-1];
• vet[j-1]=temp;
• }
• }
• }

}

RICERCA BIN

function ricercaBin(vet, x) {

var i=0; j=vet.length; trovato=false;

while(i < j && !trovato) {

med = Math.floor((i+j)/2);

if(vet[med] == x) trovato=true;

else if(vet[med] > x) j=med-1;

else i=med+1;

}

return trovato;

}

CERCA UN ELEMENTO IN UN ARRAY NEL MODO PIÙ RAPIDO

IN UN ARRAY ORDINATO

• Shift R
• Merge

SHIFT R

SPOSTA A DESTRA GLI ELEMENTI IN UN ARRAY

function shiftR(vet) {

var i;

for(i = vet.length; i > 0; i--) {

vet[i] = vet[i-1];

}

}

MERGE

function merge(a, b) {

var c = new Array(); i=0; j=0; k=0;

while(i < a.length && j < b.length) {

if(a[i] < b[j]) c[k] = a[i]; i++;

else c[k] = b[j]; j++;

k++;

}