Experimental Algorithms Lab

Laboratorio Statistico-Informatico - 2009-2010

Gianluca Della Vedova — Wed, 01 Sep 2010 09:41:54 +0200

Laboratorio Statistico-Informatico - 2009-2010

Obiettivi dell'attività formativa

Il corso si propone di introdurre alcuni strumenti informatici per il trattamento di dati statistici. Tale obiettivo verrà perseguito attraverso lo studio dei concetti fondamentali soggiacenti a SAS© e l'utilizzo di tale sistema di strumenti per la risoluzione di problemi di trattamento di dati.

L'attività formativa è svolta attraverso lezioni al calcolatore.

Risultati appelli

Appello del 21/6/2010. Risultati

Verbalizzazione Giovedì 24 alle 12 nel mio ufficio. Chi non potesse essere presente, mi contatti per email per fissare un appuntamento.

Programma dettagliato

Introduzione al trattamento dati con SAS©

Il dataset SAS, creazione di un dataset, caricamento e salvataggio di un dataset.

Dati per prima lezione: wheat.txt balloon braziltourism.csv.

Descrizione dei dati

Il data step, librerie, librerie temporanee e permanenti, variabili, array, dividere, fondere e ordinare dataset

Inferire informazioni dai dati

PROC MEANS, PROC CORR, PROC UNIVARIATE, PROC REG, PROC FREQ

Rappresentazione tabulare dei dati

PROC PRINT, PROC FORMAT

Macro in SAS

Propedeuticità

Nessuna.

Modalità dell'esame

L'esame consiste in una prova scritta da svolgere al calcolatore.

Materiale didattico

Il libro di testo adottato è “The Little SAS Book”, SAS Institute.

Ulteriori informazioni saranno disponibili durante il periodo di lezione nella pagina relativa all'insegnamento sulla piattaforma di e-learning.

Tutti gli studenti sono fortemente invitati ad iscriversi al corso sulla piattaforma di e-learning, in quanto solo in questo modo è posssibile scaricare il materiale didattico e contattare il docente.

Papers

Gianluca Della Vedova — Fri, 30 Jul 2010 11:04:12 +0200

Papers

Almost all my papers are indexed at the wonderful DBLP. Also I have made available a preprint of my recent papers at ArXiv, and I plan to do so for the foreseeable future.

Some publishers also want me to state the obvious:
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder

to appear

Paola Bonizzoni, Gianluca Della Vedova, and Riccardo Dondi. Anonymizing binary and small tables is hard to approximate. Journal of Combinatorial Optimization, to appear. [ arXiv ]

The problem of publishing personal data without giving up privacy is becoming increasingly important. An interesting formalization recently proposed is the k-anonymity. This approach requires that the rows in a table are clustered in sets of size at least k and that all the rows in a cluster become the same tuple, after the suppression of some records. The natural optimization problem, where the goal is to minimize the number of suppressed entries, is known to be NP-hard when the values are over a ternary alphabet, k=3 and the rows length is unbounded. In this paper we give a lower bound on the approximation factor that any polynomial-time algorithm can achieve on two restrictions of the problem, namely (i) when the records values are over a binary alphabet and k=3, and (ii) when the records have length at most 8 and k=4, showing that these restrictions of the problem are APX-hard.

2010

Paola Bonizzoni, Gianluca Della Vedova, and Riccardo Dondi. Approximating clustering of fingerprint vectors with missing values. Algorithmica, 58(2):282-303, 2010. [ DOI | arXiv ]

