Diario delle lezioni

A.A. 2018/2019

Lunedý 25 Febbraio 2019 - Lezioni 1-2

Introduzione sull'importanza della valutazione dei corsi di studio (a cura del presidente di CAD)

Introduzione (1)

  • Informazioni sul corso.
  • Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale; di problem solving e di problema computazionale.

Mercoledý 27 febbraio 2019 - Esercitazioni 1-2

  • TinyC. Codifica in TinyC del programma che calcola la somma iterando +1 [ D1, sezione 2 ]
  • Indagini su un programma iterativo [ L1, sez. 2.1 ]:
    • Precondizioni, Postcondizioni, invarianti di ciclo.
    • Terminazione di un ciclo: funzione di terminazione.
  • Esempi:
    • funzione che calcola la moltiplicazione. Uso della funzione somma nel calcolo del prodotto [ D1, sez. 3 ].
    • funzione che calcola il predecessore. Specifica come contratto.
    • funzione che calcola il minore o uguale.

  • Esercizi consigliati: Dispensa L1, sez. 2.5, esercizi da 2 a 8.
  • Sperimentazioni: Disp. D1, sez. 2.1.

Venerdý 1 Marzo 2019 - Lezioni 3-4

Introduzione (2)

  • Modello RAM; misura di costo uniforme e logaritmico.

Notazione asintotica (1)

  • Definizione e significato degli insiemi O, Ω e Θ
  • Metodo del limite
  • Algebra della notazione asintotica
  • Esempi

Esercizi assegnati:

  • Dimostrare le regole relative all'algebra della notazione asintotica che non sono state dimostrate a lezione
  • Calcolare l'ordine asintotico stretto di alcune funzioni assegnate.

Lunedý 4 Marzo 2019 - Lezioni 5-6

Notazione asintotica (2)

  • Pseudocodice
  • Valutazione del costo computazionale di un algoritmo
  • Un primo esempio
  • Esempi di problemi che si possono risolvere in modo pi¨ o meno efficiente e loro costo computazionale
    • somma dei primi n interi
    • valutazione di un polinomio in un punto

Il problema della ricerca (1)

  • ricerca sequenziale e suo costo computazionale nel caso migliore e peggiore
  • ricerca dicotomica e suo costo computazionale nel caso migiore e peggiore

Esercizi assegnati:

  • Calcolare il costo computazionale del Selection, dell'Insertion Sort e del Bubble Sort (pseudocodice sulle dispense)

Mercoledý 6 Marzo 2019 - Esercitazioni 3-4

  • Usando l'esempio del predecessore, revisione delle asserzioni logiche: precondizioni, postcondizioni, invarianti, funzioni di terminazione.
  • Progetto di funzioni a partire dalle specifiche logiche [ L1, sez. 2.3 ].
    • Esempio: divisione intera.
  • Uso di passaggi per riferimento per passare pi¨ risultati: funzione int divRef(int, int, int*, int*).
  • Utilizzo della funzione divRef nell'algoritmo mcdMaestra [ D1, sez. 4 ].

  • Esercizi consigliati: Dispensa L1, sez. 2.5, esercizi da 2 a 8.

Venerdý 8 Marzo 2019 Lezioni sospese per le Olimpiadi di Matematica (aule occupate)

Lunedý 11 marzo 2018 - Esercitazioni 5-6

  • Ancora sui passaggi per riferimento: funzione scambia(int*,int*)
  • Passaggio di parametri: call-by-value: impossibilitÓ di scrivere una funzione myAnd equivalente all'operatore && predefinito.
  • Call-by-value, funzione ap(int*,int*,int,int) (assegnamento parallelo Ó la Python) [ D2, sez. 2 ].
  • I problemi di alias: funzione scambia(int*,int*) senza variabile di appoggio [ D2, sez. 3 ].
  • Induzione e Ricorsione: definizione induttiva di + e funzione sommaRec(int, int) [ D3, sez. 1.1 ].
  • Esercizio: predecessore ricorsivo in TinyReC. Riflessioni sulla completezza computazioneale di TinyReC.
  • Ricorsione: funzione di Fibonacci. Efficienza e albero delle chiamate generato.

  • Esercizi consigliati: Dispensa D2 [sez. 4 ]
  • Esercizi consigliati: Dispensa D3 [sez. 1.3 ]

Mercoledý 13 Marzo 2019 - Lezioni 7-8

  • Calcolare l'andamento asintotico di alcune funzioni ed alcune sommatorie
  • Esempio pratico di funzionamento dei due algoritmi di ricerca
Ricorsione
  • ricerca sequenziale e binaria: pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;

Esercizi assegnati:

  • Progettare degli algoritmi ricorsivi ed esprimerli tramite pseudocodice che risolvano i seguenti problemi:
    • dato in input un vettore, visualizzare i suoi valori al contrario (dall'ultimo al primo)
    • dato un intero n, calcolare la somma di n valori immessi da tastiera (uno per ogni chiamata ricorsiva)
    • calcolare il MCD tra due interi positivi x ed y come segue:
      • sia y<x
      • se y=0 allora MCD(x,y)=y
      • altrimenti MCD(x,y))MCD(y, x%y) (dove x%y indica il resto della divisione intera tra x e y)

Venerdý 15 Marzo 2019 - Lezioni 9-10 Soluzioni delle equazioni di ricorrenza (1)

  • 4 metodi risolutivi (1/2):
    • metodo iterativo;
    • metodo di sostituzione;
    • metodo dell'albero.

Esercizi assegnati:

  • Calcolare la soluzione di alcune equazioni di ricorrenza

