No description available.

No description available.

Eva Novozámská Dynamics of moss overgrowth in ditches in restorated drained mires in area of Modrava bogs (Šumava NP) Abstract This thesis is devoted to a research of induced and natural Sphagnum overgrowth in dammed ditches in restorated drained mires of Šumava National Park within the "Programme of Peatland restoration". Induced overgrowth was studied on the peatlands Cikánská slať, Luzenská slať and Novohuťské močály and 36 permanent experimental sites were established for its study. In 2006 Sphagnum fallax or Sphagnum majus were placed in each site in dependence on the type of locality. For four years increase or decrease of Sphagnum were monitored. The study of natural overgrowth was investigated on the same localities as induced overgrowth. The Sphagnum cover was noted in the year 2009 at 65 sites. The depth of the ditch and the flow of water were the most important variables influencing natural overgrowth and the cover was almost the same on all localities. In the case of induced overgrowth the most important parameters were depth and width of the ditch, amount of the branch support and the interaction of depth and width. The depth of the ditch in the case of natural overgrowth was used to generate a model for prediction of Sphagnum cover. It was possible to compare the induced overgrowth with the...

The thesis deals with the evaluation of habitat preferences of the red deer in the Krkonoše National Park. In the context of Central Europe, the Krkonoše Mountains are an important locality in which many rare and protected ecosystems are located. The current management is trying to restore the species composition of the forest, which was abundant in the past and replaced by atypical spruce species. Red deer (Cervus elaphus), which lives in these forests, has no natural enemy in the Giant Mountains, so it is necessary to control the local population and perform selective management for the purpose of forest protection. For proper management planning it is important to know the life strategies of the red deer: the deer's preffered habitat, physical-geographical characteristics that affect its movement and spatio- temporal use of the area. This information can be obtained through GPS-telemetry collar monitoring. The monitoring campaign in the Giant Mountains was carried out between 2014 and 2018 and the resulting data are used in this work. Information on 71 individuals of red deer are processed and subjected to spatio-temporal analysis, which shows that deer behavior is influenced by both daily and annual cycles. Another aspect influencing its movement is the density and intensity of the use of...

Η παρούσα εργασία έχει σαν στόχο την ανάλυση ενός προβλήματος δρομολόγησης το οποίο στη βάση του έχει ως εξής: Δίνεται ακολουθία διεργασιών που πρόκειται να δοθεί για επεξεργασία σε ένα σύνολο μηχανών. Η κάθε διεργασία χαρακτηρίζεται από το χρόνο επεξεργασίας της και θα πρέπει να δρομολογηθεί σε κάποια απ' τις μηχανές για χρόνο τουλάχιστον ίσο με αυτό. Επιπλέον υπάρχει απαίτηση από ένα υποσύνολο διεργασιών για επιτάχυνση. Το ζητούμενο είναι να δοθεί αλγόριθμος που δρομολογεί τις διεργασίες στις μηχανές ελαχιστοποιώντας κάποια μετρική απόδοσης, παράλληλα με την εξυπηρέτηση όσο το δυνατόν περισσότερων αιτήσεων για επιτάχυνση. Στα πλαίσια ενός εισαγωγικού κεφαλαίου δίνεται θεωρητικό υπόβαθρο που αφορά σε προβλήματα και αλγορίθμους δρομολόγησης, σημειώνοντας ιδιαίτερα τη διαφορά μεταξύ στατικών και δυναμικών αλγορίθμων. Αντικείμενο της εργασίας αυτής γίνεται στη συνέχεια η μελέτη του παραπάνω προβλήματος, σε περιβάλλον μιας μηχανής και σε παραλλαγές του οι οποίες σχετίζονται με παραμέτρους, όπως για παράδειγμα, προθεσμίες ολοκλήρωσης. Αποτέλεσμα της μελέτης αυτής είναι η ανάπτυξη, αλλά και η αξιολόγηση αποτελεσματικών μεθόδων επίλυσης, χρησιμοποιώντας γνωστά κριτήρια βελτιστοποίησης όπως ο χρόνος που απαιτείται για την ολοκλήρωση των διεργασιών, αλλά και κάποιες νέες μετρικές που συστήνονται και η ανάγκη τους επεξηγείται αναλυτικά. Τέλος στο τρίτο κεφάλαιο γίνεται επισκόπηση προβλημάτων που αφορούν δρομολόγηση σε περισσότερες από μία μηχανές. Τα προβλήματα αυτά ενώ αποδεικνύονται ΝΡ-πλήρη, οι αποδείξεις παραλείπονται και δίδονται παρατηρήσεις για την πολυπλοκότητα παραλλαγών τους. Η εργασία κλείνει με μια παρουσίαση της υπολογιστικής μεθόδου του δυναμικού προγραμματισμού, που γίνεται προσπάθεια να εφαρμοστεί σε προβλήματα δρομολόγησης. / The purpose of the present study is to analyze a scheduling problem, the def- inition of which is: We are given a sequence of tasks that are to be processed on a set of machines. Each task is characterized by its running time and has to be scheduled on a machine, for at least its running time. In addition, there are speedup requests from a subset of tasks. The scheduling algorithm is asked to produce a schedule that minimizes an objective function in par- allel with serving as many as possible speedup requests. The introduction gives a theoretical background concerning scheduling prob- lems and algorithms, with an emphasis on the di_erence between static and dynamic algorithms. The objective of the second chapter, is to study the problem above, in its many variations, with a reference to parameters like the number of the machines, deadlines etc. The result of this study, is the development and the evaluation of two algorithms, using objective functions like makespan, and also some new ones that arise in the essay and their need is analyzed. The thesis closes with a consideration of already known schedul- ing problems and its variants, that have been proved to be NP-complete.