The problem of clustering fingerprint vectors with missing values is an interesting problem in Computational Biology that has been proposed in Figueroa et al. (J. Comput. Biol. 11(5):887–901, 2004). In this paper we show some improvements in closing the gaps between the known lower bounds and upper bounds on the approximability of variants of the biological problem. Moreover, we have studied two additional variants of the original problem proposed in Figueroa et al. (Proc. 11th Computing: The Australasian Theory Symposium (CATS), CRPIT, vol. 41, pp. 57–60, 2005). We prove that all such problems are APX-hard even when each fingerprint contains only two unknown positions and we present a greedy algorithm that has constant approximation factors for these variants. Despite the hardness of these restricted versions of the problem, we show that the general clustering problem on an unbounded number of missing values such that they occur for every fixed position of an input vector in at most one fingerprint is polynomial time solvable.

Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, Tao Jiang, Giulio Pavesi, Yuri Pirola, and Lusheng Wang. Beyond evolutionary trees. Natural Computing, 9(2):421-435, 2010. [ DOI ]

In Computational Biology, the notion of phylogeny has become synonymous with tree-like evolution. Recent advances in the Life Sciences have suggested that evolution has a much more diverse course. In this paper we will survey some of the models that have been proposed to overcome the limitations of using phylogenies to represent evolutionary histories.

Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, and Yuri Pirola. Parameterized complexity of k-anonymity: Hardness and tractability. In Proc. 21st International Workshop on Combinatorial Algorithms (IWOCA 2010), 2010. [ arXiv ]

The problem of publishing personal data without giving up privacy is becoming increasingly important. An interesting formalization that has been recently proposed is the k-anonymity. This approach requires that the rows of a table are partitioned in clusters of size at least k and that all the rows in a cluster become the same tuple, after the suppression of some entries. The natural optimization problem, where the goal is to minimize the number of suppressed entries, is known to be APX-hard even when the records values are over a binary alphabet and k=3, and when the records have length at most 8 and k=4. In this paper we study how the complexity of the problem is influenced by different parameters. In this paper we follow this direction of research, first showing that the problem is W[1]-hard when parameterized by the size of the solution (and the value k). Then we exhibit a fixed parameter algorithm, when the problem is parameterized by the size of the alphabet and the number of columns. Finally, we investigate the computational (and approximation) complexity of the k-anonymity problem, when restricting the instance to records having length bounded by 3 and k=3. We show that such a restriction is APX-hard.

Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, Yuri Pirola, and Romeo Rizzi. Pure parsimony Xor haplotyping. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2010. [ DOI | arXiv ]

The haplotype resolution from xor-genotype data has been recently formulated as a new model for genetic studies. The xor-genotype data is a cheaply obtainable type of data distinguishing heterozygous from homozygous sites without identifying the homozygous alleles. In this paper we propose a formulation based on a well known model used in haplotype inference: pure parsimony. We exhibit exact solutions of the problem by providing polynomial-time algorithms for some restricted cases and a fixed-parameter algorithm for the general case. These results are based on some interesting combinatorial properties of a graph representation of the solutions. Differently from the same problem on full genotypes, we show that the problem has a polynomial-time k-approximation. Moreover we propose a heuristic and produce an experimental analysis showing that it scales to real-world instances taken from the HapMap project.

Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, and Yuri Pirola. Variants of constrained longest common subsequence. Information Processing Letters, 110(20):877-881, 2010. [ DOI | arXiv ]

We consider a variant of the classical Longest Common Subsequence problem called Doubly-Constrained Longest Common Subsequence (DC-LCS). Given two strings s₁ and s₂ over an alphabet Σ, a set C_s of strings, and a function C_o : Σ->N, the DC-LCS problem consists of finding the longest subsequence s of s₁ and s₂ such that s is a supersequence of all the strings in C_s and such that the number of occurrences in s of each symbol σinΣ is upper bounded by C_o(σ). The DC-LCS problem provides a clear mathematical formulation of a sequence comparison problem in Computational Biology and generalizes two other constrained variants of the LCS problem that have been introduced previously in the literature: the Constrained LCS and the Repetition-Free LCS. We present two results for the DC-LCS problem. First, we illustrate a fixed-parameter algorithm where the parameter is the length of the solution which is also applicable to the more specialized problems. Second, we prove a parameterized hardness result for the Constrained LCS problem when the parameter is the number of the constraint strings (|C_s|) and the size of the alphabet Σ. This hardness result also implies the parameterized hardness of the DC-LCS problem (with the same parameters) and its NP-hardness when the size of the alphabet is constant.

