Проблеми на обучението по програмиране

Доклад по покана, поместен в сборника на Националната конференция "Образованието в информационното общество", Пловдив, октомври, 2006 г.

Quadratic Time Computable Instances of MaxMin and MinMax Area Triangulations of Convex Polygons

We consider the problems of finding two optimal triangulations of a convex polygon: MaxMin area and MinMax area. These are the triangulations that maximize the area of the smallest area triangle in a triangulation, and respectively minimize the area of the largest area triangle in a triangulation, over all possible triangulations. The problem was originally solved by Klincsek by dynamic programming in cubic time [2]. Later, Keil and Vassilev devised an algorithm that runs in O(n^2 log n) time [1]. In this paper we describe new geometric findings on the structure of MaxMin and MinMax Area triangulations of convex polygons in two dimensions and their algorithmic implications. We improve the algorithm’s running time to quadratic for large classes of convex polygons. We also present experimental results on MaxMin area triangulation.

On the Factorization of the Poincaré Polynomial: A Survey

2000 Mathematics Subject Classification: 13P05, 14M15, 14M17, 14L30.

A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs

ACM Computing Classification System (1998): G.2.2.

Programming and Testing a Two-Tree Algorithm

ACM Computing Classification System (1998): G.2.2, F.2.2.

Model Mining and Efficient Verification of Software Product Lines

Software product line modeling aims at capturing a set of software products in an economic yet meaningful way. We introduce a class of variability models that capture the sharing between the software artifacts forming the products of a software product line (SPL) in a hierarchical fashion, in terms of commonalities and orthogonalities. Such models are useful when analyzing and verifying all products of an SPL, since they provide a scheme for divide-and-conquer-style decomposition of the analysis or verification problem at hand. We define an abstract class of SPLs for which variability models can be constructed that are optimal w.r.t. the chosen representation of sharing. We show how the constructed models can be fed into a previously developed algorithmic technique for compositional verification of control-flow temporal safety properties, so that the properties to be verified are iteratively decomposed into simpler ones over orthogonal parts of the SPL, and are not re-verified over the shared parts. We provide tool support for our technique, and evaluate our tool on a small but realistic SPL of cash desks.

Partial Ovoids and Partial Spreads of Classical Finite Polar Spaces

2000 Mathematics Subject Classification: 05B25, 51E20.