{"id":45,"date":"2016-09-03T09:23:59","date_gmt":"2016-09-03T09:23:59","guid":{"rendered":"http:\/\/cricca.disi.unitn.it\/montresor\/?page_id=45"},"modified":"2025-06-06T17:03:43","modified_gmt":"2025-06-06T17:03:43","slug":"programma","status":"publish","type":"page","link":"http:\/\/cricca.disi.unitn.it\/montresor\/teaching\/asd\/programma\/","title":{"rendered":"Programma"},"content":{"rendered":"\n<h4 class=\"wp-block-heading\">Prima parte del programma \u2014 Prima prova parziale<\/h4>\n\n\n<p><b>Introduzione<\/b><\/p>\n<ul>\n<li>Cos\u2019\u00e8 un algoritmo<\/li>\n<li>Come descri\u00adve\u00adre gli algo\u00adrit\u00admi (pseu\u00addo\u00adco\u00addi\u00adce)<\/li>\n<li>Come valu\u00adta\u00adre gli algoritmi<\/li>\n<li>Algoritmi discus\u00adsi a lezione:&nbsp;<ul>\n<li>Ricerca del minimo<\/li>\n<li>Ricerca&nbsp;dico\u00adto\u00admi\u00adca<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>\n<b>Analisi degli algoritmi<\/b><\/p>\n<ul>\n<li>Modelli di calcolo<\/li>\n<li>Funzioni di&nbsp;costo<\/li>\n<li>Complessit\u00e0 algo\u00adrit\u00admi vs com\u00adples\u00adsi\u00adt\u00e0 problemi<\/li>\n<li>Limiti asin\u00adto\u00adti\u00adci supe\u00adrio\u00adri e inferiori<\/li>\n<li>Analisi di ricorrenze&nbsp;<ul>\n<li>Metodo di sostituzione<\/li>\n<li>Metodo del\u00adl\u2019al\u00adbe\u00adro di ricorrenza<\/li>\n<li>Metodo del\u00adl\u2019e\u00adsper\u00adto<\/li>\n<\/ul>\n<\/li>\n<li>Algoritmi discus\u00adsi a lezione:&nbsp;<ul>\n<li>Moltiplicazione di Karatsuba<\/li>\n<li>Selection Sort<\/li>\n<li>Insertion Sort<\/li>\n<li>Merge Sort<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>\n<b>Strutture dati astratte<\/b><\/p>\n<ul>\n<li>Sequenza<\/li>\n<li>Insiemi<\/li>\n<li>Dizionari<\/li>\n<li>Alberi e&nbsp;grafi<\/li>\n<li>Algoritmi discus\u00adsi a lezione:&nbsp;<ul>\n<li>Lista bidi\u00adre\u00adzio\u00adna\u00adle con\/senza sentinella<\/li>\n<li>Pila basa\u00adta su vettore<\/li>\n<li>Coda basa\u00adta su vet\u00adto\u00adre circolare<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>\n<b>Analisi ammor\u00adtiz\u00adza\u00adta<\/b><\/p>\n<ul>\n<li>Metodo del\u00adl\u2019ag\u00adgre\u00adga\u00adzio\u00adne<\/li>\n<li>Metodo del\u00adl\u2019am\u00admor\u00adta\u00admen\u00adto<\/li>\n<li>Metodo del potenziale<\/li>\n<li>Algoritmi discus\u00adsi a lezione:&nbsp;<ul>\n<li>Contatori bina\u00adri<\/li>\n<li>Vettori dina\u00admi\u00adci<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>\n<b>Alberi<\/b><\/p>\n<ul>\n<li>Definizioni<\/li>\n<li>Realizzazioni\n<ul>\n<li>Con vet\u00adto\u00adre dei&nbsp;figli<\/li>\n<li>Con padre\/primo figlio\/fratello<\/li>\n<li>Con vet\u00adto\u00adri dei&nbsp;padri<\/li>\n<li>Alberi bina\u00adri<\/li>\n<\/ul>\n<\/li>\n<li>Algoritmi discus\u00adsi a lezione:&nbsp;<ul>\n<li>Visita in profondit\u00e0<\/li>\n<li>Visita&nbsp;in ampiezza<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>\n<b>Alberi bina\u00adri di ricerca<\/b><\/p>\n<ul>\n<li>Alberi bina\u00adri di ricerca<\/li>\n<li>Alberi bilan\u00adcia\u00adti di ricerca&nbsp;<ul>\n<li>Alberi Red-Black<\/li>\n<\/ul>\n<\/li>\n<li>Algoritmi discus\u00adsi a lezione:&nbsp;<ul>\n<li>Ricerca, inse\u00adri\u00admen\u00adto, cancellazione<\/li>\n<li>Successore, pre\u00adde\u00adces\u00adso\u00adre<\/li>\n<li>Minimo, mas\u00adsi\u00admo<\/li>\n<li>Rotazioni in albe\u00adri Red-Black<\/li>\n<\/ul>\n<ul>\n<li>Inserimento in albe\u00adri Red-Black<\/li>\n<li>Cenni sul\u00adla can\u00adcel\u00adla\u00adzio\u00adne in albe\u00adri Red-Black<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>\n<b>Grafi<\/b><\/p>\n<ul>\n<li>Definizioni<\/li>\n<li>Realizzazioni\n<ul>\n<li>Liste\/vettori di adiacenza<\/li>\n<li>Matrici di adiacenza<\/li>\n<\/ul>\n<\/li>\n<li>Visite\n<ul>\n<li>Visita in profondit\u00e0<\/li>\n<li>Visita in ampiezza<\/li>\n<\/ul>\n<\/li>\n<li>Algoritmi basa\u00adti sul\u00adle visite:&nbsp;<ul>\n<li>Distanza<\/li>\n<li>Ordinamento topo\u00adlo\u00adgi\u00adco<\/li>\n<li>Grafi aci\u00adcli\u00adci<\/li>\n<li>Componenti con\u00adnes\u00adse<\/li>\n<li>Componenti for\u00adte\u00admen\u00adte connesse<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>\n<b>Tabelle hash<\/b><\/p>\n<ul>\n<li>Funzioni hash\n<ul>\n<li>Metodo del\u00adla moltiplicazione<\/li>\n<li>Metodo del\u00adla divisione<\/li>\n<\/ul>\n<\/li>\n<li>Metodi di scansione&nbsp;<ul>\n<li>Scansione inter\u00adna<\/li>\n<li>Scansione ester\u00adna<\/li>\n<\/ul>\n<\/li>\n<li>Algoritmi discus\u00adsi a lezione:&nbsp;<ul>\n<li>Tabella hash con scan\u00adsio\u00adne inter\u00adna basa\u00adta su dop\u00adpio hashing<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>\n<b>Insiemi<\/b><\/p>\n<ul>\n<li>Vettori boo\u00adlea\u00adni<\/li>\n<li>Liste\/vettori non ordinati<\/li>\n<li>Liste\/vettori ordi\u00adna\u00adti<\/li>\n<li>Alberi bilan\u00adcia\u00adti<\/li>\n<li>Tabelle hash<\/li>\n<\/ul>\n<p>\n<b>Strutture dati speciali<\/b><\/p>\n<ul>\n<li>Alberi heap<\/li>\n<li>Code con priorit\u00e0<\/li>\n<li>Algoritmi discus\u00adsi a lezione&nbsp;<ul>\n<li>Heapsort<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p><\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Seconda&nbsp;parte del programma \u2014 Seconda prova parziale<\/h4>\n\n\n<p><b>Strutture dati speciali<\/b><\/p>\n<ul>\n<li>Insiemi disgiun\u00adti<\/li>\n<li>Algoritmi discus\u00adsi a lezione&nbsp;<ul>\n<li>Insiemi disgiun\u00adti basa\u00adti su euri\u00adsti\u00adca sul ran\u00adgo e com\u00adpres\u00adsio\u00adne dei cammini<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>\n<b>Strutture dati e pro\u00adget\u00adta\u00adzio\u00adne di algoritmi<\/b><\/p>\n<ul>\n<li>Problema dei cam\u00admi\u00adni minimi<\/li>\n<li>Algoritmi discus\u00adsi a lezione:&nbsp;<ul>\n<li>Algoritmo di Dijkstra<\/li>\n<li>Algoritmo di Johnson<\/li>\n<li>Algoritmo di Fredman-Tarjan<\/li>\n<li>Algoritmo di Bellman-Ford-Moore<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>\n<b>Programmazione dina\u00admi\u00adca<\/b><\/p>\n<ul>\n<li>Zaino 0\/1, con varianti<\/li>\n<li>Sottosequenza comu\u00adne massimale<\/li>\n<li>String mat\u00adching approssimato<\/li>\n<li>Prodotto di cate\u00adna di matrici<\/li>\n<li>Insieme indi\u00adpen\u00adden\u00adte inter\u00adval\u00adli pesati<\/li>\n<li>Cammini mini\u00admi fra tut\u00adte le coppie<\/li>\n<\/ul>\n<p>\n<b>Algoritmi gree\u00addy<\/b><\/p>\n<ul>\n<li>Zaino rea\u00adle<\/li>\n<li>Insieme indi\u00adpen\u00adden\u00adte di intervalli<\/li>\n<li>Problema del&nbsp;resto<\/li>\n<li>Minimo albe\u00adro di copertura&nbsp;<ul>\n<li>Algoritmo di Kruskal<\/li>\n<li>Algoritmo di&nbsp;Prim<\/li>\n<\/ul>\n<\/li>\n<li>Compressione di Huffman (<span class=\"caps\">NO<\/span> 2024\/25)<\/li>\n<\/ul>\n<p>\n<b>Backtrack<\/b><\/p>\n<ul>\n<li>Enumerazione\n<ul>\n<li>Sottoinsiemi<\/li>\n<li>Permutazioni<\/li>\n<li>Problema del\u00adle <em>n<\/em> regine<\/li>\n<li>Giro di cavallo<\/li>\n<li>Sudoku<\/li>\n<\/ul>\n<\/li>\n<li>Inviluppo com\u00adples\u00adso (no 2024\/25)\n<ul>\n<li>Algoritmi di Jarvis e Graham (no 2024\/25)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>\n<b>Ricerca loca\u00adle<\/b><\/p>\n<ul>\n<li>Schema gene\u00adri\u00adco di ricer\u00adca locale<\/li>\n<li>Reti di flusso&nbsp;<ul>\n<li>Ford-Fulkerson<\/li>\n<li>Edmonds-Karp<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>\n<b>Algoritmi pro\u00adba\u00adbi\u00adli\u00adsti\u00adci<\/b><\/p>\n<ul>\n<li>Primalit\u00e0<\/li>\n<li>Bloom fil\u00adters<\/li>\n<li>Quicksort pro\u00adba\u00adbi\u00adli\u00adsti\u00adco <\/li>\n<li>Problema del\u00adla sele\u00adzio\u00adne o del\u00adla mediana<\/li>\n<ul>\n<li>Soluzione pro\u00adba\u00adbi\u00adli\u00adsti\u00adca<\/li>\n<li>Soluzione deter\u00admi\u00adni\u00adsti\u00adca<\/li>\n<\/ul>\n<\/ul>\n<p>\n<b>Ordinamento<\/b><\/p>\n<ul>\n<li>Limiti infe\u00adrio\u00adri per l\u2019or\u00addi\u00adna\u00admen\u00adto (no 2024\/25)<\/li>\n<li>Counting Sort (no 2024\/25)<\/li>\n<li>Pigeonhole Sort (no 2024\/25)<\/li>\n<li>Bucket sort  (no 2024\/25)<\/li>\n<li>Stabilit\u00e0 degli algo\u00adrit\u00admi di ordi\u00adna\u00admen\u00adto (no 2024\/25)<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Solo orale<\/h4>\n\n\n<p><b>NP-Completezza<\/b><\/p>\n<ul>\n<li>Definizione<\/li>\n<li>Riduzione<\/li>\n<li>Classe P<\/li>\n<li>Classe <span class=\"caps\">NP<\/span><\/li>\n<li>Problemi NP-com\u00adple\u00adti<\/li>\n<\/ul>\n<p>\n<b>Soluzioni per pro\u00adble\u00admi intrattabili<\/b><\/p>\n<ul>\n<li>Algoritmi pseu\u00addo-poli\u00adno\u00admia\u00adli<\/li>\n<li>Algoritmi di approssimazione<\/li>\n<li>Algoritmi branch-<span class=\"amp\">&amp;<\/span>-bound<\/li>\n<li>Algoritmi euri\u00adsti\u00adci<\/li>\n<li>Algoritmi visti\n<ul>\n<li>Subset sum, pseudopolinomiale<\/li>\n<li>Partition<\/li>\n<li>Bin-pac\u00adking<\/li>\n<li>Algoritmo appros\u00adsi\u00adma\u00adto per Delta-TSP<\/li>\n<li><span class=\"caps\">TSP<\/span> gree\u00addy<\/li>\n<li><span class=\"caps\">TSP<\/span> ricer\u00adca locale<\/li>\n<li><span class=\"caps\">TSP<\/span> branch-<span class=\"amp\">&amp;<\/span>-bound<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Prima par\u00adte del pro\u00adgram\u00adma \u2014 Prima pro\u00adva par\u00adzia\u00adle Seconda&nbsp;par\u00adte del pro\u00adgram\u00adma \u2014 Seconda pro\u00adva par\u00adzia\u00adle Solo&nbsp;orale<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":4,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"wp_typography_post_enhancements_disabled":false,"footnotes":""},"class_list":["post-45","page","type-page","status-publish","hentry","post"],"_links":{"self":[{"href":"http:\/\/cricca.disi.unitn.it\/montresor\/wp-json\/wp\/v2\/pages\/45","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/cricca.disi.unitn.it\/montresor\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"http:\/\/cricca.disi.unitn.it\/montresor\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"http:\/\/cricca.disi.unitn.it\/montresor\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/cricca.disi.unitn.it\/montresor\/wp-json\/wp\/v2\/comments?post=45"}],"version-history":[{"count":66,"href":"http:\/\/cricca.disi.unitn.it\/montresor\/wp-json\/wp\/v2\/pages\/45\/revisions"}],"predecessor-version":[{"id":5437,"href":"http:\/\/cricca.disi.unitn.it\/montresor\/wp-json\/wp\/v2\/pages\/45\/revisions\/5437"}],"up":[{"embeddable":true,"href":"http:\/\/cricca.disi.unitn.it\/montresor\/wp-json\/wp\/v2\/pages\/4"}],"wp:attachment":[{"href":"http:\/\/cricca.disi.unitn.it\/montresor\/wp-json\/wp\/v2\/media?parent=45"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}