1,721,147 research outputs found
L'informatica invisibile. Come gli algoritmi regolano la nostra vita...e tutto il resto
No full textAnche se la nascita degli algoritmi si può far risalire a circa il 2000 a.C., datazione delle tavolette mesopotamiche e dei papiri egiziani riportanti i primi esempi di procedimenti di calcolo, la definizione formale del concetto di algoritmo ha cominciato ad essere approfondita solo nel XX secolo ed ha costituito una premessa indispensabile per la realizzazione del primo calcolatore elettronico programmabile e dei primi linguaggi di programmazione. Oggi è facile affermare che gli algoritmi caratterizzano molti aspetti della nostra vita quotidiana. La prenotazione di un posto in aereo, l’effettuazione di una transazione sicura ad uno sportello bancario elettronico, la ricerca di informazioni nel web, la sicurezza della firma elettronica, la compressione o decompressione di file di musica o immagini sono solo alcuni esempi della pervasività degli algoritmi nella nostra vita quotidiana. Però, nonostante questa massiccia presenza degli algoritmi nelle applicazioni a noi più familiari, il loro ruolo e la loro rilevanza ai fini di garantire le prestazioni delle applicazioni stesse sono ignorati dalla maggior parte degli utenti o, nella migliore delle ipotesi, considerati solo come aspetti tecnici di poca rilevanza. In questo volume si vuole colmare questa lacuna conoscitiva presentando una serie di applicazioni che incontriamo quotidianamente nello svolgimento delle nostre attività di lavoro o di svago, mettendo in evidenza per ciascuna di esse le tecniche algoritmiche utilizzate, le loro basi concettuali e scientifiche e come esse siano determinanti per la validità delle applicazioni affrontate
Theoretical Computer Science in Italy: The Early Years
No full textIn this article, we provide an overview of the early developments of theoretical computer science research in Italy in the Sixties and early Seventies. In the same years, the community of researchers working in this domain were organizing to gain an identity among the more traditional disciplines and to obtain a recognition for the "new science" that was taking its first steps. This led in Italy to the creation of Group of Researchers in Theoretical Informatics, in parallel to the institution of European Association for Theoretical Computer Science at European level. In this article, we characterize the Italian contribution to theoretical computer science research in those early years by describing the landscape of activities developed in Italian Universities and research centers in the late sixties and early seventies, on the basis of a census run in 1971 by the newly born GRIT
Structure Preserving Reductions Among Convex Optimization Problems
No full textAbstractIn this paper we introduce the concept of convex optimization problem. Convex optimization problems are studied by giving a formalization of the concept of combinatorial structure, in terms of spectra of approximate solutions, and of reduction which preserves such structure. On this basis a classification of convex NP-optimization problems is introduced and is applied to study the combinatorial structure of several optimization problems associated to well-known NP-complete sets. Conditions on the approximability of such optimization problems are also given and it is shown that structurally isomorphic problems have similar approximability properties
PROTECTION OF THE TERRACED LANDSCAPE BETWEEN RURAL CULTURE, CLIMATE RESILIENCE AND BIODIVERSITY,LA TUTELA DEL PAESAGGIO TERRAZZATO TRA CULTURA RURALE, RESILIENZA CLIMATICA E BIODIVERSIT?
No full textThe protection of terraced landscapes is an objective that has gained the greatest attention after the recognition of dry stone walls as intangible Unesco in 2018. The starting point is the knowledge that starts from the analysis of the meaning and formal values that the types of walls introduce in morphologically complex landscapes. An ideal cognitive path follows, the awareness of the dry masonry technique and the numerous advantages it introduces to the environmental scale, up to the safeguarding of biodiversity. The experience and the proactive aspects gained in some related contexts is an important reflection which, compared to the cognitive phase, is configured as the keystone for identifying permanent guidelines in the protection interventions of the terraces that constitute a great heritage of our country
The on-line asymmetric traveling salesman problem
No full textWe consider two on-line versions of the asymmetric traveling salesman problem with triangle inequality. For the homing version, in which the salesman is required to return in the city where it started from, we give a frac(3 + sqrt(5), 2)-competitive algorithm and prove that this is best possible. For the nomadic version, the on-line analogue of the shortest asymmetric Hamiltonian path problem, we show that the competitive ratio of any on-line algorithm depends on the amount of asymmetry of the space in which the salesman moves. We also give bounds on the competitive ratio of on-line algorithms that are zealous, that is, in which the salesman cannot stay idle when some city can be served. © 2007 Elsevier B.V. All rights reserved
The online Prize-Collecting Traveling Salesman Problem
Full text linkWe study the online version of the Prize-Collecting Traveling Salesman Problem (PCTSP), a generalization of the Traveling Salesman Problem (TSP). In the TSP, the salesman has to visit a set of cities while minimizing the length of the overall tour. In the PCTSP, each city has a given weight and penalty, and the goal is to collect a given quota of the weights of the cities while minimizing the length of the tour plus the penalties of the cities not in the tour. In the online version, cities are disclosed over time. We give a 7/3-competitive algorithm for the problem, which compares with a lower bound of 2 on the competitive ratio of any deterministic algorithm. We also show how our approach can be combined with an approximation algorithm in order to obtain an O (1)-competitive algorithm that runs in polynomial time. © 2008 Elsevier B.V. All rights reserved
Processi digitali per la riqualificazione dell’edilizia scolastica: l’Istituto Comprensivo Marino - Santa Rosa a Ponticelli (NA)
No full text- …