2009

Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, Yuri Pirola, and Raffaella Rizzi. Minimum factorization agreement of spliced ests. In Proceedings of the 9th Workshop on Algorithms in Bioinformatics (WABI 2009), pages 1-12, 2009. [ arXiv ]

Paola Bonizzoni, Gianluca Della Vedova, and Riccardo Dondi. A PTAS for the minimum consensus clustering problem with a fixed number of clusters. In Proceedings of the 11th Italian Conference on Theoretical Computer Science (ICTCS 2009), 2009. [ arXiv | Slides ]

Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, and Yuri Pirola. The k-anonymity problem is hard. In Proceedings of the 17th International Symposium on Fundamentals of Computation Theory (FCT 2009), pages 26-37, 2009. [ arXiv ]

Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, Yuri Pirola, and Romeo Rizzi. Pure parsimony xor haplotyping. In Proceedings of the 5th International Symposium on Bioinformatics Research and Applications, (ISBRA 2009), volume 5542 of LNCS, pages 186-197, 2009. [ arXiv ]

Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, and Yuri Pirola. Parameterized complexity of the k-anonymity problem. Technical report, CoRR, 2009. [ arXiv ]

2008

Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, and Giancarlo Mauri. The comparison of phylogenetic networks: Algorithms and complexity. In Ion Mandoiu and Alexander Zelikovsky, editors, Bioinformatics Algorithms: Techniques and Applications, pages 143-173. Wiley-Interscience, 2008.

Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, and Tao Jiang. On the approximation of correlation clustering and consensus clustering. Journal of Computer and System Sciences, 74(5):671-696, 2008. [ DOI | arXiv ]

The Correlation Clustering problem has been introduced recently as a model for clustering data when a binary relationship between data points is known. More precisely, for each pair of points we have two scores measuring the similarity and dissimilarity respectively, of the two points, and we would like to compute an optimal partition where the value of a partition is obtained by summing up the similarity scores of pairs involving points from the same cluster and the dissimilarity scores of pairs involving points from different clusters. A closely related problem is Consensus Clustering, where we are given a set of partitions and we would like to obtain a partition that best summarizes the input partitions. The latter problem is a restricted case of Correlation Clustering. In this paper we prove that Minimum Consensus Clustering is APX-hard even for three input partitions, answering an open question in the literature, while Maximum Consensus Clustering admits a PTAS. We exhibit a combinatorial and practical (4)/(5)-approximation algorithm based on a greedy technique for Maximum Consensus Clustering on three partitions. Moreover, we prove that a PTAS exists for Maximum Correlation Clustering when the maximum ratio between two scores is at most a constant.

2007

Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, and Jing Li. The haplotyping problem: An overview of computational models and solutions. In Sun Kim, Haixu Tang, and Elaine R. Mardis, editors, Genome Sequencing Technology and Algorithms, pages 151-181. Artech House, Inc., 2007.

Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, Guillaume Fertin, Raffaella Rizzi, and Stéphane Vialette. Exemplar longest common subsequence. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 4(4):535-543, 2007. [ DOI | arXiv ]

In the paper we investigate the computational and approximation complexity of the Exemplar Longest Common Subsequence of a set of sequences (ELCS problem), a generalization of the Longest Common Subsequence problem, where the input sequences are over the union of two disjoint sets of symbols, a set of mandatory symbols and a set of optional symbols. We show that different versions of the problem are APX-hard even for instances with two sequences. Moreover, we show that the related problem of determining the existence of a feasible solution of the Exemplar Longest Common Subsequence of two sequences is NP-hard. On the positive side, efficient algorithms for the ELCS problem over instances of two sequences where each mandatory symbol can appear totally at most three times or the number of mandatory symbols is bounded by a constant are given.

2006

Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, and Lorenzo Mariani. Experimental analysis of a new algorithm for partial haplotype completion. International Journal of Bioinformatics Research and Applications, 1(4):461-473, 2006.

Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, and Giancarlo Mauri. Fingerprint clustering with bounded number of missing values. In Proceedings of the 17th Symposium on Combinatorial Pattern Matching (CPM2006), pages 106-116, 2006. [ DOI | arXiv ]

Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, Guillaume Fertin, and Stéphane Vialette. Exemplar longest common subsequence. In International Conference on Computational Science (2), pages 622-629, 2006. [ DOI ]

Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, and Giancarlo Mauri. A PTAS for the maximum consensus clustering. In Proc. 1st FIMA International Conference Models and Methods for Human Genomics, 2006. [ arXiv ]

2005

Paola Bonizzoni, Gianluca Della Vedova, and Riccardo Dondi. Reconciling gene trees to a species tree. Theoretical Computer Science, 347(1-2):36-53, 2005. [ .pdf ]

The general problem of reconciling the information from evolutionary trees representing the relationships between distinct gene families is of great importance in Bioinformatics and has been popularized among the Computer Science researchers in (Ma, Li and Zhang, SIAM J. Comp. 2000) where the authors pose the intriguing question if a certain definition of minimum tree that reconciles a gene tree and a species tree is correct. We answer affirmatively to this question; moreover we show an efficient algorithm for computing such minimum-leaf reconciliation trees and prove the uniqueness of such trees. We then tackle some different versions of the biological problem by showing that the exemplar problem, arising from the exemplar analysis of multigene genomes, is NP-hard even when the number of copies of a given label is at most two. Finally we introduce two novel formulations for the problem of recombining evolutionary trees, extending the gene duplication problem studied previously, and we give an exact algorithm (via dynamic programming) for one of these formulations.

Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, and Lorenzo Mariani. Experimental analysis of a new algorithm for partial haplotype completion. In International Conference on Computational Science (2), volume 3515 of LNCS, pages 952-959, 2005.

Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, and Tao Jiang. Correlation clustering and consensus clustering. In Algorithms and Computation, 16th International Symposium (ISAAC), volume 3827 of LNCS, pages 226-235, 2005.

Gianpiero Cattaneo, Gianluca Della Vedova, Alberto Ottavio Leporati, and Roberto Leporini. Towards a theory of conservative computing. International Journal of Theoretical Physics, 44(7):861-873, 2005.

2004

Paola Bonizzoni, Gianluca Della Vedova, and Tao Jiang. Foreword - special issue on bioinformatics. Journal of Computer Science and Technology, 19(1):1-1, 2004.

Winfried Just and Gianluca Della Vedova. Multiple sequence alignment as a facility location problem. INFORMS Journal on Computing, 16(4):430-440, 2004. [ DOI | .pdf ]

This paper deals with the computational problem of inferring complete information on haplotypes from haplotypes with missing data. This problem is one of the main issues in haplotyping, as the current DNA sequencing technology often produces haplotypes with missing bases and thus the complete information on haplotypes has to be inferred through computational methods. In this paper we propose a new algorithmic approach to the problem that assumes both the Coalescent and the Minimum Entropy models and we provide an experimental analysis relating it to the previously investigated approaches. In particular, the reconstruction of a perfect phylogeny from haplotypes with missing data is addressed.

Lea Valinsky, Alexandra J. Scupham, Gianluca Della Vedova, Zheng Liu, Andres Figueroa, Katechan Jampachaisri, Bei Yin, Elizabeth Bent, Robert Mancini-Jones, James Press, Tao Jiang, and James Borneman. In G. A. Kowalchuk, F. J. de Bruijn, I. M. Head, A. D. L. Akkermans, and J. D. van Elsas, editors, Molecular Microbial Ecology Manual, pages 569-585. Kluwer Academic Publishers, Dordrecht, The Netherlands, 2nd edition, 2004.

Sergio Pozzi, Gianluca Della Vedova, and Giancarlo Mauri. An explicit upper bound for the approximation ratio of the maximum gene regulatory network problem. In CMSB04, volume 3082 of LNCS, pages 1-8, 2004.

2003

