Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Авторизация

       
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Niedermeier R. — Randomisierte Algorithmen
Niedermeier R. — Randomisierte Algorithmen

Читать книгу
бесплатно

Скачать книгу с нашего сайта нельзя

Обсудите книгу на научном форуме



Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter


Название: Randomisierte Algorithmen

Автор: Niedermeier R.

Аннотация:

Nehmen wir an, daß es jedes Jahrtausend mindestens einen Meteoriteneinschlag gibt, der mehr als 100 Quadratmeter der Erdoberfläche verwüstet. Dann läßt sich folgern, daß ein Rechner während einer Mikrosekunde seines Daseins mit einer Wahrscheinlichkeit von mindestens $2^{-100}$ zerstört wird. Von diesem Standpunkt aus erscheint ein Algorithmus, der mit Fehlerwahrscheinlichkeit kleiner $2^{-100}$ in Sekundenschnelle $2^{400}$ — 593 als die größte Primzahl kleiner $2^{400}$ identifiziert, als sehr praktisch (insbesondere in Bezug auf dahinterstehende, kryptologische Anwendungen). Ein randomisierter Algorithmus ist ein Algorithmus, dessen Verhalten in jedem Schritt von einem Zufallsexperiment ("Münzwurf") abhängen kann. Da sich randomi-sierte Algorithmen nicht mehr deterministisch verhalten, können die Laufzeit und/oder die Korrektheit nur noch mit gewissen Wahrscheinlichkeiten garantiert werden. Es gibt zwei grundsätzliche Vorteile randomisierter Algorithmen gegenüber "normalen" (deterministischen) Algorithmen: Effizienz und Einfachheit (letzteres führt oft auch zu besserer Implementier-barkeit). In der Vorlesung werden grundlegende randomisierte Algorithmen für verschiedenste Anwendungen vorgestellt. Zudem werden randomisierte Komplexitätsklassen betrachtet und einige Methoden und Werkzeuge für die Analyse randomisierter Algorithmen bereitgestellt.


Язык: de

Рубрика: Computer science/

Статус предметного указателя: Неизвестно

ed2k: ed2k stats

Год издания: 1997

Количество страниц: 78

Добавлена в каталог: 27.03.2007

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2019
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте