1,721,022 research outputs found
Convex Minimization on a Grid and Applications
No full textThis artide discussesa discrete version of the convex minimization problem with applicationsto the efficient computation of proximity measures for pairs of convex polyhedra. Given a d-variate convex function and an isothetic grid of size O(nd) in Rd, which is supposed to be finite but not necessarily regular, we want to find the grid cell containing the minimum point. With this aim, we identify a dass of elementary subproblems, each resulting in the determination of a half-space in Rd, and show that the minimization problem can be solved by computing O(log n) half-spaces in the worst case for almost uniform grids of fixed dimension d and O(log n) half-planes in the average for arbitrary planar grids A major point is the potential of the approach to uniformly solve distance related problems for different configurations of a pair of convex bodies In this respect, the case of a bivariate function is of particular interest and leads to a fast algorithm for detecting collisions between two convex polyhedra in three dimensions. The collision algo-rithm runs in O(log2n) average time for polyhedra with O(n) vertices whose boundaries are suitably represented; more specifically, the 1-skeletons can be embedded into layered Directed Acyclic Graphs which require just O(n) storage. The article ends with a brief discussion of a few experimental results
Oltre l'arcano del "giuoco delle perle di vetro"
No full textUn tema molto dibattuto nell’ambito della didattica dell’informatica, a partire dagli anni ’90 quando l’esercizio della programmazione ha cominciato ad essere via via sostituito dall’introduzione di strumenti applicativi preconfezionati, riguarda il ruolo educativo da attribuire a questa disciplina nel corso dell’istruzione scolastica. Ci si riferisce, in particolare, agli aspetti che possono avere valore formativo per ogni allievo, non solo per coloro che la scelgono come indirizzo specifico di studio. L’attualità del tema è recentemente riemersa a livello internazionale sull’onda della discussione attorno al computational thinking, il pensare in termini di elaborazione di informazioni, che tra l’altro ha determinato importanti interventi nei curricula di alcuni paesi europei. In queste pagine vorrei quindi condividere con il lettore alcune riflessioni, e stimolarne di sue personali, che mi auguro possano contribuire a vedere l’informatica nella scuola in una prospettiva più articolata, anche e specialmente da parte di insegnanti che hanno una diversa formazione culturale, scientifica o umanistica, ma che comunque si devono confrontare con essa in ragione della pervasività degli strumenti che ne applicano i principi..
Is iteration really easier to master than recursion? an investigation in a functional-first CS1 context
No full textDespite a general consensus on the difficulties faced to master recursion, a two-year investigation on the achievements in a 'functional-first' introductory course does not corroborate the hypothesis that students are more at ease with iteration than they are with recursion
Mental Models of Recursive Computations vs. Recursive Analysis in the Problem Domain
No full textThe work outlined here was inspired by a related one, where the authors analyze the mental models of recursion by looking at how students trace simple recursive computations. Besides trying to understand if their results generalize to a different context, I was interested to see the correlations between the mental models of the computation process and the ability to establish recursive relationships in the problem domain. My investigation essentially lends further support to those above findings. However, a consistent mental model of recursive computations, although implied by the ability to use recursion in problem-solving, does not seem to be suffcient for the achievement of this higher-level skill
Learning (through) recursion: a multidimensional analysis of the competences achieved by CS1 students
No full textIn this paper I will discuss an investigation intended to address the learning of recursion in a multidimensional perspective, where the dimensions correspond to different types of competence relevant to programming. One such dimension is the understanding of the computation model, that I have assessed under the methodology proposed by Goetschi et al. (2003). Moreover, I have tried to analyze and correlate other learning dimensions, such as the ability to establish relations in the problem domain, to deal with recursive structures, as well as to develop basic abstraction skills. One of my objectives is indeed to gain a better understanding of the major sources of difficulties that students face. In essence, my investigation lends further support to previous related findings on mental models. However, a consistent model of recursive computations, although implied by the ability to use recursion in problem-solving, does not seem to be sufficient for the achievement of higher-level skills
A Practical Motion Planning Strategy Based on a Plane-Sweep Approach
No full textWe discuss a practical motion planning strategy based on a two-step approach. First, an approximation of the C-space is built by a plane-sweep algorithm. Then, the search for a solution path drives the necessary refinement steps. Our claim is that an approach based on the incremental characterization of the C-space can be competitive with the best proposed motion planning techniques. We substantiate this claim in the simple case of planning translations of a convex body in the plane. Since the shape of the free space is incrementally recognized by probing the space via collision detection, every item of geometric information is obtained from the analysis of contact configurations involving convex bodies. At any stage the probes provide a partial characterization, represented by a simple cell subdivision and a suitable set of chains approximating the boundaries of the grown obstacles. The cells and their adjacencies do not change during the refinement step, so that the search strategy is straightforward. Although the performances are not optimal in theory, the planning algorithm shows a good behaviour, as demonstrated by a few experiments where it is compared with a quadtree-based strategy
Numeri e Macchine: Un museo virtuale per apprendere la storia dell'informatica
No full textQuesto articolo si propone di illustrare il progetto e la realizzazione di un museo virtuale sulla storia dell’informatica. ll lavoro nasce dall’esperienza maturata negli allestimenti della mostra “Numeri e Macchine” a Udine e si inserisce in un momento di crescente attenzione per la radici storiche dell’informatica. Infatti, in ambito scolastico e universitario ormai si riconosce che una riflessione in
chiave storica può favorire un atteggiamento critico da parte dei sempre più numerosi utenti del computer.
I vari aspetti del progetto sono stati affrontati facendo riferimento a due obiettivi principali. Da un lato si è inteso cogliere le potenzialità offerte dalla multimedialità e dall’interattività al fine di sviluppare un ambiente di apprendimento che si caratterizzi per ricchezza di stimoli e per un coinvolgimento attivo del visitatore, attraverso azioni che vanno da semplici manipolazioni di oggetti fino alla sperimentazione di alcuni dispositivi di calcolo, contribuendo così a mantenere vivi interesse e motivazione anche nei giovani allievi. D’altro lato si è cercato di realizzare un’architettura che si presenti come un sistema aperto in grado di evolvere nel tempo, dotato quindi della flessibilità necessaria a definire nuovi percorsi di visita, adattabili a diverse esigenze didattiche o divulgative.
La versione corrente del museo virtuale, basata sugli strumenti DHTML e consultabile direttamente tramite browser, è disponibile su CD-ROM ed è stata utilizzata in alcune sperimentazioni didattiche
Storia dell'informatica e formazione culturale degli studenti
No full textL'Universita' di Udine aderisce all'iniziativa "Corsi AICA", volta a promuovere l'insegnamento della storia dell'informatica. Questo articolo presenta un'analisi condotta sugli esiti delle prove d'esame con l'obiettivo di esplorare la formazione culturale degli studenti. Dalle prime osservazioni emerge una fragile prospettiva storica, in particolare per quanto riguarda l'evoluzione della scienza, che rende loro difficile trasformare la spontanea curiosita' per gli artefatti tecnologici in un piu' maturo interesse per gli sviluppi del pensiero e della societa' che li hanno resi possibili
Fast convex minimization to detect collisions between polyhedra
No full textThe subject of this paper is a fast algorithm for detecting collisions of two convex polyhedra translating in the space. A major feature is the novelty of the approach: collision detection for two convex bodies is reduced to collision detection for pairs of planar sections and minimization of a bivariate convex function; furthermore, most of the subproblems are solved using two-dimensional geometry. As proved by previous theoretical work, on this basis it is possible to design an algorithm, which runs in O(log^2n) time in the average and O(log^3n) in the worst case, where n is the total number of vertices. Here the focus is on a more practical version of the algorithm, which is particularly suited to plan collision-free paths on the basis of fine-grain descriptions of the objects in the workspace, as it is the case for the systems supported by sophisticated geometric modelers. After explaining the main ideas underlying the approach, a set of experimental results are presented and discussed in some depth
- …
