DIARIO DELLE LEZIONI ANNI PRECEDENTI
A.A. 2023/2024
Lunedì 26 Febbraio 2024 - Lezioni 1-2 Introduzione- Informazioni sul corso.
- Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale; di problem solving e di problema computazionale.
- Definizione e significato degli insiemi O, Ω e Θ
- Algebra della notazione asintotica
- Metodo del limite
- Esempi
- 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 svolti
- ricerca sequenziale e suo costo computazionale nel caso migliore, peggiore e medio
- ricerca binaria e suo costo computazionale nel caso migliore, peggiore e medio
- funzioni matematiche ricorsive
- algoritmi ricorsivi
- fattoriale: pseudocodice iterativo e ricorsivo;
- ricerca sequenziale: pseudocodice ricorsivo;
- ricerca binaria: pseudocodice ricorsivo;
- equazione di ricorrenza degli algoritmi ricorsivi già visti (fattoriale; ricerca sequenziale; ricerca binaria; numeri di Fibonacci)
- esempi di algoritmi ricorsivi (potenza di n alla k, somma degli elementi di un array, minimo in un array, array palindromo): pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza.
- esempi di algoritmi ricorsivi (stampa dei valori in un array, Torri di Hanoi): pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;
- metodi risolutivi (1):
- metodo iterativo
- metodo di sostituzione;
- metodo dell'albero.
- metodi risolutivi (2):
- metodo principale
- esempi di soluzione di equazioni di ricorrenza (1)
- esempi di soluzione di equazioni di ricorrenza (2)
- algoritmi naif: insertion sort, selection sort, bubble sort; calcolo del costo computazionale;
- esempi di soluzione di equazioni di ricorrenza (3)
- albero delle decisioni e teorema sulla limitazione inferiore per il costo computazionale di un algoritmo per confronti
- algoritmi efficienti (1):
- paradigma del Divide et Impera
- merge sort (pseudocodice e costo computazionale, pseudocodice della funzione Fondi)
- problematica dell'ordinamento in loco: una parentesi sull'uso della memoria secondaria
- quick sort (idea e pseudocodice, costo computazionale nei casi migliore e peggiore)
- pseudocodice della funzione Partiziona
- un esercizio svolto: Tim Sort (Merge Sort + Insertion Sort per il caso base)
- algoritmi efficienti (2):
- quick sort (costo computazionale nel caso medio, randomizzazione)
- algoritmi efficienti (3):
- heap sort: struttura dati heap; Heapify (pseudocodice e costo computazionale) e BuildHeap (pseudocodice)
- Heap sort (pseudocodice e costo computazionale)
- algoritmi lineari
- counting sort (versione semplificata e versione completa)
- bucket sort (idea)
- strutture dati ed insiemi dinamici
- confronto tra array qualunque e array ordinato
- liste puntate
- introduzione alle liste concatenate: ricerca e inserimento in testa
- cancellazione nelle liste concatenate
- pila
- le operazioni Push e Pop
- coda
- le operazioni enqueue e dequeue
- code con priorità
- Esercizio svolto: simulazione di una coda tramite due pile
- Esercizi svolti sulle liste
- alberi (1)
- definizione tramite la nozione di grafo
- caratterizzazione degli alberi
- memorizzazione degli alberi:
- tramite record e puntatori
- posizionale
- tramite vettore dei padri
- confronto delle tre memorizzazioni
- Ancora esercizi svolti sulle liste
- alberi (2) * visite di alberi: in-ordine, pre-ordine e post-ordine
-
- pseudocodice ricorsivo per memorizzazione con record e puntatori
- costo computazionale tramite equazione di ricorrenza e metodo di sostituzione
- esercizi che si risolvono utilizzando le visite: numero di nodi di un albero, ricerca in un albero
- pseudocodice ricorsivo per memorizzazione con vettore dei padri e costo computazionale
- visita per livelli
- esercizi svolti: calcolo dell'altezza e del numero di nodi ad un dato livello
-
- alberi (3)
- esercizi svolti: calcolo dell'altezza e del numero di nodi ad un dato livello; trasformazione da memorizzazione tramite vettore dei padri a notazione posizionale
- dizionari
- tabelle ad indirizzamento diretto
- tabelle hash
- collisioni
- liste di trabocco
- tabelle ad indirizzamento aperto
- tabelle hash
- hashing doppio
- Alberi binari di ricerca (ABR) (1):
- definizione e proprietà dell' "ordinamento orizzontale"
- algoritmo per la ricerca
- Alberi binari di ricerca (ABR) (2):
- 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
- Alberi binari di ricerca (ABR) (3):
- Esercizi svolti sugli ABR
- alberi bilanciati: alberi rosso-neri
- dimostrazione che gli alberi rosso-neri hanno altezza logaritmica
- rotazioni
- algoritmo di inserimento
A.A. 2022/2023
Lunedì 20 Febbraio 2023 - 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.
- Definizione e significato degli insiemi O, Ω e Θ
- Algebra della notazione asintotica
- Metodo del limite
- Esempi
- 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.
- 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
- Calcolare il costo computazionale del Selection, dell'Insertion Sort e del Bubble Sort (pseudocodice sulle slides)
- Esercizi svolti
- ricerca sequenziale e suo costo computazionale nel caso migliore, peggiore e medio
- ricerca binaria e suo costo computazionale nel caso migliore, peggiore e medio
- funzioni matematiche ricorsive
- algoritmi ricorsivi
- fattoriale: pseudocodice iterativo e ricorsivo;
- ricerca sequenziale: pseudocodice ricorsivo;
- ricerca binaria: pseudocodice ricorsivo;
- Progettare degli algoritmi che calcolino quanti elementi di un array appartengono all'intervallo chiuso [a,b] sotto varie ipotesi.
- equazione di ricorrenza degli algoritmi ricorsivi già visti (fattoriale; ricerca sequenziale; ricerca binaria; numeri di Fibonacci)
- esempi di algoritmi ricorsivi (potenza di n alla k, somma degli elementi di un vettore, minimo in un array, vettore palindromo, stampa dei valori in un array, Torri di Hanoi): pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;
- metodi risolutivi (1):
- metodo iterativo
- 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)
- metodi risolutivi (2):
- metodo di sostituzione;
- metodo dell'albero.
- Risolvere con i primi tre metodi alcune equazioni di ricorrenza assegnate
- metodi risolutivi (3):
- metodo principale
- esempi di soluzione di equazioni di ricorrenza (1)
- Risolvere con tutti i metodi alcune equazioni di ricorrenza assegnate
- esempi di soluzione di equazioni di ricorrenza (2)
- Risolvere alcune equazioni di ricorrenza assegnate
- algoritmi naif: insertion sort, selection sort, bubble sort; calcolo del costo computazionale;
- albero delle decisioni e teorema sulla limitazione inferiore per il costo computazionale di un algoritmo per confronti
- algoritmi efficienti (1):
- paradigma del Divide et Impera
- Calcolare il costo computazionale dell'algoritmo di Insertion Sort in cui la posizione dell'elemento da inserire viene determinata tramite ricerca binaria.
- Scrivere in pseudocodice una funzione che, dato un array A ed un indice j, calcoli il valore minimo nel sottoarray 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 l’array risulta ordinato (con l'aggiunta di una flag).
- Dato un array di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento
- algoritmi efficienti (2)
- 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
- quick sort (idea e pseudocodice)
- pseudocodice della funzione Partiziona
- un esercizio svolto: Tim Sort (Merge Sort + Insertion Sort per il caso base)
- Scrivere la funzione di fusione ricorsiva
- Scrivere Merge Sort iterativo
- quick sort (costo computazionale nei casi migliore e peggiore, costo computazionale nel caso medio, randomizzazione)
- heap sort: struttura dati heap; Heapify (pseudocodice e costo computazionale) e BuildHeap (pseudocodice)
- Sia dato un array di lunghezza n contenente solo valori 0 e 2. Si progetti un algoritmo con costo computazionale lineare che modifichi l'array 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 l'array contenga tutti elementi uguali.
- algoritmi efficienti:
- Build Heap (costo computazionale)
- Heap sort (pseudocodice e costo computazionale)
- algoritmi lineari
- counting sort (versione semplificata e versione completa)
- bucket sort (idea)
- Scrivere una funzione che restituisca il valore minimo di un HeapMax e calcolarne il costo computazionale
- Scrivere Heapsort sfruttando la struttura dati HeapMin
- Scrivere la funzione di inserimento in un HeapMax e calcolarne il costo computazionale
- strutture dati ed insiemi dinamici
- confronto tra array qualunque e array ordinato
- introduzione alle liste concatenate: ricerca e inserimento in testa
- cancellazione nelle liste concatenate
- vari esercizi di manipolazione delle liste.
- pila
- le operazioni Push e Pop
- code con priorità
- la struttura dati coda
- le operazioni enqueue e dequeue
- Esercizio svolto: simulazione di una coda tramite due pile
- Esercizio svolto: inserimento in una lista ordinata (versione iterativa e ricorsiva)
- scrivere lo pseudocodice delle funzioni Enqueue e Dequeue quando la coda sia circolare ed implementata su array
- scrivere lo pseudocodice delle funzioni Pop, Push e Pila_Piena quando la pila sia implementata su array
- Esercizi svolti sulle liste
- alberi (1)
- definizione tramite la nozione di grafo
- caratterizzazione degli alberi
- 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 per memorizzazione con record e puntatori
- costo computazionale tramite equazione di ricorrenza e metodo di sostituzione
- esercizi che si risolvono utilizzando le visite: numero di nodi di un albero, ricerca in un albero
- scrivere lo pseudocodice di una funzione che, dato un albero in notazione posizionale, lo restituisca tramite vettore dei padri
- scrivere lo pseudocodice di una funzione che, dato un albero tramite vettore dei padri, lo restituisca in notazione posizionale
- alberi (2)
- visite di alberi
- pseudocodice ricorsivo per memorizzazione con vettore dei padri e costo computazionale
- visita per livelli
- esercizi svolti: calcolo dell'altezza e del numero di nodi ad un dato livello; trasformazione da memorizzazione tramite vettore dei padri a notazione posizionale
- visite di alberi
- dizionari (1)
- tabelle ad indirizzamento diretto
- tabelle hash
- collisioni
- liste di trabocco
- tabelle ad indirizzamento aperto
- Pseudocodice iterativo della visita in preordine
- Strutture dati fondamentali (6)
- dizionari (2)
- tabelle hash
- hashing doppio
- tabelle hash
- dizionari (2)
- 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
- Strutture dati fondamentali (7)
- Alberi binari di ricerca (ABR) (2):
- Esercizi svolti sugli ABR
- alberi bilanciati: alberi rosso-neri
- dimostrazione che gli alberi rosso-neri hanno altezza logaritmica
- rotazioni
- algoritmo di inserimento
- Alberi binari di ricerca (ABR) (2):
Tiziana Calamoneri - 2024-02-27
Comments
Edit | Attach | Topic revision: r2 - 2025-03-03 - TizianaCalamoneri
Intro_algo/AD Web
Create New Topic
Index
Search
Changes
Notifications
Statistics
Preferences
- Algebra
- Algoritmi
- Architetture
- Basi di Dati
- Calcolo
- Metodi mat. per l'inf. (ex. Logica)
- Programmazione
- Reti
- Sistemi operativi
- Altri corsi
- Automi, Calcolabilità
e Complessità
- Apprendimento Automatico
- Economia Aziendale
- Elaborazione Immagini
- Fisica 2
- Grafica 3D
- Informatica Giuridica
- Laboratorio di Sistemi Interattivi
- Linguaggi di Programmazione 3° anno Matematica
- Linguaggi e Compilatori
- Sistemi Informativi
- Tecniche di Sicurezza dei Sistemi
- Automi, Calcolabilità
- Percorsi di studio
- Corsi
- Algoritmi Avanzati
- Algoritmica
- Algoritmi e Strutture Dati
- Algoritmi per le reti
- Architetture degli elaboratori 3
- Architetture avanzate e parallele
- Autonomous Networking
- Big Data Computing
- Business Intelligence
- Calcolo Intensivo
- Complessità
- Computer Systems and Programming
- Concurrent Systems
- Crittografia
- Elaborazione del Linguaggio Naturale
- Estrazione inf. dal web
- Fisica 3
- Gamification Lab
- Information Systems
- Ingegneria degli Algoritmi
- Interazione Multi Modale
- Metodi Formali per il Software
- Methods in Computer Science Education: Analysis
- Methods in Computer Science Education: Design
- Prestazioni dei Sistemi di Rete
- Prog. avanzata
- Internet of Things
- Sistemi Centrali
- Reti Wireless
- Sistemi Biometrici
- Sistemi Distribuiti
- Sistemi Informativi Geografici
- Sistemi operativi 3
- Tecniche di Sicurezza basate sui Linguaggi
- Teoria della
Dimostrazione
- Verifica del software
- Visione artificiale
- Algoritmi Avanzati
- Attività complementari
- Commissioni
- Corsi esterni
- Sistemi Operativi (Matematica)
- Perl e Bioperl
- ECDL
- Fondamenti 1
(NETTUNO)
- Tecniche della Programmazione 1° modulo
(NETTUNO)
- Seminars in Artificial Intelligence and Robotics: Natural Language Processing
- Informatica generale
- Informatica
- Informatica per Statistica
- Laboratorio di Strumentazione Elettronica e Informatica
- Sistemi Operativi (Matematica)
- Progetti
Site map
AA web
More...
RSS Feed
Account 
 |
 |
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica 
|
|
|
|
Copyright © 2008-2025 by the contributing authors. All material on this collaboration platform is the property of the contributing authors. Ideas, requests, problems regarding TWiki? Send feedback