Gianluca Della Vedova and Riccardo Dondi. A library of efficient bioinformatics algorithms. Applied Bioinformatics, 2(2):117-121, 2003. [ .pdf ]

Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, and Jing Li. The haplotyping problem: An overview of computational models and solutions. Journal of Computer Science and Technology, 18(6):675-688, 2003. [ DOI | .pdf ]

Paola Bonizzoni, Gianluca Della Vedova, and Riccardo Dondi. Reconciling gene trees to a species tree. In R. Petreschi, G. Persiano, and R. Silvestri, editors, Algorithms and Complexity, Proceedings of the 5th Italian Conference (CIAC 2003), volume 2653 of LNCS, pages 120-131, 2003.

2002

Gianluca Della Vedova and H. Todd Wareham. Optimal algorithms for local vertex quartet cleaning. Bioinformatics, 18(10):1297-1304, 2002.

Reconstructing evolutionary trees is an important problem in biology. A response to the computational intractability of most of the traditional criteria for inferring evolutionary trees has been a focus on new criteria, particularly quartet-based methods that seek to merge trees derived on subsets of four species from a given species-set into a tree for that entire set. Unfortunately, most of these methods are very sensitive to errors in the reconstruction of the trees for individual quartets of species. A recently-developed technique called quartet cleaning can alleviate this difficulty in certain cases by using redundant information in the complete set of quartet topologies for a given species-set to correct such errors. In this paper, we describe two new local vertex quartet cleaning algorithms which have optimal time complexity and error-correction bound, respectively. These are the first known local vertex quartet cleaning algorithms that are optimal with respect to either of these attributes.

Gianluca Della Vedova and H. Todd Wareham. Optimal algorithms for local vertex quartet cleaning. In Proceedings of the 17th ACM Symposium on Applied Computing (SAC2002), pages 173-177, 2002. [ .pdf ]

Gianluca Della Vedova, Tao Jiang, Jing Li, and Jianjun Wen. Approximating minimum quartet inconsistency. In 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA2002), pages 894-895, 2002. [ .pdf ]

Lea Valinsky, Gianluca Della Vedova, A.J. Scupham, S. Alvey, Andres Figueroa, B. Yin, R.J. Hartin, Marek Chrobak, D.E. Crowley, Tao Jiang, and James Borneman. Analysis of bacterial microbial community composition by oligonucleotide fingerprinting of rrna genes. Applied and Environmental Microbiology, 68(7):3243-3250, 2002.

Lea Valinsky, Gianluca Della Vedova, Tao Jiang, and James Borneman. Oligonucleotide fingerprinting of rrna genes for analysis of fungal community composition. Applied and Environmental Microbiology, 68(12):5999-6004, 2002.

2001

Paola Bonizzoni, Gianluca Della Vedova, and Giancarlo Mauri. Experimenting an approximation algorithm for the LCS. Discrete Applied Mathematics, 110(1):13-24, 2001. [ .pdf ]

The problem of finding the longest common subsequence (lcs) of a given set of sequences over an alphabet Σ occurs in many interesting contexts, such as data compression and molecular biology, in order to measure the “similarity degree” among biological sequences. Since the problem is NP-complete in its decision version (i.e. does there exist a lcs of length at least k, for a given k?) even over fixed alphabet, polynomial algorithms which give approximate solutions have been proposed. Among them, Long Run (LR) is the only one with guaranteed constant performance ratio. In this paper, we give a new approximation algorithm for the longest common subsequence problem: the Expansion algorithm (EA). First of all we prove that the solution found by the Expansion algorithm is always at least as good as the one found by LR. Then we report the results of an experimentation with two different groups of instances, which show that EA clearly outperforms Long Run in practice.

James Borneman, Marek Chrobak, Gianluca Della Vedova, Andres Figueroa, and Tao Jiang. Probe selection algorithms with applications in the analysis of microbial communities. Bioinformatics, 17(Suppl. 1):S39-S48, 2001. [ .pdf ]

