![Algoritmi-UniTrento](/img/default-banner.jpg)
- Видео 244
- Просмотров 419 807
Algoritmi-UniTrento
Италия
Добавлен 27 сен 2017
Lezioni del corso di Algoritmi e Strutture Dati dell'Università di Trento.
Lezioni registrate in aula dal 2017 al 2020. Lezioni registrate in studio a causa del coronavirus, nel 2020/21.
Lezioni registrate in aula dal 2017 al 2020. Lezioni registrate in studio a causa del coronavirus, nel 2020/21.
14 - Algoritmi greedy - Compressione di Huffman
Algoritmi e Strutture Dati - Università di Trento - a.a. 2020/21
30/03/2021 - Parte 7
Compressione di Huffman.
cricca.disi.unitn.it/montresor/teaching/asd/
30/03/2021 - Parte 7
Compressione di Huffman.
cricca.disi.unitn.it/montresor/teaching/asd/
Просмотров: 1 701
Видео
Algoritmi di ordinamento
Просмотров 1,5 тыс.3 года назад
Algoritmi e Strutture Dati - Università di Trento - a.a. 2020/21 25/05/2021 - Parte 4 Algoritmi di ordinamento cricca.disi.unitn.it/montresor/teaching/asd/
17 - Algoritmi probabilistici - Problema della selezione
Просмотров 5753 года назад
Algoritmi e Strutture Dati - Università di Trento - a.a. 2020/21 25/05/2021 - Parte 3 Algoritmi probabilistici - Problema della selezione cricca.disi.unitn.it/montresor/teaching/asd/
17 - Algoritmi probabilistici - Bloom Filter
Просмотров 3983 года назад
Algoritmi e Strutture Dati - Università di Trento - a.a. 2020/21 25/05/2021 - Parte 2 Algoritmi probabilistici - Bloom filter cricca.disi.unitn.it/montresor/teaching/asd/
17- Algoritmi probabilistici - Introduzione e primalità
Просмотров 4683 года назад
Algoritmi e Strutture Dati - Università di Trento - a.a. 2020/21 25/05/2021 - Parte 1 Algoritmi probabilistici - Introduzione e primalità cricca.disi.unitn.it/montresor/teaching/asd/
16 - Backtracking - Inviluppo convesso
Просмотров 4703 года назад
Algoritmi e Strutture Dati - Università di Trento - a.a. 2020/21 11/05/2021 - Parte 2 Backtracking - Inviluppo convesso (Convex Hull), algoritmo di Graham. cricca.disi.unitn.it/montresor/teaching/asd/
19 - Problemi intrattabili - Branch & Bound
Просмотров 2,8 тыс.3 года назад
Algoritmi e Strutture Dati - Università di Trento - a.a. 2020/21 11/05/2021 - Parte 1 Branch & Bound cricca.disi.unitn.it/montresor/teaching/asd/
19 - Problemi intrattabili - Tecniche euristiche
Просмотров 4883 года назад
Algoritmi e Strutture Dati - Università di Trento - a.a. 2020/21 04/05/2021 - Parte 3 Tecniche euristiche cricca.disi.unitn.it/montresor/teaching/asd/
19 - Problemi intrattabili - Tecniche di approssimazione.
Просмотров 5143 года назад
Algoritmi e Strutture Dati - Università di Trento - a.a. 2020/21 04/05/2021 - Parte 2 Tecniche di approssimazione. cricca.disi.unitn.it/montresor/teaching/asd/
19 - Problemi intrattabili - Algoritmi pseudo-polinomiali
Просмотров 6253 года назад
Algoritmi e Strutture Dati - Università di Trento - a.a. 2020/21 04/05/2021 - Parte 2 Algoritmi pseudo-polinomiali. cricca.disi.unitn.it/montresor/teaching/asd/
19 - Problemi intrattabili - Introduzione
Просмотров 4703 года назад
Algoritmi e Strutture Dati - Università di Trento - a.a. 2020/21 04/05/2021 - Parte 1 Introduzione alle tecniche risolutive per problemi intrattabili. cricca.disi.unitn.it/montresor/teaching/asd/
18 - NP-Completezza - Definizioni e teoremi
Просмотров 2,5 тыс.3 года назад
Algoritmi e Strutture Dati - Università di Trento - a.a. 2020/21 27/04/2021 - Parte 5 Breve introduzione alle classi P, NP, NP-complete cricca.disi.unitn.it/montresor/teaching/asd/
18 - NP-Completezza - Riduzioni fra problemi
Просмотров 1,3 тыс.3 года назад
Algoritmi e Strutture Dati - Università di Trento - a.a. 2020/21 27/04/2021 - Parte 4 Riduzioni polinomiali fra problemi. cricca.disi.unitn.it/montresor/teaching/asd/
18 - NP-Completezza - Introduzione
Просмотров 1 тыс.3 года назад
18 - NP-Completezza - Introduzione Algoritmi e Strutture Dati - Università di Trento - a.a. 2020/21 27/04/2021 - Parte 3 Introduzione alla teoria della NP-Completezza. cricca.disi.unitn.it/montresor/teaching/asd/
16 - Backtracking - Puzzle
Просмотров 5883 года назад
Algoritmi e Strutture Dati - Università di Trento - a.a. 2020/21 27/04/2021 - Parte 2 Applicazione dello schema generale di backtracking per risolvere problemi su giochi e puzzle quali sudoku, giro del cricca.disi.unitn.it/montresor/teaching/asd/
16 - Backtracking - Enumerazione dei sottoinsiemi di dimensione k
Просмотров 5373 года назад
16 - Backtracking - Enumerazione dei sottoinsiemi di dimensione k
16 - Backtracking - Problema delle n regine
Просмотров 1,1 тыс.3 года назад
16 - Backtracking - Problema delle n regine
16 - Backtracking - Enumerazione delle permutazioni
Просмотров 5823 года назад
16 - Backtracking - Enumerazione delle permutazioni
16 - Backtracking - Enumerazione dei sottoinsieme di un insieme
Просмотров 5653 года назад
16 - Backtracking - Enumerazione dei sottoinsieme di un insieme
15 - Ricerca locale - Dimostrazione ottimalità
Просмотров 7133 года назад
15 - Ricerca locale - Dimostrazione ottimalità
15 - Ricerca locale - Abbinamento grafi bipartiti
Просмотров 5473 года назад
15 - Ricerca locale - Abbinamento grafi bipartiti
15 - Ricerca locale - Complessità algoritmi di flusso
Просмотров 5803 года назад
15 - Ricerca locale - Complessità algoritmi di flusso
15 - Ricerca locale - Ford-Fulkerson - Versione Java
Просмотров 5193 года назад
15 - Ricerca locale - Ford-Fulkerson - Versione Java
15 - Ricerca locale - Ford-Fulkerson - Cammini aumentanti
Просмотров 4 тыс.3 года назад
15 - Ricerca locale - Ford-Fulkerson - Cammini aumentanti
15 - Ricerca locale - Ford-Fulkerson - Correttezza
Просмотров 6103 года назад
15 - Ricerca locale - Ford-Fulkerson - Correttezza
15 - Ricerca locale - Ford-Fulkerson - Schema generale
Просмотров 1,1 тыс.3 года назад
15 - Ricerca locale - Ford-Fulkerson - Schema generale
15 - Ricerca locale - Reti di flusso
Просмотров 2,1 тыс.3 года назад
15 - Ricerca locale - Reti di flusso
Nel caso 2 della removeNode(), non dovremmo fare "delete u" dopo le operazioni "link(...)" e "if u.parent == nil then ..." ? Siccome il nodo u, dopo le operazioni del caso 2 avrebbe comunque un riferimento verso uno dei nodi figlio che non è nil e quindi in teoria dovrebbe non permettere al garbage collector di liberare quella memoria. Sbaglio?
Uhm, è vero che manca la delete. Ho guardato la versione nel libro e cancella correttamente in tutti i casi, che però sono più "mischiati" e difficili da comprendere. Quando ho fatto questa versione, me lo sono dimenticato. Ho corretto le slide, il video ovviamente resta così. Grazie.
Salve, attorno al minuto 10:20 si vedono le regole per ricavare le informazioni in un vettore heap. Tuttavia mi sorge un dubbio. Se l'unico nodo di grado 1 ammesso fosse interno (ad esempio livello 2 su un albero di altezza 4), e al netto di errori commessi mi sembra che si possa costruire un albero del genere, le regole per la memorizzazione non perdono di validità? Purtroppo nel commento non è possibile inserire immagini, ma spero di aver reso l'idea. O forse, con il termine di "accatastato" per l'albero completo si intende proprio che una situazione del genere non è contemplata? Perché se sono tutti sulla sinistra allora effettivamente l'albero che ho descritto non è completo.
Bisogna considerare il combinato disposto delle varie regole: tutte le foglie sono a livello h o h-1 (con h altezza), le foglie sono accatastate a sinistra, al massimo un nodo di grado 1. Non mi pare che si riesca a generare un albero che non rispetti la memorizzazione se rispetto tutte e tre le regole.
@@albimontre Si, effettivamente non mi era chiaro il senso del termine "accatastato" nel contesto di questi alberi. Grazie mille
primo
Salve, non mi è chiaro il motivo per cui alla fine di tutta la trattazione risulta essere utile utilizzare una struttura come gli alberi RB. Ricade essenzialmente sul fatto che ricerca, inserimento e cancellazione sono efficienti rispetto ad altre strutture, ovvero sono tutti O(log n)? Inoltre, questa caratteristica è legata al fatto che, per come definiti, gli alberi RB sono ben bilanciati?
Un albero binari di ricerca non bilanciato può essere... sbilanciato, per l'appunto.Un albero in cui si inseriscono valori in ordine crescente genera un albero con solo nodi con figli sinistri, che corrisponde a una lista, quindi O(n). Le strane regole degli alberi RB garantiscono che l'albero abbia altezza O(log n) e questo garantisce l'efficenza. A parte, c'è il discorso che la tabelle hash sono più efficienti, ma perdono la struttura d'ordine. Quindi se si vuole efficienza e ordine, meglio gli alberi RB (per esempio utilizzati in TreeMap in Java).
Chiaro, grazie @@albimontre
il problema non dovrebbe essere diviso in parti uguali per essere un algoritmo divide et impera? così non è solo ricorsivo?
Copio questo dalla pagina su divide-et-impera (in inglese): The name "divide and conquer" is sometimes applied to algorithms that reduce each problem to only one sub-problem, such as the binary search algorithm for finding a record in a sorted list (or its analog in numerical computing, the bisection algorithm for root finding).[2] These algorithms can be implemented more efficiently than general divide-and-conquer algorithms; in particular, if they use tail recursion, they can be converted into simple loops. Under this broad definition, however, every algorithm that uses recursion or loops could be regarded as a "divide-and-conquer algorithm". Therefore, some authors consider that the name "divide and conquer" should be used only when each problem may generate two or more subproblems.[3] The name decrease and conquer has been proposed instead for the single-subproblem class. Quindi sì, volendo si potrebbe fare una distinzione, ma personalmente non trovo che sia importante.
Il secondo caso è intero superiore
complimenti per la spiegazione e grazie!
ma se non si capisce un cazzo
mi pensavo che era difficilissimo e invecie qua ho capito tutto. Grz pfor
minghia bottana finalmente me ne vado via da reggiocalabbbria
Spiegazione eccellente, grazie mille!
Complimenti, spiegazioni sempre chiare e soprattutto semplici, come soltanto una persona che ha capito l'argomento fino in fondo può fare, e non è affatto banale per un professore
Salve, prima di tutto volevo ringraziarla per queste lezioni, io non frequento l'università di Trento ma mi trovo veramente bene con le sue spiegazioni. Poi mi chiedevo, dalla slide del minuto 30:18 in poi, stiamo ipotizzando che T e U siano della stessa lunghezza, o sbaglio? Perché nel mio codice mi viene invece da inizializzarle con: for i = 0 to n: DP[i][0] = 0 for j = 0 to m: DP[0][j] = 0 Mentre nel suo (come dimostra la slide dopo) viene solo inizializzata la prima colonna (tutta) e poi la prima riga solo fino alla lunghezza di T, non di U, che potrebbe essere anche più lunga e andare fuori la memoria. O c'è qualcosa che non vedo?
Capita di sbagliare ;-) Nella versione attuale e nel video registrato durante la pandemia, è come dice lei: disi.unitn.it/~montreso/asd/slides/13-pd2.pdf ruclips.net/video/LL-yVCzOhoA/видео.html&ab_channel=Algoritmi-UniTN
@@albimontre grazie mille, avevo solo paura di essermi perso qualcosa. Sappi che mi sta salvando la carriera 😅
Fantastico, sto preparando un interview come Software eng e queste spiegazioni, sono una manna :)
Ottimo, ib bocca al lupo. Ci faccia sapere come è andata.
Idem anche io! Veramente ottime spiegazioni! Grazie prof
Sto seguendo con interesse questa lezione. Volevo segnalare che, nelle slide scaricabili, quando si parla di binary search viene indicato come algoritmo efficiente "2 log n". Mentre sulla slide di questo video c'è scritto solo "log n". Se possibile, vorrei capire qual è la versione corretta. Grazie mille
Siccome sto calcolando il numero *esatto* di confronti, il fattore 2 è corretto: per ogni chiamata, vengono fatti due confronti, uno per l'uguaglianza e uno per il <. Questa è una lezione vecchia, sono stato impreciso. Però dal punta di vista della complessità, alla fine è O(log n).
@@Algoritmi-UniTrento - ok, chiarissimo! Grazie mille
Ma quindi un DAG può avere solo un ordinamento topologico?
no
individuazione di tutti gli insiemi di archi di cardinalità minima la cui rimozione renda il grafo originale un DAG In questo esercizio con cardinalità si intende il numero di archi o di nodi? Come si potrebbe risolvere?
individuazione di tutti gli insiemi di archi di cardinalità minima la cui rimozione renda il grafo originale un DAG In questo esercizio con cardinalità si intende il numero di archi o di nodi? Come si potrebbe risolvere?
individuazione di tutti gli insiemi di archi di cardinalità minima la cui rimozione renda il grafo originale un DAG In questo esercizio con cardinalità si intende il numero di archi o di nodi? Come si potrebbe risolvere?
Molto chiaro, mi ha aiutato parecchio a far mente locale.
Professore ma queste slide le ha create lei?
Sì, in latex. Si trovano qui: cricca.disi.unitn.it/montresor/teaching/asd/
@@Algoritmi-UniTrento la ringrazio gentilissimo
Grazie mille! Bravissimo prof
Buonasera, al minuto 4:40, quando dell'interpretazione della notazione Theta in relazione alla valutazione di un problema computazionale, non ho ben compreso il motivo per cui nel problema dell'ordinamento di un vettore non ordinato abbiamo che la complessità e sia Omega di n che O grande di n. Nello specifico, per il caso in specifico, mi è chiaro il Theta di n (perchè come minimo devo guardare tutti gli elementi e non posso far meglio di così) ma non ho capito il motivo dell' O(n). E' possibile chiarire l'esempio?
Dal minuto 4.40 non parlo più di ordinamento, ma di ricerca in un vettore non ordinato - che è sia omega(n) che O(n). Fino a qualche secondo prima, dicevo che per l'ordinamento sappiamo che è Omega(n), ma non sappiamo se è O(n) - e ovviamente non lo è.
@@Algoritmi-UniTrento Buonasera si ha ragione, parlava della ricerca in un vettore ordinato, mi scuso per l'errore. Ecco non comprendo quando dice "che il problema è anche un O(n) perchè se li devo guardare tutti, li devo guardare uno dopo l'altro" ecco è questa affermazione che non riesco a capire nel giustificar l'O(n). può gentilmente chiarirmi questa parte? Grazie mille in anticipo. Alessandro
@@alessandromocci4933 In effetti, le mie parole, se le trascrive, non sono il massimo della chiarezza :-) Quando parliamo di problemi, se esiste un algoritmo che costa O(f(n)), allora il problema è O(f(n)). Man mano che troviamo algoritmi migliori, questo limite superiore scende. Ad esempio, nel caso dell'ordinamento abbiamo visto selection sort (il che ci dice che l'ordinamento è O(n^2)) e poi merge sort (il che ci dice che è O(n log n)). Entrambe le affermazioni sono vere, ma la seconda è più precisa. In lezioni più recenti uso questa analogia: io sono alto meno di 3 metri (vero), ma sono anche alto meno di 2 metri (vero e più preciso). Nel caso della ricerca in un vettore non ordinato, una soluzione possibile (in realtà l'unica ragionevole) scorre tutti gli elementi con un ciclo for (for i = 1 to n), quindi l'algoritmo è O(n), quindi il problema è O(n). E' possibile dimostrare che il problema è \Omega(n) - in quanto non essendo ordinato, se salto un valore quello potrebbe essere quello che cerco, quindi il problema è Theta(n).
Buonasera professore, ma la dimensione massima che devo cercare di coprire con io segmenti è data da "n", corretto?
No, è l'asse delle ascisse - se cerco di ottimizzare rispetto a n, questo è il problema dell'Insieme di Intervalli Indipendenti. Se diamo un peso ai segmenti, ottengo il problema dell'insieme degli intervalli indipendenti pesati. Se come peso uso la lunghezza dei segmenti, massimizzo la copertura dell'asse cartesiano.
Vedendo questo video sono finalmente riuscito a capire il merge Sort. Grazie professore!
Nel secondo esempio per c=13 n è minore di m perché radice cubica di 7 è 1.9 ed m=2
non ho capito il passaggio di a = 2 log a nel minuto 15:19 del video
Tutti i logaritmi in queste lezioni sono in base 2. Quindi 2^{\log a} (2 elevato alla potenza a cui bisogna elevare 2 per ottenere a) è... a. Questo poi mi serve per fare le semplificazioni successive e il cambiamento di base.
@@Algoritmi-UniTrento grazie infinite
Buongiorno Professore, vorrei sapere se esistono delle slide liberamente distribuibili del corso? Non faccio parte dell'ateneo ed anzi ho concluso il mio percorso di studi e sto concludendo quello di dottorato ma data la spiegazione estremamente chiara e ben fatta tornerebbero sicuramente utili delle slide. Grazie in anticipo.
Con un po' di ritardo, ecco qui: cricca.disi.unitn.it/montresor/teaching/asd/
Complimenti al prof, sono iscritto ad un'altra università ma queste lezioni sono utilissime.
Grazie.
Bellissima lezione, complimenti
Ottimo grazie per i contenuti davvero eccellenti
Grazie!
Qual'é il libro di riferimento per il questo corso di algoritmi e strutture dati?
Algoritmi e strutture di dati, Bertossi e Montresor, Città Studi Edizioni
complimenti per il corso
Grazie!
Ottima spiegazione.
Grazie!
è spiegato molto male
Kruskal : 28:46
Prim : 42:09
moa?coinquilino di nick?:D
Critica costruttiva: migliorare l'audio.
Le faccio i complimenti per l'ottima chiarezza espositiva e le sono grato moltissimo per aver deciso di condividere questo corso, ma per caso c'è qualche video che mi sono perso dove espone l'implementazione dei grafi tramite riferimenti a oggetti?
Grazie. I dettagli implementativi li facciamo in maniera molto "hands on" in laboratorio (con i tutor che girano fra i computer). Non registravamo perché sono pochi minuti di presentazione e poi si lavora. Ora, con il covid dovremo rivedere questa politica, ma non verrà fatto prima di ottobre-novembre, sorry.
@@Algoritmi-UniTrento non si preoccupi alla fine sono riuscito a sciogliere i miei dubbi, la ringrazio per la risposta rapidissima e le comunico che non vedo l'ora di finire questa sessione per gustarmi con calma i capitoli finali che da noi non siamo riusciti a trattare, buona serata
Per le implementazione c'è geeksforgeeks che le espone molto bene e in diversi linguaggi. Consiglio di fare qui la parte teorica e guarda da lì come implementare
non c eun video che si salvi
spiegazione approfondita e completa
non ce un video corso in italiano che si salvi
è un buon corso, sei tu che non capisci
@@corvo4708 🗿
32 : 54 passaggio di una formula 1 in fondo è da oscar xD.....senno,bellissimo corso,chiaro,complimenti al docente..
semplicemente grazie per aver postato queste lezioni , chiarissime e con ottime slides. complimenti al docente
grazie! fa piacere sentire che sono utili - specialmente in questo periodo
Ciao sto cercando dei partners matematici ed informatici che desiderino lavorare ad un progetto finanziario legato alle cryotovalute. Ho contatti con varie università ma io necessito di persone visionarie non di persone che guardano alla propria tasca a breve termine. I matematici mi servono per trovare degli algoritmi che approssimino l'andamento di processi stocastici normalizzati. Questo mi serve per modellare una distribuzione di probabilità da utilizzare nella costruzione di un portafoglio. Statisticamente vorrei costruire dei portafogli finanziari sulla base di condizionamenti legati alle probabilità future delle distribuzioni dei prezzi. una modellazione basata su condizionamenti Bayesiani. O se avete dei fisici interessati, legata ai movimenti Browniani. Questa roba può aiutarmi a farla solo chi ha una mente fresca evitandomi di tornare sui libri della mia università ormai vecchi ed obsoleti :) Se sei/siete interessati contattatemi.
Grazie, playlist veramente utile e ben fatta.
Complimenti, corso veramente ben fatto. Una curiosità: registrare i corsi è una direttiva della vostra Università e viene fatto sistematicamente, o invece è stata un'iniziativa isolata?
Grazie. E' un iniziativa personale, spiacente. Il sistema per registrarli è al momento abbastanza macchinoso, spero di riuscire a semplificare e proporlo ai colleghi.
cosa fa link()?
Scusami ma cosa intendi per "to" nel pseudocodice tu???? si dovrebbe partire da 0 ... Min prendere s[0] e poi partire da i=1 a mio parere...
Grazie tante per questi video. Una cosa ma i confronti se parto da i=2 e arrivo a n-1 nel caso del minimo non sono n-2 ?... oppure conta anche il confronto quando i diventa uguale a n e quindi esco dal ciclo for??
Esatto. Un ciclo for i = 2 to n-1 corrisponde a: i = 2 while i<= n-1 do i = i+1 Viene fatto anche l'ultimo confronto quindi sono n-1 confronti. Spero che questo risponda anche all'altra domanda.