Tags:
create new tag
view all tags

Diario delle lezioni

A.A. 2021/2022

Le lezioni di questo semestre sono in modalitÓ blended.

NOTA: le lezioni NON verranno registrate, ma trovate qui il dettaglio degli argomenti svolti ed il pdf delle slides utilizzate.

Martedý 23 Febbraio 2021 - Lezioni 1-2

Introduzione (1)

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

Slides

Giovedý 25 Febbraio 2021 - Lezioni 3-4-5

Notazione asintotica

  • Definizione e significato degli insiemi O, Ω e Θ
  • Algebra della notazione asintotica
  • Metodo del limite
  • 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.

Slides Corrette

Martedý 2 Marzo 2021 - Lezioni 6-7

Valutazione del costo computazionale

  • 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

Esercizi assegnati:

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

Slides

Giovedý 4 Marzo 2021 - Lezioni 8-9-10

Soluzione di alcuni esercizi sulla notazione asintotica

Il problema della ricerca

  • ricerca sequenziale e suo costo computazionale nel caso migliore, peggiore e medio
  • ricerca binaria e suo costo computazionale nel caso migliore, peggiore e medio

Esercizi assegnati:

  • Progettare degli algoritmi che calcolino quanti elementi di un vettore appartengono all'intervallo chiuso [a,b] sotto varie ipotesi.

Slides

Ricorsione (1)

  • funzioni matematiche ricorsive ed algoritmi ricorsivi
  • fattoriale: pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;
  • ricerca sequenziale: pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;

Slides

Martedý 9 Marzo 2021 - Lezioni 11-12

Ricorsione (2)

  • ricerca binaria: pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;
  • numeri di Fibonacci: pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;
  • esempi di algoritmi ricorsivi (potenza di n alla k, somma degli elementi di un vettore, minimo in un vettore, vettore palindromo, stampa dei valori in un vettore, Torri di Hanoi): pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;

Esercizi assegnati:

  • Progettare degli algoritmi ricorsivi ed esprimerli tramite pseudocodice che risolvano i seguenti problemi:
    • calcolare il coefficiente binomiale n sopra k;
    • 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)

Giovedý 11 Marzo 2021 - Lezioni 13-14-15

Soluzioni delle equazioni di ricorrenza (1)

  • metodi risolutivi (1):
    • metodo iterativo;
    • metodo di sostituzione.

Esercizi assegnati:

  • Risolvere con i primi due metodi alcune equazioni di ricorrenza assegnate

Martedý 16 Marzo 2021 - Lezioni 16-17

Soluzioni delle equazioni di ricorrenza (2)

  • metodi risolutivi (2):
    • metodo dell'albero
    • metodo principale
  • esempi di soluzione di equazioni di ricorrenza (1)

Esercizi assegnati:

  • Risolvere con i secondi due metodi alcune equazioni di ricorrenza assegnate

Slides corrette

Slides nuova versione

Giovedý 18 Marzo 2021 - Lezioni 18-19-20

Soluzioni delle equazioni di ricorrenza (3)

  • esempi di soluzione di equazioni di ricorrenza (2)

Il problema dell'ordinamento (1)

  • algoritmi naif: insertion sort, selection sort; calcolo del costo computazionale;

Esercizi assegnati:

  • 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.

Slides

Martedý 23 Marzo 2021 - Lezioni 21-22

Soluzioni delle equazioni di ricorrenza (4)

  • esempi di soluzione di equazioni di ricorrenza (3)

Il problema dell'ordinamento (2)

  • algoritmi naif: 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

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.
  • 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.

Giovedý 25 Marzo 2021 - Lezioni 23-24-25

Soluzioni delle equazioni di ricorrenza (5)

  • esempi di soluzione di equazioni di ricorrenza (4)