We propose two efficient heuristics for minimizing the number of oligonucleotide probes needed for analyzing populations of ribosomal RNA gene (rDNA) clones by hybridization experiments on DNA microarrays. Such analyses have applications in the study of microbial communities. Unlike in the classical SBH (sequencing by hybridization) procedure, where multiple probes are on a DNA chip, in our applications we perform a series of experiments, each one consisting of applying a single probe to a DNA microarray containing a large sample of rDNA sequences from the studied population. The overall cost of the analysis is thus roughly proportional to the number of experiments, underscoring the need for minimizing the number of probes. Our algorithms are based on two well-known optimization techniques, i.e. simulated annealing and Lagrangian relaxation, and our preliminary tests demonstrate that both algorithms are able to find satisfactory probe sets for real rDNA data.

Paola Bonizzoni and Gianluca Della Vedova. The complexity of multiple sequence alignment with SP-score that is a metric. Theoretical Computer Science, 259(1):63-79, 2001. [ .pdf ]

This paper analyzes the computational complexity of computing the optimal alignment of a set of sequences under the SP (sum of all pairs) score scheme. We solve an open question by showing that the problem is NP-complete in the very restricted case in which the sequences are over a binary alphabet and the score is a metric. This result establishes the intractability of multiple sequence alignment under a score function of mathematical interest, which has indeed received much attention in biological sequence comparison.

James Borneman, Marek Chrobak, Gianluca Della Vedova, Andres Figueroa, and Tao Jiang. Probe selection algorithms with applications in the analysis of microbial communities. In Proceedings of the 9th International Conference on Intelligent Systems for Molecular Biology (ISMB2001), pages S39-S48, 2001. [ Slides ]

Lea Valinsky, A.J. Scupham, Gianluca Della Vedova, Marek Chrobak, Tao Jiang, Andres Figueroa, R.J. Hartin, B. Yin, and James Borneman. A dna array approach for analysis of microbial communities using oligonucleotide fingerprinting of ribosomal rna genes. In Annual Meeting of the American Phytopathological Society 2001, volume 91 of Phytopathology, page S90, 2001.

Paolo Barone, Paola Bonizzoni, Gianluca Della Vedova, and Giancarlo Mauri. An approximation algorithm for the shortest common supersequence: An experimental analysis. In Proceedings of the 16th ACM Symposium on Applied Computing (SAC2001), pages 56-60, 2001. [ .pdf ]

2000

Paola Bonizzoni, Gianluca Della Vedova, and Giancarlo Mauri. Approximating the maximum isomorphic agreement subtree is hard. International Journal on the Foundations of Computer Science, 11(4):579-590, 2000. [ .pdf ]

The Maximum Isomorphic Agreement Subtree (MIT) problem is one of the simplest versions of the Maximum Interval Weight Agreement Subtree method (MIWT) which is used to compare phylogenies. More precisely MIT allows to provide a subset of the species such that the exact distances between species in such subset are preserved among all evolutionary trees considered. In this paper, the approximation complexity of the MIT problem is investigated, showing that it cannot be approximated in polynomial time within factor log^δn for any δ>0 unless NP=DTIME(2^{polylog n}) for instances containing three trees. Moreover, we show that such result can be strengthened whenever instances of the MIT problem can contain an arbitrary number of trees, since MIT shares the same approximation lower bound of MAX CLIQUE.

Winfried Just and Gianluca Della Vedova. Multiple sequence alignment as a facility location problem. In Proceedings of the Prague Stringology Club Workshop 2000 (PSCW2000), 2000.

Paola Bonizzoni, Gianluca Della Vedova, and Giancarlo Mauri. Approximating the maximum isomorphic agreement subtree is hard. In Raffaele Giancarlo and David Sankoff, editors, Proceedings of the 11th Symposium on Combinatorial Pattern Matching (CPM2000), volume 1848 of LNCS, pages 119-128, 2000.

1999

Paola Bonizzoni and Gianluca Della Vedova. An algorithm to compute the modular decomposition of hypergraphs. Journal of Algorithms, 32(2):65-86, 1999. [ .pdf ]

We propose an O(n⁴) algorithm to build the modular decomposition tree of hypergraphs of dimension 3 and show how this algorithm can be generalized to compute in O(n^{3k -5}) time the decomposition of hypergraphs of any fixed dimension k.

Paola Bonizzoni, Gianluca Della Vedova, and Tao Jiang. Approximating maximum trace alignment and its complement. manuscript, 1999.

1998

P. Bonizzoni, G. Della Vedova, and G. Mauri. Graal: a graph-based algebra to model information retrieval. Rapporto n.1 - Contratto ENEL/CRA n. R23WC0012, 1998.

Paola Bonizzoni, Massimo D'Alessandro, Gianluca Della Vedova, and Giancarlo Mauri. Experimenting an approximation algorithm for the lcs. In Roberto Battiti and Alan Bertossi, editors, Algorithms and Experiments (ALEX98), pages 96-102, 1998.

1997

P. Bonizzoni, G. Della Vedova, and G. Mauri. Modellizzazione ad oggetti di sistemi multimediali distribuiti, 1997.

P. Bonizzoni, G. Della Vedova, and G. Mauri. Modellizzazione ad oggetti di sistemi multimediali distribuiti. Rapporto finale - Contratto ENEL/CRA n. R23TC0012, 1997.

Paola Bonizzoni, Gianluca Della Vedova, Dario Lucarella, and Giancarlo Mauri. On genericity and stability in a graph based data model. Technical Report TR 201-97, Dipartimento di Scienze dell'Informazione, Università degli Studi di Milano, 1997.

P. Bonizzoni, G. Della Vedova, D. Lucarella, and G. Mauri. Graal: a graph based query language. manuscript, 1997.

1995

Paola Bonizzoni and Gianluca Della Vedova. Modular decomposition of hypergraphs. In Manfred Nagl, editor, Proceedings of the 21st Workshop on Graph-Theoretic Concepts in Computer Science (WG95), volume 1017 of LNCS, pages 303-317, 1995.

Gianluca Della Vedova. An algorithm to compute the modular decomposition of k-structures. Technical Report TR139-95, Università degli Studi di Milano, Dipartimento di Scienze dell'Informazione, 1995.

Basi di Dati - 2009-2010

Gianluca Della Vedova — Wed, 14 Jul 2010 18:29:35 +0200

Basi di Dati - 2009-2010

Obiettivi dell'attività formativa

Il corso si propone di introdurre alcuni strumenti informatici avanzati per il trattamento delle informazioni. Un primo obiettivo consiste nella presentazione del modello Entità-Relazione per la rappresentazione di dati. Successivamente verrà introdotto un linguaggio di programmazione e mostrato come tale linguaggio permetta di operare sui dati. L'ultimo obiettivo è l'introduzione alle basi di dati, con particolare riferimento alla modellazione ed alla interrogazione delle stesse.

L'attività formativa è svolta attraverso lezioni.

Programma riassuntivo

ARGOMENTI	Ore Lezioni
Tecniche e concetti della progettazione concettuale	6
Modello relazionale	8
SQL come linguaggio per la definizione dei dati	8
SQL come linguaggio per la interrogazione dei dati	10
Il modello Entità-Relazione	16
TOTALE GENERALE	48

Programma dettagliato

Fondamenti di basi di dati.

Nozioni di progettazione concettuale: Suddivisione logica fra schemi e istanze; Criteri di rappresentazione; Obiettivi della progettazione.

Tecniche di progettazione: Strategie top-down, bottom-up.

Modello relazionale: Algebra relazionale; Chiavi e vincoli di integrità; Prima e terza forma normale e loro proprietà.

SQL: Concetti fondamentali dei linguaggi di programmazione; Definizione di schemi e tabelle.

Come gestire i dati in formato tabellare in SQL.

Collegare informazioni memorizzate in tabelle diverse. Estrazione di informazioni in tabelle. Viste.

Modello Entità-Relazione: Introduzione alla progettazione di basi di dati; Introduzione al modello E-R; Costrutti fondamentali e avanzati di E-R.