Lunedý 18 Marzo 2019 - Lezioni 11-12 Soluzioni delle equazioni di ricorrenza (2)

  • 4 metodi risolutivi (2/2):
    • metodo principale: enunciato del teorema senza dimostrazione
  • soluzione di alcune equazioni di ricorrenza

Esercizi assegnati:

  • Calcolare la soluzione di alcune equazioni di ricorrenza

Mercoledý 20 marzo 2019: Esercitazioni 7-8:

  • Esecuzione della funzione ricorsiva di Fibonacci: evoluzione della pila di sistema.
  • Iterazione e ricorsione: Fibonacci iterativo efficiente. Trasformazione sistematica di un ciclo in una funzione ricorsiva.
  • Dimostrazioni di correttezza per programmi ricorsivi. [ D3, sez. 2 ]
  • Problemi con soluzione inerentemente ricorsiva: il problema della Torre di Hanoi [ D3, sez. 3 ]
  • Soluzione di un esonero sul tema: il problema del massimo fattore primo [ S4 ]

* Esercizi consigliati: Dispensa 3 [sez. 2.4 e 3.3 ]

Venerdý 22 Marzo 2019 - Lezioni 13-14 Soluzioni delle equazioni di ricorrenza (3)

  • Esercizi riepilogativi sulle equazioni di ricorrenza

Esercizi assegnati:

  • Calcolare la soluzione di alcune equazioni di ricorrenza

Lunedý 25 Marzo 2019 - Lezioni 15-16

Il problema dell'ordinamento (1)

  • algoritmi naif: insertion sort, selection sort e bubble sort; calcolo del costo computazionale; algoritmi input sensitive
  • albero delle decisioni e teorema sulla limitazione inferiore per la complessitÓ di un algoritmo per confronti
  • paradigma del divide et impera

Esercizi assegnati:

  • Nell'algoritmo dell'insertion sort, la ricerca della posizione in cui inserire l'elemento corrente pu˛ essere effettuata tramite una ricerca binaria. Calcolare il costo computazionale dell'algoritmo cosý modificato.
  • Scrivere in pseudocodice una funzione che, dato un vettore A ed un indice j, calcoli il valore minimo nel sottovettore A[j..n]. Riscrivere lo pseudocodice del selection sort che utilizzi ripetutamente questa funzione.
  • Modificare l'algoritmo di Bubble Sort in modo che non prosegua la computazione se il vettore risulta ordinato (con l'aggiunta di una flag).
  • Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (prima versione).
  • Determinare l'albero delle decisioni del Selection Sort.

Anni Precedenti

alt="joomla visitor" >

Topic attachments
I Attachment History Action Size Date Who Comment
C source code filec coda.c r1 manage 1.5 K 2011-05-12 - 14:07 SimoneSilvestri  
Texttxt elemento_comune_vettori.txt r1 manage 0.4 K 2011-04-01 - 13:01 SimoneSilvestri  
C source code filec elimina_occorrenze.c r1 manage 2.0 K 2011-05-19 - 10:51 SimoneSilvestri  
C source code filec esempio1.c r1 manage 0.2 K 2011-03-15 - 10:25 SimoneSilvestri  
C source code filec fattoriale_iterativo.c r1 manage 0.3 K 2011-03-18 - 07:26 SimoneSilvestri Fattoriale iteraivo
C source code filec find_max_array.c r1 manage 0.6 K 2011-03-18 - 07:30 SimoneSilvestri  
C source code filec inserimento_ordinato.c r1 manage 1.0 K 2011-05-26 - 08:09 SimoneSilvestri  
C source code filec int_list.c r1 manage 0.8 K 2011-05-10 - 09:16 SimoneSilvestri  
C source code filec inverti_list.c r1 manage 1.5 K 2011-05-19 - 10:50 SimoneSilvestri  
C source code filec inverti_lista.c r1 manage 1.7 K 2011-05-12 - 14:09 SimoneSilvestri  
C source code filec liste_funzioni_ricorsive.c r1 manage 2.5 K 2011-05-26 - 08:09 SimoneSilvestri  
Texttxt minimo_vettore_ricorsivo.txt r1 manage 0.2 K 2011-03-31 - 11:05 SimoneSilvestri  
Texttxt occorrenze_vettore_ricorsivo.txt r1 manage 0.3 K 2011-04-01 - 13:00 SimoneSilvestri  
Texttxt palidromo_ricorsivo.txt r1 manage 0.4 K 2011-04-01 - 13:01 SimoneSilvestri  
C source code filec pila.c r1 manage 1.2 K 2011-05-12 - 14:07 SimoneSilvestri  
C source code filec pop.c r1 manage 0.2 K 2011-05-19 - 10:50 SimoneSilvestri  
C source code filec power_function.c r1 manage 0.4 K 2011-03-24 - 08:48 SimoneSilvestri  
C source code filec sum_positive_matrix.c r1 manage 0.7 K 2011-03-24 - 08:42 SimoneSilvestri  
Texttxt to_binary.txt r1 manage 0.2 K 2011-04-15 - 08:55 SimoneSilvestri  
Texttxt trova_vip.txt r1 manage 1.1 K 2011-04-15 - 08:55 SimoneSilvestri  
Texttxt trova_vip_lineare.txt r1 manage 0.8 K 2011-04-28 - 08:27 SimoneSilvestri  
Edit | Attach | Watch | Print version | History: r234 < r233 < r232 < r231 < r230 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r234 - 2019-03-25 - TizianaCalamoneri





 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback