Matroids Matheplanet Forum Index
Moderiert von viertel
Matroids Matheplanet Forum Index » Rätsel und Knobeleien (Knobelecke) » * Erwartungen an einen eigenartigen Sortieralgorithmus
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule * Erwartungen an einen eigenartigen Sortieralgorithmus
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2324
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-08-03

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Ich bin am Wochenende über folgenden Sortieralgorithmus gestolpert:


Im Folgenden soll immer aufsteigend sortiert werden, d.h. wenn man eine Folge mit StalinSort sortiert, dann erhält man eine monoton wachsende Folge.

Beispiel: Wenn man die Folge 0,3,1,5,2,4 mit StalinSort sortiert, dann erhält man 0,3,5.


Zu einem fest gewählten $n\in \IN$ sei $a_1,a_2,\ldots, a_n$ eine zufällig gewählte Permutation von $0,1,2,\ldots, n-1$.
Es sei $b_1,\ldots, b_m$ die Stalinsortierung dieser Permutation.

Man bestimme:
a) die durchschnittliche Länge der sortierten Folge, d.h. den Erwartungswert von $m$,
b) den Erwartungswert der Summe $b_1+b_2+\ldots + b_m$.
 

Zusatzaufgabe:
c) Man bestimme den Erwartungswert von $\frac 1m(b_1+b_2+\ldots + b_m)$.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Deine Lösung nicht direkt im Forum posten darfst.
Sende stattdessen Deine Lösung als private Nachricht an den Themensteller. Benutze dazu den Link 'Privat', den Du unter seinem Beitrag findest.
Der Themensteller wird zu gegebener Zeit über eingesandte (richtige) Lösungen informieren
und nach Ablauf einer (von ihm) festgelegten Zeit alle Lösungen veröffentlichen.
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2324
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, vom Themenstarter, eingetragen 2020-08-03

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Zur Klarstellung: Bei a) und b) soll jeweils eine einigermaßen explizite Formel in Abhängigkeit von $n$ angeben werden. Bei c) reicht es einen Algorithmus zu finden, mit dem man den Erwartungswert auch für größere $n$ (z.B. $n=100$) in annehmbarer Zeit (Programme schreiben ist erlaubt) ausrechnen kann.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2324
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-08-14


*schieb*

Bisher wurde noch keine Lösung eingereicht.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2324
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2020-08-15


Die ersten richtigen Lösungen für a) und b) kamen von Kitaktus. Glückwunsch!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Deine Lösung nicht direkt im Forum posten darfst.
Sende stattdessen Deine Lösung als private Nachricht an den Themensteller. Benutze dazu den Link 'Privat', den Du unter seinem Beitrag findest.
Der Themensteller wird zu gegebener Zeit über eingesandte (richtige) Lösungen informieren
und nach Ablauf einer (von ihm) festgelegten Zeit alle Lösungen veröffentlichen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]