Tecniche di documentazione; Analisi di schemi E-R; Ristrutturazione di schemi;.

Da E-R a modello relazionale; Relazioni uno a uno; Relazioni uno a molti, molti a uno, molti a molti.

Propedeuticità

Nessuna

Modalità dell'esame

L'esame consiste in una prova scritta (dove viene verificata la capacità di progettazione di un diagramma ER e la conoscenza di SQL) ed una orale.

Risultati

Esame del 13 Luglio 2010: Ammessi all'orale.

Studente	Voto
Bollani	22
Carrara	28
Carsana	22
Coppa	23
Ferraioli	20
Giardiello	26
Giuliano	18
Graziani	19
La Porta	24
Lini	21
Manzoni	24
Mazzola	19
Riganti	23
Romanoni	25
Dell'Ovo	20
Soncco Zuniga	25
Sperman	30
Triunfo	20

Gli orali saranno Giovedì 15 a partire dalle 10.30 nell'aula seminari sezione Economica. Gli orali si tengono in ordine crescente di voto ottenuto allo scritto.

Materiale didattico

Il libro di testo adottato è “Basi di dati, Modelli e Linguaggi di interrogazione”, Atzeni, Ceri, Paraboschi, Torlone, McGraw-Hill.

Le parti relative a trigger e Data Warehouse si trovano nel libro Basi di dati: Architetture e linee di evoluzione, P. Atzeni, S. Ceri, P. Fraternali, S. Paraboschi, R. Torlone McGraw-Hill Italia.

Sono reperibili le soluzioni degli esercizi svolti.

Orario delle lezioni

Giorno	Ora	Aula
Lunedì	9.10-11.30	U7-22
Martedì	9.10-11.30	U7-22
Mercoledì	14.30-16.00	U7-22

L'orario sopra indicato è quello effettivo di lezione.

Elenco delle lezioni

Descrizione del corso. Basi di Dati e DBMS. Suddivisione logica fra schemi e istanze.
Il modello logico. Relazione come associazione fra oggetti. Definizione matematica di relazione. Il modello relazionale. Il valore NULL. Vincoli. Vincoli di integrità.
Chiavi di una tabella. Definizione di chiavi primaria.
Algebra relazionale: proiezione, restrizione, unione, intersezione, differenza.
Algebra relazionale: join naturale, join esterno e confronto con join naturale. Interrogazioni nel modello relazionale.
Cenni di calcolo relazionale.
Introduzione ai linguaggi di programmazione. SQL: definizione dei dati. Schemi, tabelle, domini. Vincoli intra e interrelazionali. Definizione di chiavi primaria. Vincoli di integrità. Differenza fra REFERENCES e FOREIGN KEY.
Restrizione di dominio. Modifica struttura di una tabella. Interrogazioni che coinvologono una tabella. SELECT .. FROM .. WHERE. Creazione di viste. GROUP BY. ORDER BY. Operatori aggregati. Interrogazioni che coinvologono almeno due tabelle. HAVING. Interrogazioni nidificate. Alias delle tabelle
Inserimento e modifica dati in una tabella.
Creazione di indici. Definizione di vista e vista materializzata. Check. Funzioni scalari.
Motivazioni e obiettivi della progettazione concettuale. Criteri di rappresentazione. Modello Entità relazione: costrutti fondamentali
Modello Entità relazione: attributi, generalizzazioni. Progettazione concettuale di un database universitario. Chiavi di una entità. Cardinalità delle relazioni. Documentazione dello schema. Regole aziendali. Strategie top-down e bottom-up.
La progettazione logica come passo intermedio fra la progettazione concettuale e la realizzazione nel modello relazionale. Passare dallo schema ER alle tabelle.
Forma normale di Boyce-Codd. Terza forma normale. Proprietà delle forme normali. Trasformazioni di schemi.
Transazioni. Autoreferenzialità nei DBMS.
Trigger.
Sicurezza nelle basi di dati.
Cenni di Data Warehouse.