Alviss

01 | 0:00:00 Starten 0:00:10 Kapitel: Randomisierte Algorithmen 0:01:10 Uberblick 0:01:38 Sichtweisen fur randomisierte Algorithmen 0:03:33 Fundamentale Anderung 0:04:03 Beispiel: Randomisierter Quicksort 0:05:32 Zufallsvariablen uberall 0:05:49 Errinerung an W-Theorie 0:09:32 Standardbeispiel: Wurfeln 0:15:26 Algorithmen mit unbekannter Laufzeit 0:16:25 Algorithmen, die ""variierende Ausgaben"" l...

Fungal automata are a variation of the two-dimensional sandpile automaton of Bak, Tang, and Wiesenfeld (Phys. Rev. Lett. 1987). In each step toppling cells emit grains only to some of their neighbors chosen according to a specific update sequence. We show how to embed any Boolean circuit into the initial configuration of a fungal automaton with update sequence $HV$. In particular we give a constru...

We consider asynchronous one-dimensional cellular automa- ta (CA). It is shown that there is one with von Neumann neighborhood of radius 1 which can simulate each asynchronous one-dimensional cellular automaton. An analogous construction is described for α-asynchronous CA (where each cell independently enters a new state with probability α. We also point out some generalizations for other updating...

02 | 0:00:00 Starten 0:01:08 Erinnerung an W-Theorie 0:02:22 Randomisierter Quicksort 0:04:34 randQS: Anzahl Vergleiche 0:11:40 randQS: Anzahl Vergleiche mit hoher Wkt. 0:28:25 Chernoff-Schranken 0:29:04 Einfache Schranken 0:32:19 Chernoff-Schranken 0:38:03 Chernoff-Schranken: Beweis von Teil 1 0:44:26 Chernoff-Schranken: Verienfachungen 0:45:47 Chernoff-Schranken: Korollare 0:47:14 Auswertung von...

12 | 0:00:00 Start 0:02:12 Dokumente haben Inhalt, Struktur und Form 0:10:05 Struktur von Dokumenten 0:18:57 Beispiel fur Tabelle in XHTML 0:30:27 Formale Sprachen kommen ins Spiel 0:33:23 Eine Grenze unserer bisherigen Vorgehensweise 0:37:25 Was ist wichtig? 0:42:17 Ubung 6: Prozessor 0:46:56 Bitweise Operationen 0:52:36 MIMA Befehlssatz 0:58:25 Beispielprogramm 1:04:14 Links rotieren 1:08:09 Kon...

SKaMPI is now an established benchmark for MPI implementations. In autumn 2002 the development of the “new SKaMPI” has started in three major directions: (i) extension of the benchmark to cover more functions of MPI and a redesign of the benchmark allowing it to be extended more easily (thus matching requests from SKaMPI users); (ii) construction of a collection of important algorithm kernels whic...

SKaMPI-5 is a micro-benchmark for MPI implementations, designed to be easily extensible. Besides a “global” parallel file system at least some parallel machines offer (many) hard disks which are local to (processors or) computing nodes. While the MPI2 standard includes functions for doing disk IO, MPI is unable to use this resource because by (our) definition the local disks are not visible to rem...

09 | 0:00:00 Start 0:00:05 Ubung: Start 0:01:44 Zahlendarstellung 0:17:06 Zahlendarstellung und formale Sprachen 0:21:51 Vorlesung: Start 0:23:37 Homomorphismen 0:30:14 Prafixfreie Codes 0:44:41 Beispiel Unicode: UTF-8 0:58:12 Huffman-Codierung 1:03:49 Algorithmus fur Huffman-Codes 1:09:23 Konstruktion des Huffman-Baumes 1:16:56 Eigenschaften von Huffman-Codes 1:23:50 Block-Codierung

03 | 0:00:00 Start 0:00:21 Relationen 0:01:42 Mehr zu Mengen 0:03:25 Menge aller Funktionen von A nach B 0:07:37 Potenzmenge einer Menge M 0:10:35 ""Grose"" Vereinigung und Durchschnitte 0:13:23 Kapitelzusammenfassung Mengen 0:14:33 Kapitel 4: Worter 0:15:25 Themenubersicht 0:18:33 Wort uber einem Alphabet 0:19:29 Rolle des Leerzeichen 0:21:20 Definition Wort 0:26:16 Menge aller Worter 0:28:46 Das...

15 | 0:00:00 Start 0:00:59 Kontextfreie Sprachen 0:09:04 Schnitt kontextfreier Sprachen 0:12:45 Produkt von Relationen 0:18:09 Reflektiv, transitiv 0:26:24 Interpretationen 0:35:52 Allgemeingultige Formeln 0:40:09 Modelle 0:46:21 Vorkommen von Variablensymbolen in Formeln 0:54:07 Substitution 1:08:06 Logische aquivalente Formeln 1:17:58 Groszugige Benutzung von Pradikatenlogik 1:22:53 Eine Zeitrei...