Title: The knapsack and its applications Author: Romana Linkeová Department: Department of Algebra Supervisor: doc. Mgr. Pavel Příhoda, Ph.D., Department of Algebra Abstract: This thesis is focused on various aspects of cryptosystems based on NP (non-deterministic polynomial) complete knapsack problem. From the theory of complexity point of view, the less known parts of the proof of knapsack problem NP completeness are shown in detail. From the cryptographical point of view, a demonstration of breaking of the Merkle-Hellman cryptosystem (the basic de- sign of knapsack-type cryptosystems) is provided, showing that poor parameters choice can lead to easy obtaining of the whole private key. Another contribution of this thesis consists in a presented proposal of a new cryptosystem concept based on the matrix 0-1 knapsack problem. This concept was developed in order to prevent known attacks, however, in the thesis we provide a proof analogous to J. C. Lagarias and A. M. Odlyzko, 1985, which shows that an attack based on the LLL algorithm will be successful on the majority of the matrix 0-1 kna- psack problem cryptosystems. Finally, a list of modern cryptosystems based on the knapsack problem is provided and a cryptanalysis thereof is given. Keywords: knapsack problem, NP complete problems, LLL algorithm 1

Based on the author's Ph. D. thesis, University of California, Berkeley, 1993. / Includes bibliographical references (p. [73]-78) and index. Also issued online.

Random NP-Complete problems have come under study as an important tool used in the analysis of optimization algorithms and help in our understanding of how to properly address issues of computational intractability. In this thesis, the Number Partition Problem and the Hamiltonian Cycle Problem are taken as representative NP-Complete classes. Numerical evidence is presented for a phase transition in the probability of solution when a modified Lévy-Stable distribution is used in instance creation for each. Numerical evidence is presented that show hard random instances exist near the critical threshold for the Hamiltonian Cycle problem. A choice of order parameter for the Number Partition Problem’s phase transition is also given. Finding Hamiltonian Cycles in Erdös-Rényi random graphs is well known to have almost sure polynomial time algorithms, even near the critical threshold. To the author’s knowledge, the graph ensemble presented is the first candidate, without specific graph structure built in, to generate graphs whose Hamiltonicity is intrinsically hard to determine. Random graphs are chosen via their degree sequence generated from a discretized form of Lévy-Stable distributions. Graphs chosen from this distribution still show a phase transition and appear to have a pickup in search cost for the algorithms considered. Search cost is highly dependent on the particular algorithm used and the graph ensemble is presented only as a potential graph ensemble to generate intrinsically hard graphs that are difficult to test for Hamiltonicity. Number Partition Problem instances are created by choosing each element in the list from a modified Lévy-Stable distribution. The Number Partition Problem has no known good approximation algorithms and so only numerical evidence to show the phase transition is provided without considerable focus on pickup in search cost for the solvers used. The failure of current approximation algorithms and potential candidate approximation algorithms are discussed.

Given an undirected edge-weighted graph G and a positive integer m, the Constrained Forest Problem (CFP) seeks a lowest-cost (or minimum-weight) forest F which spans G while satisfying the requirement that each tree in F contain at least m vertices. This problem has been shown to be NP-hard for values of m greater than three, giving rise to a number of approximation strategies for finding reasonable m-forest solutions. This research presents a new genetic algorithm (GA) which can consistently find equal-or-better solutions to the problem when compared to non-genetic alternatives. This GA is unique in that it uses chromosomes which are actual candidate solutions (m-forests) and performs genetic operations (random creation, selection, recombination, and mutation) on these candidate solutions. Experiments were run using 180 different GA configurations on 50 benchmark graphs to determine which operators and techniques would be most successful in solving the m-forest problem. The "heaviest edge first" or HEF algorithm run against the minimum spanning tree (MST) of a graph was used as a performance metric. Previously, the HEF(MST) algorithm had been shown to produce the best results on m-forest problems. When the GA was able to find better results than HEF(MST) on the same problem instance, this was considered a GA success. Since the GA's initial population included heuristic candidate solutions such as HEF(MST), the GA never did worse than the best of these. GA solution quality did vary, however, often finding several different better-than-HEF(MST) solutions, illustrating the stochastic nature of the process. Based on data collected from the 9000 initial problem instances, several factors were shown to significantly improve the quality of the GA solution. Problem instances which did not include mutation had a much lower success rate than those which did. Adding calculated heuristic solutions such as HEF(MST) to the initial population allowed the GA to converge more quickly and improved its likelihood of finding better-than-HEF(MST) solutions. Building an initial population using randomly-generated candidate solutions whose edges were restricted to the problem graph's MST proved equally successful. GA configuration options were analyzed using all 9000 test cases and again using only those 403 cases in which the GA was able to find the very best solution for each graph. These analyses were consistent, and resulted in the identification of a single "best" GA configuration which combined the best overall initial population strategy, random seeding algorithms, mutation and crossover strategy. The selected configuration was then further tested using various values of m to ensure that the resulting GA could in fact find better-than-HEF(MST) solutions for the majority of problem instances.

We consider competitive location problems where two competing providers place their facilities sequentially and users can decide between the competitors. We assume that both competitors act non-cooperatively and aim at maximizing their own benefits. We investigate the complexity and approximability of such problems on graphs, in particular on simple graph classes such as trees and paths. We also develop fast algorithms for single competitive location problems where each provider places a single facilty. Voting location, in contrast, aims at identifying locations that meet social criteria. The provider wants to satisfy the users (customers) of the facility to be opened. In general, there is no location that is favored by all users. Therefore, a satisfactory compromise has to be found. To this end, criteria arising from voting theory are considered. The solution of the location problem is understood as the winner of a virtual election among the users of the facilities, in which the potential locations play the role of the candidates and the users represent the voters. Competitive and voting location problems turn out to be closely related. / Wir betrachten kompetitive Standortprobleme, bei denen zwei konkurrierende Anbieter ihre Versorger sequenziell platzieren und die Kunden sich zwischen den Konkurrenten entscheiden können. Wir nehmen an, dass beide Konkurrenten nicht-kooperativ agieren und auf die Maximierung ihres eigenen Vorteils abzielen. Wir untersuchen die Komplexität und Approximierbarkeit solcher Probleme auf Graphen, insbesondere auf einfachen Graphklassen wie Bäumen und Pfaden. Ferner entwickeln wir schnelle Algorithmen für kompetitive Einzelstandortprobleme, bei denen jeder Anbieter genau einen Versorger errichtet. Im Gegensatz dazu geht es bei Voting-Standortproblemen um die Bestimmung eines Standorts, der die Benutzer oder Kunden soweit wie möglich zufrieden stellt. Solche Fragestellungen sind beispielsweise bei der Planung öffentlicher Einrichtungen relevant. In den meisten Fällen gibt es keinen Standort, der von allen Benutzern favorisiert wird. Daher muss ein Kompromiss gefunden werden. Hierzu werden Kriterien betrachtet, die auch in Wahlsystemen eingesetzt werden: Ein geeigneter Standort wird als Sieger einer gedachten Wahl verstanden, bei der die möglichen Standorte die zur Wahl stehenden Kandidaten und die Kunden die Wähler darstellen. Kompetitive Standortprobleme und Voting-Standortprobleme erweisen sich als eng miteinander verwandt.