By Bernhard Korte, Jens Vygen

Questo libro di testo di ottimizzazione combinatoria pone in particolare risalto i

risultati teorici e gli algoritmi che, al contrario delle euristiche, hanno una garanzia

di avere buone prestazioni. Comprende una vasta scelta di argomenti e nasce

come riferimento di diversi corsi di ottimizzazione combinatoria sia di base che di

livello avanzato. Il libro contiene dimostrazioni entire (ma concise) anche

di molti risultati avanzati, alcuni dei quali non sono mai apparsi prima in un libro.

Vengono anche trattati molti dei temi di ricerca più attuali e sono riportati molti

riferimenti alla letteratura. Quindi questo libro, traduzione della quarta edizione in lingua originale, rappresenta lo stato dell’arte dell’ottimizzazione combinatoria.

Show description

Read or Download Ottimizzazione Combinatoria: Teoria e Algoritmi PDF

Similar italian books

Bossic instinct

Il libro raccoglie le principali vignette edite ed inedite del 1993. Un anno così burrascoso dal punto di vista politico da rappresentare, according to Forattini, un'autentica cuccagna.

Extra resources for Ottimizzazione Combinatoria: Teoria e Algoritmi

Example text

M} tale che si = ti per i = 1, . . , j − 1 e s j < t j . Ora, date n stringhe di lunghezza m, vorremo ordinarle lessicograficamente. Dimostrare che esiste un algoritmo tempo-lineare per questo problema (ovvero con tempo di esecuzione O(nm)). Suggerimento: raggruppare le stringhe in base al primo bit e ordinare ciascun gruppo. 8. Descrivere un algoritmo che ordini una lista di numeri naturali a1 , . . , an in tempo lineare; cio`e che trovi una permutazione π con aπ(i) ≤ aπ(i+1) (i = 1, . . , n − 1) e richieda tempo O(log(a1 + 1) + · · · + log(an + 1)).

Inoltre, dist(G,c) (v, w) denota il minimo c(E(P)) su tutti i cammini v-w P in G. 2 Alberi, circuiti e tagli Un grafo non orientato G e` connesso se esiste un cammino v-w per tutti i v, w ∈ V (G); in caso contrario G e` sconnesso. Un digrafo e` connesso se il grafo non orientato sottostante e` connesso. I sottografi connessi massimali di un grafo sono le sue componenti connesse. A volte, si identificano le componenti connesse con l’insieme di vertici che le induce. Un insieme di vertici X e` connesso se il sottografo indotto da X e` connesso.

Dimostrazione. A qualsiasi passo dell’algoritmo, (R, T ) e` un albero o un’arborescenza radicata in s. Si supponga che alla fine dell’esecuzione dell’algoritmo esista un vertice w ∈ V (G) \ R che e` raggiungibile da s. Sia P un cammino s-w, e sia {x, y} o (x, y) un arco di P con x ∈ R e y ∈ / R. Poich´e x e` stato aggiunto a R, ad un certo passo dell’esecuzione dell’algoritmo, e` stato aggiunto anche a Q. L’algoritmo non si ferma prima di aver rimosso x da Q. Ma questo viene fatto in / R. 3 solo se non esiste alcun arco {x, y} o (x, y) con y ∈ Siccome questo e` il primo algoritmo per grafi incontrato in questo libro, presentiamo alcune problematiche implementative.

Download PDF sample

Rated 4.19 of 5 – based on 37 votes