@phdthesis{Apfelbache2009, author = {Apfelbache, R{\´e}my}, title = {Tolerierbare Inkonsistenzen in Konzeptbeschreibungen}, address = {Potsdam}, pages = {iv, 182 S. : graph. Darst.}, year = {2009}, language = {de} } @unpublished{Arnold2009, author = {Arnold, Holger}, title = {A linearized DPLL calculus with clause learning (2nd, revised version)}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus-29080}, year = {2009}, abstract = {Many formal descriptions of DPLL-based SAT algorithms either do not include all essential proof techniques applied by modern SAT solvers or are bound to particular heuristics or data structures. This makes it difficult to analyze proof-theoretic properties or the search complexity of these algorithms. In this paper we try to improve this situation by developing a nondeterministic proof calculus that models the functioning of SAT algorithms based on the DPLL calculus with clause learning. This calculus is independent of implementation details yet precise enough to enable a formal analysis of realistic DPLL-based SAT algorithms.}, language = {en} } @article{BenderSteinert2009, author = {Bender, Katrin and Steinert, Markus}, title = {Ein handlungsorientiertes, didaktisches Training f{\"u}r Tutoren im Bachelorstudium der Informatik}, series = {Commentarii informaticae didacticae : (CID)}, journal = {Commentarii informaticae didacticae : (CID)}, number = {1}, issn = {1868-0844}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus-29690}, pages = {119 -- 130}, year = {2009}, abstract = {Die didaktisch-p{\"a}dagogische Ausbildung studentischer Tutoren f{\"u}r den Einsatz im Bachelorstudium der Informatik ist Gegenstand dieser Arbeit. Um die theoretischen Inhalte aus Sozial- und Lernpsychologie handlungsorientiert und effizient zu vermitteln, wird das Training als Lehrform gew{\"a}hlt. Die in einer Tutor{\"u}bung zentrale Methode der Gruppenarbeit wird dabei explizit und implizit vermittelt. Erste praktische Erfahrungen mit ihrer zuk{\"u}nftigen Rolle gewinnen die Tutoren in Rollenspielen, wobei sowohl Standardsituationen als auch fachspezifisch und p{\"a}dagogisch problematische Situationen simuliert werden. W{\"a}hrend die Vermittlung der genannten Inhalte und die Rollenspiele im Rahmen einer Blockveranstaltung vor Beginn des Semesters durchgef{\"u}hrt werden, finden w{\"a}hrend des Semesters Hospitationen statt, in der die F{\"a}higkeiten der Tutoren anhand eines standardisierten Bewertungsbogens beurteilt werden.}, language = {de} } @article{BenschBordihnHolzeretal.2009, author = {Bensch, Suna and Bordihn, Henning and Holzer, Markus and Kutrib, Martin}, title = {On input-revolving deterministic and nondeterministic finite automata}, issn = {0890-5401}, doi = {10.1016/J.Ic.2009.03.002}, year = {2009}, abstract = {We introduce and investigate input-revolving finite automata, which are (nondeterministic) finite state automata with the additional ability to shift the remaining part of the input. Three different modes of shifting are considered, namely revolving to the left, revolving to the right, and circular-interchanging. We investigate the computational capacities of these three types of automata and their deterministic variants, comparing any of the six classes of automata with each other and with further classes of well-known automata. In particular, it is shown that nondeterminism is better than determinism, that is, for all three modes of shifting there is a language accepted by the nondeterministic model but not accepted by any deterministic automaton of the same type. Concerning the closure properties most of the deterministic language families studied are not closed under standard operations. For example, we show that the family of languages accepted by deterministic right-revolving finite automata is an anti-AFL which is not closed under reversal and intersection.}, language = {en} } @article{BickelBruecknerScheffer2009, author = {Bickel, Steffen and Brueckner, Michael and Scheffer, Tobias}, title = {Discriminative learning under covariate shift}, issn = {1532-4435}, year = {2009}, abstract = {We address classification problems for which the training instances are governed by an input distribution that is allowed to differ arbitrarily from the test distribution-problems also referred to as classification under covariate shift. We derive a solution that is purely discriminative: neither training nor test distribution are modeled explicitly. The problem of learning under covariate shift can be written as an integrated optimization problem. Instantiating the general optimization problem leads to a kernel logistic regression and an exponential model classifier for covariate shift. The optimization problem is convex under certain conditions; our findings also clarify the relationship to the known kernel mean matching procedure. We report on experiments on problems of spam filtering, text classification, and landmine detection.}, language = {en} } @article{BickelBruecknerScheffer2009, author = {Bickel, Steffen and Br{\"u}ckner, Michael and Scheffer, Tobias}, title = {Discriminative learning under covariate shift}, issn = {1532-4435}, year = {2009}, abstract = {We address classification problems for which the training instances are governed by an input distribution that is allowed to differ arbitrarily from the test distribution-problems also referred to as classification under covariate shift. We derive a solution that is purely discriminative: neither training nor test distribution are modeled explicitly. The problem of learning under covariate shift can be written as an integrated optimization problem. Instantiating the general optimization problem leads to a kernel logistic regression and an exponential model classifier for covariate shift. The optimization problem is convex under certain conditions; our findings also clarify the relationship to the known kernel mean matching procedure. We report on experiments on problems of spam filtering, text classification, and landmine detection.}, language = {en} } @article{BieniusaDegenHeideggeretal.2009, author = {Bieniusa, Annette and Degen, Markus and Heidegger, Phillip and Thiemann, Peter and Wehr, Stefan and Gasbichler, Martin and Crestani, Marcus and Klaeren, Herbert and Knauel, Eric and Sperber, Michael}, title = {Auf dem Weg zu einer robusten Programmierausbildung}, series = {Commentarii informaticae didacticae : (CID)}, journal = {Commentarii informaticae didacticae : (CID)}, number = {1}, issn = {1868-0844}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus-29655}, pages = {67 -- 79}, year = {2009}, abstract = {Die gelungene Durchf{\"u}hrung einer Vorlesung „Informatik I - Einf{\"u}hrung in die Programmierung" ist schwierig, trotz einer Vielfalt existierender Materialien und erprobter didaktischer Methoden. Gerade aufgrund dieser vielf{\"a}ltigen Auswahl hat sich bisher noch kein robustes Konzept durchgesetzt, das unabh{\"a}ngig von den Durchf{\"u}hrenden eine hohe Erfolgsquote garantiert. An den Universit{\"a}ten T{\"u}bingen und Freiburg wurde die Informatik I aus den gleichen Lehrmaterialien und unter {\"a}hnlichen Bedingungen durchgef{\"u}hrt, um das verwendete Konzept auf Robustheit zu {\"u}berpr{\"u}fen. Die Grundlage der Vorlesung bildet ein systematischer Ansatz zum Erlernen des Programmierens, der von der PLTGruppe in USA entwickelt worden ist. Hinzu kommen neue Ans{\"a}tze zur Betreuung, insbesondere das Betreute Programmieren, bei dem die Studierenden eine solide Basis f{\"u}r ihre Programmierf{\"a}higkeiten entwickeln. Der vorliegende Bericht beschreibt hierbei gesammelte Erfahrungen, erl{\"a}utert die Entwicklung der Unterrichtsmethodik und der Inhaltsauswahl im Vergleich zu vorangegangenen Vorlesungen und pr{\"a}sentiert Daten zum Erfolg der Vorlesung.}, language = {de} } @article{Bobda2009, author = {Bobda, Christophe}, title = {Special issue on ReCoSoC 2007 : editorial}, issn = {0141-9331}, doi = {10.1016/j.micpro.2009.01.001}, year = {2009}, language = {en} } @article{BoernerBulatovChenetal.2009, author = {Boerner, Ferdinand and Bulatov, Andrei and Chen, Hubie and Jeavons, Peter and Krokhin, Andrei}, title = {The complexity of constraint satisfaction games and QCSP}, issn = {0890-5401}, doi = {10.1016/J.Ic.2009.05.003}, year = {2009}, abstract = {We study the complexity of two-person constraint satisfaction games. An instance of such a game is given by a collection of constraints on overlapping sets of variables, and the two players alternately make moves assigning values from a finite domain to the variables, in a specified order. The first player tries to satisfy all constraints, while the other tries to break at least one constraint: the goal is to decide whether the first player has a winning strategy. We show that such games can be conveniently represented by a logical form of quantified constraint satisfaction, where an instance is given by a first-order sentence in which quantifiers alternate and the quantifier-free part is a conjunction of (positive) atomic formulas; the goal is to decide whether the sentence is true. While the problem of deciding such a game is PSPACE-complete in general, by restricting the set of allowed constraint predicates, one can obtain infinite classes of constraint satisfaction games of lower complexity. We use the quantified constraint satisfaction framework to study how the complexity of deciding such a game depends on the parameter set of allowed predicates. With every predicate. one can associate certain predicate-preserving operations, called polymorphisms. We show that the complexity of our games is determined by the surjective polymorphisms of the constraint predicates. We illustrate how this result can be used by identifying the complexity of a wide variety of constraint satisfaction games.}, language = {en} } @article{BordihnHolzerKutrib2009, author = {Bordihn, Henning and Holzer, Markus and Kutrib, Martin}, title = {Determination of finite automata accepting subregular languages}, issn = {0304-3975}, doi = {10.1016/j.tcs.2009.05.019}, year = {2009}, abstract = {We investigate the descriptional complexity of the nondeterministic finite automaton (NFA) to the deterministic finite automaton (DFA) conversion problem, for automata accepting subregular languages such as combinational languages, definite languages and variants thereof, (strictly) locally testable languages, star-free languages, ordered languages, prefix-, suffix-, and infix-closed languages, and prefix-, Suffix-, and infix-free languages. Most of the bounds for the conversion problem are shown to be tight ill the exact number of states, that is, the number is sufficient and necessary in the worst case. Otherwise tight bounds in order of magnitude are shown.}, language = {en} } @phdthesis{Decker2009, author = {Decker, Gero}, title = {Design and analysis of process choreographies}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus-40761}, school = {Universit{\"a}t Potsdam}, year = {2009}, abstract = {With the rise of electronic integration between organizations, the need for a precise specification of interaction behavior increases. Information systems, replacing interaction previously carried out by humans via phone, faxes and emails, require a precise specification for handling all possible situations. Such interaction behavior is described in process choreographies. Choreographies enumerate the roles involved, the allowed interactions, the message contents and the behavioral dependencies between interactions. Choreographies serve as interaction contract and are the starting point for adapting existing business processes and systems or for implementing new software components. As a thorough analysis and comparison of choreography modeling languages is missing in the literature, this thesis introduces a requirements framework for choreography languages and uses it for comparing current choreography languages. Language proposals for overcoming the limitations are given for choreography modeling on the conceptual and on the technical level. Using an interconnection modeling style, behavioral dependencies are defined on a per-role basis and different roles are interconnected using message flow. This thesis reveals a number of modeling "anti-patterns" for interconnection modeling, motivating further investigations on choreography languages following the interaction modeling style. Here, interactions are seen as atomic building blocks and the behavioral dependencies between them are defined globally. Two novel language proposals are put forward for this modeling style which have already influenced industrial standardization initiatives. While avoiding many of the pitfalls of interconnection modeling, new anomalies can arise in interaction models. A choreography might not be realizable, i.e. there does not exist a set of interacting roles that collectively realize the specified behavior. This thesis investigates different dimensions of realizability.}, language = {en} } @article{DinesLiuSchulze2009, author = {Dines, Nicoleta and Liu, Xiaochun and Schulze, Bert-Wolfgang}, title = {Edge quantisation of elliptic operators}, series = {Preprint / Universit{\"a}t Potsdam, Institut f{\"u}r Mathematik, Arbeitsgruppe Partiell}, journal = {Preprint / Universit{\"a}t Potsdam, Institut f{\"u}r Mathematik, Arbeitsgruppe Partiell}, issn = {1437-739X}, doi = {10.1007/s00605-008-0058-y}, year = {2009}, abstract = {The ellipticity of operators on a manifold with edge is defined as the bijectivity of the components of a principal symbolic hierarchy sigma = (sigma(psi), sigma(boolean AND)), where the second component takes values in operators on the infinite model cone of the local wedges. In the general understanding of edge problems there are two basic aspects: Quantisation of edge-degenerate operators in weighted Sobolev spaces, and verifying the ellipticity of the principal edge symbol sigma(boolean AND) which includes the (in general not explicity known) number of additional conditions of trace and potential type on the edge. We focus here on these questions and give explicit answers for a wide class of elliptic operators that are connected with the ellipticity of edge boundary value problems and reductions to the boundary. In particular, we study the edge quantisation and ellipticity for Dirichlet-Neumann operators with respect to interfaces of some codimension on a boundary. We show analogues of the Agranovich-Dynin formula for edge boundary value problems.}, language = {en} } @article{EirundSethmann2009, author = {Eirund, Helmut and Sethmann, Richard}, title = {NetS-X : Netzsicherheit lernen mit Spaß}, series = {Commentarii informaticae didacticae : (CID)}, journal = {Commentarii informaticae didacticae : (CID)}, number = {1}, issn = {1868-0844}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus-29660}, pages = {81 -- 92}, year = {2009}, abstract = {Das Gebiet der Netzsicherheit ist ein schwer zu lehrendes und m{\"u}hsam zu lernendes Fach in der Informatikausbildung. Dies hat verschiedene Gr{\"u}nde, z.B. erfordert es Fachkenntnis, die jenseits von bunten Bildern zu vermitteln ist und sich dabei mit geringer Halbwertszeit weiterentwickelt. Echte Bedrohungsszenarien m{\"u}ssen unter Laborbedingungen nachgestellt werden, und der Umgang mit den Sicherheitswerkzeugen ist sehr komplex. Auf der einen Seite muss das System konzeptionell verstanden werden und auf der anderen Seite sind viele Details in der Konfiguration von Firewalls, Netz-Komponenten und -Werkzeugen f{\"u}r klassische Pr{\"u}fungssituationen in der Ausbildung anzuwenden. Mit NetS-X (Network Security Experience) stellen wir einen laufenden Prototyp einer e-learning Plattform vor, mit der ein weiter Bereich von Sicherheitsszenarien vermittelt werden kann. Dabei wird der Lernende in einem Spielsystem mit Situationen konfrontiert, die er in einer echten, auf Linux basierenden typischen IT-Infrastruktur eines Unternehmens beherrschen muss. Die sicherheitsrelevanten Aktivit{\"a}ten des Lernenden, z.B. der Einsatz von Monitor-Werkzeugen oder die Konfiguration von Netz-Komponenten werden dabei nicht simuliert, sondern real durchgef{\"u}hrt und durch Prozesse des Spielsystems beobachtet und bewertet. Autorenwerkzeuge erm{\"o}glichen den Lehrenden und Spielern, selber neue Spielsituationen, Sicherheitsszenarien oder Wissenskomponenten in das System zu integrieren.}, language = {de} } @book{Freischlad2009, author = {Freischlad, Stefan}, title = {Entwicklung und Erprobung des Didaktischen Systems Internetworking im Informatikunterricht}, publisher = {Universit{\"a}tsverlag Potsdam}, address = {Potsdam}, isbn = {978-3-86956-058-8}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus-41851}, publisher = {Universit{\"a}t Potsdam}, pages = {XIV, 405}, year = {2009}, abstract = {Internetbasierte Informatiksysteme beeinflussen in steigendem Maße Situationen in unterschiedlichen Lebensbereichen. Kompetenzen zur Verwendung von Internetanwendungen und -diensten m{\"u}ssen explizit erworben werden, weil damit ein notwendiger Einblick in nicht beobachtbare Abl{\"a}ufe und nicht offen sichtbare Strukturen verbunden ist. Bisher gibt es Vorschl{\"a}ge f{\"u}r die Gestaltung schulischer Lehr-Lernprozesse zu ausgew{\"a}hlten Teilaspekten des Internets. Es fehlt eine systematische Analyse des Bildungsbedarfs und ein daraus resultierendes Unterrichtsmodell. In dieser Arbeit wird ein Gesamtkonzept f{\"u}r den Informatikunterricht in der Sekundarstufe II vorgestellt, das zu zielgerichteter und verantwortungsvoller Anwendung des Internets beitr{\"a}gt. Die vorliegende Arbeit umfasst den Prozess von der Analyse erforderlicher Kompetenzen bis zur Realisierung von Lehr-Lernprozessen im Informatikunterricht in der Sekundarstufe II. Es werden der Beitrag der Informatik zu identifizierten Kompetenzen untersucht und Bildungsanforderungen bestimmt. Bildungsempfehlungen und Forschungsergebnisse zu erfolgreichen Unterrichtseinheiten werden im Hinblick auf die Bildungsziele analysiert. Der Informatikunterricht unterst{\"u}tzt die Kompetenzentwicklung zu internetbasierten digitalen Medien. Es wird die Entwicklung eines Unterrichtsmodells zu Internetworking beschrieben. Dazu wird der Ansatz der Didaktischen Systeme untersucht, weiter entwickelt und auf den Bereich Internetworking {\"u}bertragen. Der theoretische Ansatz wird dazu in vier Unterrichtsprojekten zu Internetworking in der Praxis realisiert. Beziehungen zwischen Fachkonzepten zu Internetworking werden untersucht und durch Wissensstrukturen zur Planung von Unterrichtsprojekten eingesetzt und in der Praxis erprobt. Die Beschreibung von Lernaktivit{\"a}ten erfolgt auf der Basis von Aufgabenklassen, die das notwendige Wissen zur Bearbeitung einer Aufgabenstellung repr{\"a}sentieren. Auf der Grundlage des Ablaufs der Aufgabenbearbeitung werden Eigenschaften von Aufgaben beschrieben und zu deren Gestaltung nutzbar gemacht. Bisher nicht durchf{\"u}hrbare T{\"a}tigkeiten im Unterricht werden durch die Entwicklung der Lernsoftware Filius erm{\"o}glicht. Die Reduktion der komplexen Wirklichkeit durch Simulation realer internetbasierter Informatiksysteme und die Auswahl geeigneter Sichten auf den Untersuchungsgegenstand werden mit Ergebnissen der Informatikdidaktik begr{\"u}ndet. Unterrichtsprojekte zu den Zielen werden durchgef{\"u}hrt, um Lehr-Lernprozesse zu erkunden und das entwickelte Didaktische System zu erproben. Ausgehend von der theoretischen Fundierung erfolgt die praktische Realisierung von Lehr-Lernprozessen. Zur Erprobung im Informatikunterricht der Sekundarstufe II in Nordrhein-Westfalen werden Minimalziele aufgrund der Lehrvorgaben bestimmt. Die methodische Gestaltung in der Erprobung erfolgt unter Ber{\"u}cksichtigung der Vorgaben f{\"u}r den Informatikunterricht und allgemeinen Anforderungen der Fachdidaktik. Handlungsorientierte Unterrichtsmittel werden ausgew{\"a}hlt und in der Praxis zur Untersuchung der Lehr-Lernprozesse verwendet. Im Unterricht identifizierte Lernschwierigkeiten f{\"u}hren zur Modifikation der Wissensstrukturen und werden im Entwicklungsprozess von Filius ber{\"u}cksichtigt. Die Erkenntnisse aus Unterrichtsprojekten werden genutzt, um zu bestimmen, zu welchen Aufgabenklassen weitere Aufgaben erforderlich sind und inwieweit das aus den identifizierten Merkmalen abgeleitete Vorgehen zur Entwicklung niveaubestimmender Aufgaben genutzt werden kann. Die Erprobungen best{\"a}tigen die Tragf{\"a}higkeit des Didaktischen Systems Internetworking und leisten mit der Implementierung in der Praxis einen Beitrag zur Untersuchung von Kompetenzentwicklung im Informatikunterricht. Mit dem Didaktischen System Internetworking wird ein theoretisch fundiertes und empirisch erprobtes Unterrichtsmodell zur Entwicklung von Kompetenzen zur Einrichtung und Anwendung internetbasierter Informatiksysteme beschrieben.}, language = {de} } @article{GebserGharibMerceretal.2009, author = {Gebser, Martin and Gharib, Mona and Mercer, Robert E. and Schaub, Torsten H.}, title = {Monotonic answer set programming}, issn = {0955-792X}, doi = {10.1093/logcom/exn040}, year = {2009}, abstract = {Answer set programming (ASP) does not allow for incrementally constructing answer sets or locally validating constructions like proofs by only looking at a part of the given program. In this article, we elaborate upon an alternative approach to ASP that allows for incremental constructions. Our approach draws its basic intuitions from the area of default logics. We investigate the feasibility of the concept of semi-monotonicity known from default logics as a basis of incrementality. On the one hand, every logic program has at least one answer set in our alternative setting, which moreover can be constructed incrementally based on generating rules. On the other hand, the approach may produce answer sets lacking characteristic properties of standard answer sets, such as being a model of the given program. We show how integrity constraints can be used to re-establish such properties, even up to correspondence with standard answer sets. Furthermore, we develop an SLD-like proof procedure for our incremental approach to ASP, which allows for query-oriented computations. Also, we provide a characterization of our definition of answer sets via a modification of Clarks completion. Based on this notion of program completion, we present an algorithm for computing the answer sets of a logic program in our approach.}, language = {en} } @article{HaiderScheffer2009, author = {Haider, Peter and Scheffer, Tobias}, title = {Bayesian clustering for email campaign detection}, isbn = {978-1-605-58516-1}, year = {2009}, language = {en} } @book{HartmannSelbig2009, author = {Hartmann, Stefanie and Selbig, Joachim}, title = {Introductory Bioinformatics}, publisher = {Books on Demand}, address = {Norderstedt}, isbn = {978-3-8370-5189-6}, pages = {246 S.}, year = {2009}, language = {en} } @article{HilscherBraunRichteretal.2009, author = {Hilscher, Martin and Braun, Michael and Richter, Michael and Leininger, Andreas and G{\"o}ssel, Michael}, title = {X-tolerant test data compaction with accelerated shift registers}, issn = {0923-8174}, doi = {10.1007/s10836-009-5107-5}, year = {2009}, abstract = {Using the timing flexibility of modern automatic test equipment (ATE) test response data can be compacted without the need for additional X-masking logic. In this article the test response is compacted by several multiple input shift registers without feedback (NF-MISR). The shift registers are running on a k-times higher clock frequency than the test clock. For each test clock cycle only one out of the k outputs of each shift register is evaluated by the ATE. The impact of consecutive X values within the scan chains is reduced by a periodic permutation of the NF-MISR inputs. As a result, no additional external control signals or test set dependent control logic is required. The benefits of the proposed method are shown by the example of an implementation on a Verigy ATE. Experiments on three industrial circuits demonstrate the effectiveness of the proposed approach in comparison to a commercial DFT solution.}, language = {en} } @book{Huebner2009, author = {H{\"u}bner, Sandra}, title = {Wie Online-Werkszeuge eine maßgeschneiderte Veranstaltungkonzeption unterst{\"u}tzen k{\"o}nnen}, publisher = {Univ.-Bibl.}, address = {Potsdam}, year = {2009}, language = {de} } @article{IshebabiBobda2009, author = {Ishebabi, Harold and Bobda, Christophe}, title = {Automated architecture synthesis for parallel programs on FPGA multiprocessor systems}, issn = {0141-9331}, doi = {10.1016/j.micpro.2008.08.009}, year = {2009}, abstract = {This paper presents a concept for automated architecture synthesis for adaptive multiprocessors on chip, in particular for Field-Programmable Gate-Array (FPGA) devices. Given a parallel program, the intent is to simultaneously allocate processor resources and the corresponding communication network, and at the same time, to map the parallel application to get an optimum application-specific architecture. This approach builds up on a previously proposed design platform that automates system integration and FPGA synthesis for such architectures. As a result, the overall concept offers an automated design approach from application mapping to system and FPGA configuration. The automated synthesis is based on combinatorial optimization. Automation is possible because a solvable Integer Linear Programming (ILP) model that captures all necessary design trade-off parameters of such systems has been found. Experimental results to study the feasibility of the automated synthesis indicate that problems with sizes that can be encountered in the embedded domain can be readily solved. Results obtained underscore the need for an automated synthesis for design space exploration.}, language = {en} }