Il problema dell'ordinamento (3)

  • Un esercizio svolto
  • algoritmi efficienti:
    • paradigma del Divide et Impera
    • merge sort (pseudocodice e costo computazionale, pseudocodice della funzione Fondi, problematica dell'ordinamento in loco)
    • cosa non va nel merge sort: una parentesi sull'uso della memoria secondaria

Slides

Martedý 30 Marzo 2021 - Lezioni 26-27

Il problema dell'ordinamento (3)

  • Un esercizio svolto
  • algoritmi efficienti:
    • quick sort (idea)
    • quick sort (pseudocodice, pseudocodice e costo della funzione Partiziona, costo computazionale nei casi migliore e peggiore)

Esercizi assegnati:

  • Scrivere la funzione di fusione ricorsiva
  • Scrivere Merge Sort iterativo

Slides nuova versione

VACANZE PASQUALI: prossima lezione giovedý 8 aprile

Giovedý 8 Aprile 2021 - Lezioni 28-29-30

Il problema dell'ordinamento (4)

  • algoritmi efficienti:
    • quick sort (riflessioni sulla scelta del valore soglia, costo computazionale nei casi migliore e peggiore, costo computazionale nel caso medio)
    • heapsort (struttura dati heap; Heapify: pseudocodice e costo computazionale)

Esercizi assegnati:

  • Sia dato un vettore di lunghezza n contenente solo valori 0 e 2. Si progetti un algoritmo con costo computazionale lineare che modifichi il vettore in modo che tutte le occorrenze di 0 si trovino pi¨ a sinistra di tutte le occorrenze di 2.
  • Si considerino i valori 0 1 2 3 4 5 6 7. Si determini una permutazione di questi valori che generi il caso peggiore per l'algortimo Quick sort.
  • Calcolare il costo computazionale del Quick sort nel caso in cui il vettore contenga tutti elementi uguali.

Slides

Martedý 13 Aprile 2021 - Lezioni 31-32

Il problema dell'ordinamento (5)

  • algoritmi efficienti:
    • heapsort (Build Heap: pseudocodice e costo; Heapsort: pseudocodice e costo)
  • algoritmi lineari
    • counting sort (versione semplificata e versione completa)

svolgimento questionario OPIS

Esercizi assegnati:

  • Scrivere una funzione che restituisca il valore minimo di un HeapMax e calcolarne il costo computazionale
  • Scrivere Heapsort sfruttando la struttura dati HeapMin

Slides

Giovedý 15 Aprile 2021 - Lezioni 33-34-35

Il problema dell'ordinamento (6)

  • algoritmi lineari
    • bucket sort (idea)

Strutture dati fondamentali (1)

  • strutture dati ed insiemi dinamici
  • confronto tra vettore qualunque e vettore ordinato
  • introduzione alle liste: ricerca e inserimento in testa
  • cancellazione nelle liste, liste doppiamente puntate

Esercizi assegnati:

  • vari esercizi di manipolazione delle liste.

Slides

Martedý 20 Aprile 2021 - Lezioni 36-37

  • Strutture dati fondamentali (2)
    • pila
    • le operazioni Push e Pop
    • code con prioritÓ
    • la struttura dati coda
    • le operazioni enqueue e dequeue

Esercizi assegnati:

  • scrivere lo pseudocodice delle funzioni Enqueue e Dequeue quando la coda sia circolare ed implementata su vettore
  • scrivere lo pseudocodice delle funzioni Pop, Push e Pila_Piena quando la pila sia implementata su vettore.

Slides

Giovedý 22 Aprile 2021 - Lezioni 38-39-40

  • Strutture dati fondamentali (3)
    • Esercizio svolto: simulazione di una coda tramite due pile
    • Esercizi svolti sulle liste

    • alberi (1)
      • definizione tramite la nozione di grafo
      • caratterizzazione degli alberi

Slides

Slides

Martedý 27 Aprile 2021 - Lezioni 41-42

  • Strutture dati fondamentali (4)
    • alberi (2)
      • memorizzazione degli alberi:
        • tramite record e puntatori
        • posizionale
        • tramite vettore dei padri
        • confronto delle tre memorizzazioni * visite di alberi: in-ordine, pre-ordine e post-ordine
        • pseudocodice ricorsivo

Slides

Giovedý 29 Aprile 2021 - Lezioni 43-44-45

  • Strutture dati fondamentali (5)
    • alberi (3)
        • costo computazionale tramite equazione di ricorrenza e metodo di sostituzione
        • esercizi che si risolvono utilizzando le visite

Martedý 4 Maggio 2021 - Lezioni 46-47

  • Strutture dati fondamentali (6)
    • dizionari (1)
      • tabelle ad indirizzamento diretto
      • tabelle hash
        • collisioni
        • liste di trabocco
        • tabelle ad indirizzamento aperto e hashing doppio

Slides

Giovedý 6 Maggio 2021 - Lezioni 48-49-50

  • Strutture dati fondamentali (7)
    • Alberi binari di ricerca (ABR) (1):
      • definizione e proprietÓ dell' "ordinamento orizzontale"
      • algoritmo per il massimo e minimo
      • algoritmo per il successore e predecessore
      • algoritmo di inserimento
      • osservazioni sul costo computazionale delle operazioni viste come funzione dell'altezza
      • Esercizi svolti sugli ABR.

Slides

Martedý 11 Maggio 2021 - Lezioni 51-52

  • Strutture dati fondamentali (8)
    • Alberi binari di ricerca (ABR) (2):
      • Esercizi svolti sugli ABR.
      • alberi bilanciati: alberi rosso-neri (1)
        • dimostrazione che gli alberi rosso-neri hanno altezza logaritmica

Giovedý 13 Maggio 2021 - Lezioni 53-54-55

  • Strutture dati fondamentali (9)
    • Alberi binari di ricerca (ABR) (3):
      • alberi bilanciati: alberi rosso-neri (2)
        • rotazioni
        • algoritmo di inserimento
  • Esercizi svolti riepilogativi in preparazione dell'esame

Slides

Slides

Martedý 18 Maggio 2021 - Lezioni 56-57

  • Esercizi svolti riepilogativi in preparazione dell'esame

Martedý 25 Maggio 2021 - Lezioni 58-59

  • Esercizi svolti riepilogativi in preparazione dell'esame

Slides

Edit | Attach | Watch | Print version | History: r38 < r37 < r36 < r35 < r34 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r38 - 2021-05-24 - 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-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback