111 |
Sudoku puzzles και συνδυαστικά προβλήματαΖώττου, Δήμητρα Νεφέλη 06 December 2013 (has links)
Στην παρούσα εργασία προσεγγίζονται τα Sudoku puzzles χρησιμοποιώντας
μαθηματικές έννοιες κυρίως από την θεωρία γραφημάτων, την άλγεβρα, τη θεωρία
πινάκων αλλά και την κρυπτογραφία και τη θεωρία ανάπτυξης αλγορίθμων, oυσιαστικά
χρησιμοποιούνται διάφορες οπτικές γωνίες προκειμένου να απεικονιστεί η μελέτη
αυτών των puzzles μέσω των μαθηματικών.
Η εργασία χωρίζεται σε έξι βασικά κεφάλαια:
Το πρώτο κεφάλαιο περιέχει βασικές έννοιες της άλγεβρας και της θεωρίας
γραφημάτων, όπως ο ορισμός της ομάδας, του συνεκτικού γραφήματος, ο βαθμός
κορυφής και άλλα, οι οποίες χρησιμοποιούνται επανειλημμένα στην εργασία, έτσι ώστε
να μπορεί να γίνει κατανοητή χωρίς να απαιτείται η χρήση άλλων επιστημονικών
πηγών. Χωρίζεται σε τέσσερεις βασικές ενότητες οι οποίες παρουσιάζονται με την
ακόλουθη σειρά. Η πρώτη ενότητα είναι οι Βασικές Έννοιες Γραφημάτων, η οποία
ουσιαστικά αναφέρεται στην βασική ορολογία των γραφημάτων. Η δεύτερη ενότητα
είναι τα Βασικά Είδη Γραφημάτων και περιέχει γραφήματα με συγκεκριμένα
χαρακτηριστικά και ιδιότητες, οι οποίες είναι απαραίτητες για την ανάλυση της παρούσας εργασίας. Στη συνέχεια η τρίτη ενότητα είναι οι Βασικές Έννοιες Γραμμικής
Άλγεβρας, η οποία περιέχει συγκεκριμένους ορισμούς κυρίως των ομάδων και των
συμμετριών που χρησιμοποιούνται για την απαρίθμηση των Sudoku. Τέλος η τελευταία
ενότητα είναι οι Αλγεβρικές Ιδιότητες Γραφημάτων, η οποία περιέχει ορισμούς και
αλγεβρικές αλληλεπιδράσεις πάνω στα γραφήματα. Για περισσότερες λεπτομέρειες
σχετικά με την άλγεβρα και τη θεωρία γραφημάτων, παραπέμπουμε στα [6], [7] και [29].
Το δεύτερο κεφάλαιο περιέχει τους ορισμούς του Sudoku puzzle και των
λατινικών τετραγώνων, τα οποία είναι μια γενίκευση των Sudoku puzzles, όπως θα
αναφερθεί παρακάτω. Για εκτενέστερη έρευνα πάνω στα λατινικά τετράγωνα
παραπέμπουμε στα [3], [10], [11], [12],[13], [15], [16], [17], [18] και [29].
Στο τρίτο κεφάλαιο απαριθμούνται οι κλάσεις ισοδυναμίας των λατινικών
τετραγώνων αρχικά και στη συνέχεια γίνεται απαρίθμηση τριών ειδών Sudoku puzzles,
τα οποία είναι τα junior Sudoku puzzles τάξης 44, τα Sudoku puzzles τάξης 9x9 και
τα 2-Quasi-μαγικά Sudoku, τα οποία έχουν έναν παραπάνω περιορισμό σε σχέση με τα
συνήθη Sudoku. Τέλος, απαριθμούνται οι συμμετρίες των Sudoku puzzles τάξης 9x9 και
γίνεται μια σύντομη ανάλυση των μητρώων μετάθεσής τους. Περαιτέρω πληροφορίες
βρίσκονται στα [1], [2], [4], [5], [9], [14], [19], [20], [21], [22], και [26].
Στο τέταρτο κεφάλαιο αλλάζει η αυστηρά αλγεβρική προσέγγιση που υπάρχει
στις παραπάνω ενότητες. Εδώ παρουσιάζεται το Sudoku puzzle με μια ισοδύναμη
μορφή γραφήματος και γίνεται μια σύντομη παρουσίαση βασικών εννοιών της
κρυπτογραφίας, καθώς και μια θεωρητική προσέγγιση της κρυπτογράφησης του
Sudoku puzzle, με τη βοήθεια του πρωτοκόλλου της μηδενικής γνώσης. Περαιτέρω
πληροφορίες βρίσκονται στα [8], [23] και [24].
Στο πέμπτο κεφάλαιο αλλάζει πάλι ο επιστημονικός κλάδος, μέσω του οποίου
εξετάζουμε τα Sudoku puzzles και επικεντρώνεται στην απεικόνιση ενός στιγμιοτύπου
του puzzle Sudoku σε ένα στιγμιότυπο του προβλήματος SAT. Όλοι οι περιορισμοί του
Sudoku θα μπορέσουν να διατηρηθούν μέσω των κανονικών συζευκτικών προτάσεων
του προβλήματος SAT, οι οποίες έχουν χωριστεί σε πέντε ενότητες. Η καταμέτρηση των
κανονικών συζευκτικών προτάσεων του προβλήματος SAT μέσω αναδρομικών τύπων,
αποτελεί το πρωτότυπο τμήμα της διπλωματικής καθώς και η ανάλυση των τύπων
αυτών, την οποία περιέχει το επισυναπτόμενο CD. Για πιο θεωρητική προσέγγιση
προτείνονται τα [25], [26], [27], [30].
Το έκτο κεφάλαιο της εργασίας περιέχει μια διασκεδαστική εφαρμογή
κρυπτογράφησης οποιουδήποτε Sudoku puzzle τάξης 99 . Η εφαρμογή υλοποιείται με
τραπουλόχαρτα, έτσι ώστε ο αναγνώστης να είναι σε θέση να κρυπτογραφήσει
οποιοδήποτε λύση puzzle Sudoku, χωρίς να είναι υποχρεωμένος να παρουσιάσει τη
λύση του στον αντίπαλο, χρησιμοποιώντας μόνο τρείς τράπουλες. Ο στόχος του τελευταίου κεφαλαίου είναι να κάνει τον επίλογο της εργασίας πιο ευχάριστο και πιο
ανάλαφρο ακόμα και για νέους επιστήμονες στο χώρο της κρυπτογραφίας, της θεωρίας
γραφημάτων και της άλγεβρας. / The essay is about the complexity of the Sudoku puzzles and how you can numarated them.
|
112 |
Low-Complexity Perceptual JPEG2000 Encoder for Aerial ImagesOh, Han, Kim, Yookyung 10 1900 (has links)
ITC/USA 2011 Conference Proceedings / The Forty-Seventh Annual International Telemetering Conference and Technical Exhibition / October 24-27, 2011 / Bally's Las Vegas, Las Vegas, Nevada / A highly compressed image inevitably has visible compression artifacts. To minimize these artifacts, many compression algorithms exploit the varying sensitivity of the human visual system (HVS) to different frequencies. However, this sensitivity has typically been measured at the near-threshold level where distortion is just noticeable. Thus, it is unclear that the same sensitivity applies at the supra-threshold level where distortion is highly visible. In this paper, we measure the sensitivity of the HVS for several supra-threshold distortion levels based on our JPEG2000 distortion model. Then, a low-complexity JPEG2000 encoder using the measured sensitivity is described. For aerial images, the proposed encoder significantly reduces encoding time while maintaining superior visual quality compared with a conventional JPEG2000 encoder.
|
113 |
ADAPTATIONAL FLEXIBILITY AND PROCESSES OF EMERGING COMPLEXITY: EARLY TO MID-HOLOCENE FORAGERS IN THE LOWER JEQUETEPEQUE VALLEY, NORTHERN PERUStackelbeck, Kary L. 01 January 2008 (has links)
Early complex societies developed in the Central Andes as a result of in situ processes of culture change. However, the developments commonly associated with complex societiespermanent village settlement, monumental architecture, intensive agriculture, and institutionalized stratificationwere neither uniformly nor simultaneously adopted. Rather, they appear to have been the result of different trajectories that initially were tied to changes among populations in certain circumscribed areasoften within individual valley systems. This dissertation explores the cultural and historical contexts of emerging complexity in one such areathe lower Jequetepeque Valley in northern Peru. This area encompasses several quebrada drainages and associated landforms along the lower, western flanks of the Andes, which were the focus of intensive Preceramic occupation (~11,000-4000 14C BP). The Preceramic Period correlates with the transition from the Terminal Pleistocene to the mid-Holocene, which involved changes in the local environment from cooler, wetter conditions to warmer, drier conditions that approximate the modern arid setting. Despite these deteriorating conditions, transitional late Early through Middle Preceramic (LE/M) populations (~9000-4500 14C BP) continued to occupy the project areawith some adjustments compared to their Paijanense predecessors (~11,000-9000 14C BP)based on survey and excavation data from 138 sites. These data consist of faunal remains, lithic tools and debris, hearth features, land snail middens, limited paleobotanical remains, and remnants of simple domestic structures and two possible rudimentary canals. Analyses of these data indicate that LE/M populations had intensified the localization of their settlement and subsistence patterns, and transformed their use and materialization of certain spaces to which they had become tethered. Taken collectively with evidence of Early through Middle Preceramic occupation in the nearby Zana and Chicama Valleys, the regional patterns observed among these three drainages indicate that a broad-spectrum diet, territoriality, ritualistic activities, and the separation of public and private spheres of activity preceded the adoption of intensive agriculture, socio-economic stratification, and the construction of large-scale monumental architecture, among other, more recognizable markers of cultural complexity. Further, these patterns indicate that Preceramic populations in this region actively negotiated changes in their local environment and social landscape by employing strategies of adaptational flexibility.
|
114 |
MID-HOLOCENE EMERGENT COMPLEXITY AND LANDSCAPE TRANSFORMATION: THE SOCIAL CONSTRUCTION OF EARLY FORMATIVE COMMUNITIES IN URUGUAY, LA PLATA BASINIriarte, José 01 January 2003 (has links)
This dissertation is a multidisciplinary study combining both archaeological andpaleoecological data to examine the rise of early Formative societies in Uruguay, La Plata Basin.It is contextualized within broader anthropological concerns related to the emergence of culturalcomplexity, the significance of ritual and public architecture in intermediate-level societies, andthe role of human-environment interactions during the mid-Holocene. This investigationgenerated the first Late Quaternary paleoclimatic record, based on pollen and phytolith analyses,documenting that the mid-Holocene (ca. 6,620 to ca. 4,040 bp) was a period of environmentalflux and increased aridity. It describes the occupational history of the Los Ajos site from thecreation of a household-based community integrating a centralized communal space during thePreceramic Mound Component (ca. 4,120 – 3,000- 2,500 bp) to the Ceramic Mound Component(ca. 3,000 2,500 bp to the Contact Period), where Los Ajos acquired a strong public ritualcharacter through the formatilization and spatial segregation of its mounded architecture. Duringthe Ceramic Mound Period, the site exhibited both internal stratification (inner versus outerprecincts) and dual asymmetrical architecture in its central sector, which suggest the emergenceof incipient social differentiation. This study also marks the earliest occurrence of at least twodomesticated crops in the region: corn (Zea mays) and squash (Cucurbita spp.), showing that theearly Formative societies adopted a mixed economy shortly after 4,120 bp. Collectively, theseresults challenge the long-standing view that the La Plata Basin was a marginal area byevidencing an early and idiosyncratic emergence of social complexity never before registered inthis region of South America.
|
115 |
Evolution of structure-function relationships in the GFP-family of proteinsModi, Chintan Kishore 16 September 2014 (has links)
One of the most intriguing questions in evolutionary biology is how biochemical and structural complexity arise through small and incremental changes; however answering this question requires an explicit set of candidate residues and an experimental system in which to test them. This dissertation aims to understand how biochemical complexity evolves and assesses the structure-function relationship in the green fluorescent protein (GFP) protein family using an ancestral reconstruction approach. In the second chapter, I studied the evolution of biochemical complexity in Kaede-type red fluorescent proteins (FPs) from Faviina corals. An increase in biochemical complexity is represented by the emergence of red fluorescence because it necessitates the synthesis of a tri-cyclic chromophore from a precursor bi-cyclic chromophore through an additional autocatalytic reaction step. The autocatalytic reaction is fully enabled by as many as twelve historical mutations. Here, I showed that the red fluorescent chromophore evolved from an ancestral green chromophore by perturbing the ancestral protein stability at multiple levels of protein structure. Moreover, only three historical mutations are sufficient to initiate the selection-accessible evolutionary trajectory leading to emergence of red fluorescence. The third chapter investigates six mutations proximate to the chromophore in the Kaede-type FP that could have facilitated autocatalytic synthesis of the red chromophore by enlarging the chromophore-containing cavity and modifying its microenvironment. Two of these six mutations were found to strongly affect the protein’s stability and oligomeric tendency. Additionally, I showed that the dimeric least divergent Kaede-type FP, R1-2, evolved from the tetrameric green ancestor. Taken together the results of these studies indicate that the step-up in biochemical complexity in the Kaede-type FPs was achieved via disruption of the existing stable interactions at tertiary and quaternary protein structure levels. In the fourth chapter, I resurrected the common ancestor of all FPs cloned from the order Leptothecata (class Hydrozoa), which are characterized by the highest known homo-oligomeric diversity. I showed that the ancestor was a green monomeric FP with a large Stokes shift. The ancestral FP together with the extant Leptothecata FPs could server as a model system to study the evolution of function and homo-oligomerization, and the desirable photophysical characteristics would make this ancestral FP a useful bio-marker in bio-medical research. / text
|
116 |
Language applications for UEFI BIOSLeara, William Daniel 06 October 2014 (has links)
The Unified Extensible Firmware Interface (UEFI) is the industry-standard Basic Input/Output System (BIOS) firmware specification used by modern desktop, portable, and server computers, and is increasingly being ported to today's new mobile form factors as well. UEFI is firmware responsible for bootstrapping the hardware, turning control over to an operating system loader, and then providing runtime services to the operating system. ANTLR (ANother Tool for Language Recognition) is a lexer-parser generator for reading, processing, executing, and translating structured text and binary files. It supersedes older technologies such as lex/yacc or flex/bison and is widely used to build languages and programming tools. ANTLR accepts a provided grammar and generates a parser that can build and walk parse trees. This report studies UEFI BIOS and compiler theory and demonstrates ways compiler theory can be leveraged to solve problems in the UEFI BIOS domain. Specifically, this report uses ANTLR to implement two language applications aimed at furthering the development of UEFI BIOS implementations. They are: 1. A software complexity analysis application for UEFI created that leverages ANTLR's standard general-purpose C language grammar. The complexity analysis application uses general-purpose and domain-specific measures to give a complexity score to UEFI BIOS modules. 2. An ANTLR grammar created for the VFR domain-specific language, and a sample application which puts the grammar to use. VFR is a language describing visual elements on a display; the sample application creates an HTML preview of VFR code without requiring a developer to build and flash a BIOS image on a target machine to see its graphical layout. / text
|
117 |
Symmetry and shape analysis for assembly-oriented CADTate, Susan J. January 2000 (has links)
No description available.
|
118 |
Dynamics of conventions : a post-classical analysisAndrade, Rogerio Pereira de January 1998 (has links)
No description available.
|
119 |
Mossy Oak Revisited: A Case Study in Mississippian CeramicsCadwell, Lillian 12 August 2014 (has links)
The research presented here seeks to better understand the relationship between the Macon Plateau site and Mossy Oak ceramics. The Early Mississippian period in central Georgia was a time of great change with emerging political centralization and social ranking. This thesis aims to better understand Macon Plateau’s relationship with outlying areas. To accomplish this objective the ceramic assemblage site from the site of Mossy Oak (11 Bi 17) is revisited and reanalyzed using spatial analysis and detailed investigations of Vining Simple Stamped pottery. Rather than taking a top-down, elite-focused approach, this thesis explores the impact of horizontal relationships between groups present at the inception of social institutions and social inequality at the dawn of the Early Mississippian and the rise of Macon Plateau.
|
120 |
Complexity, aftershock sequences, and uncertainty in earthquake statisticsTouati, Sarah January 2012 (has links)
Earthquake statistics is a growing field of research with direct application to probabilistic seismic hazard evaluation. The earthquake process is a complex spatio-temporal phenomenon, and has been thought to be an example of the self-organised criticality (SOC) paradigm, in which events occur as cascades on a wide range of sizes, each determined by fine details of the rupture process. As a consequence, deterministic prediction of specific event sizes, locations, and times may well continue to remain elusive. However, probabilistic forecasting, based on statistical patterns of occurrence, is a much more realistic goal at present, and is being actively explored and tested in global initiatives. This thesis focuses on the temporal statistics of earthquake populations, exploring the uncertainties in various commonly-used procedures for characterising seismicity and explaining the origins of these uncertainties. Unlike many other SOC systems, earthquakes cluster in time and space through aftershock triggering. A key point in the thesis is to show that the earthquake inter-event time distribution is fundamentally bimodal: it is a superposition of a gamma component from correlated (co-triggered) events and an exponential component from independent events. Volcano-tectonic earthquakes at Italian and Hawaiian volcanoes exhibit a similar bimodality, which in this case, may arise as the sum of contributions from accelerating and decelerating rates of events preceding and succeeding volcanic activity. Many authors, motivated by universality in the scaling laws of critical point systems, have sought to demonstrate a universal data collapse in the form of a gamma distribution, but I show how this gamma form is instead an emergent property of the crossover between the two components. The relative size of these two components depends on how the data is selected, so there is no universal form. The mean earthquake rate—or, equivalently, inter-event time—for a given region takes time to converge to an accurate value, and it is important to characterise this sampling uncertainty. As a result of temporal clustering and non-independence of events, the convergence is found to be much slower than the Gaussian rate of the central limit theorem. The rate of this convergence varies systematically with the spatial extent of the region under consideration: the larger the region, the closer to Gaussian convergence. This can be understood in terms of the increasing independence of the inter-event times with increasing region size as aftershock sequences overlap in time to a greater extent. On the other hand, within this high-overlap regime, a maximum likelihood inversion of parameters for an epidemic-type statistical model suffers from lower accuracy and a systematic bias; specifically, the background rate is overestimated. This is because the effect of temporal overlapping is to mask the correlations and make the time series look more like a Poisson process of independent events. This is an important result with practical relevance to studies using inversions, for example, to infer temporal variations in background rate for time-dependent hazard estimation.
|
Page generated in 0.4365 seconds