Stoff?, Tips? ...
Results 1 to 11 of 11
  1. #1

    Title
    Veteran
    Join Date
    Feb 2002
    Posts
    15
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Stoff?, Tips? ...

    Hallo,

    ich würde gerne wissen was Stofflich zur VO Prüfung kommt(ich nehme an der ganze Stoff aber da ich selten (kaum) in der VO war frag ich lieber nochmal)? vielliecht gibts ja kleine Teile die nicht kommen.

    gibt es sonst irgendwelche Tips oder Details die ich für die Prüfung (ausser dem Skritpum ) wissen sollte?

    danke

  2. #2
    Kakarot's Avatar
    Title
    Hero
    Join Date
    Jun 2002
    Posts
    222
    Thanks
    0
    Thanked 0 Times in 0 Posts
    1 Frage: Notation
    2 Frage: Sortierverfahren
    3 Frage: Pseudocode
    4 u. 5 Frage unterschiedlich je nachdem was du studierst:
    Inf., Winf, Mathe
    Für Inf: Einfoch 2 Fragen aus dem Rest des Stoffes, ich glaube aber eher aus dem Stoff nach hash, also Optimierung ist ein guter Tipp.

    Die Reihenfolge hat Georg Kraml im Rep. bekannt gegeben, der Tipp kommt von mir!
    Wennst weißt von wo`s kommt,
    weißt das stimmt

  3. #3
    Kakarot's Avatar
    Title
    Hero
    Join Date
    Jun 2002
    Posts
    222
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Ach ja was ich fragen wollte: Was ist Radix-Sort? Bucket-Sort?
    Hat Georg Kraml in den Rep. mal über hash oder Tries gesprochen?
    Wennst weißt von wo`s kommt,
    weißt das stimmt

  4. #4
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    Nein, nicht im Repetetorium. Hat aber gemeint man sollte sich das auch mal anschaun.

    Bucket-Sort ist ein lineares Sotierverfahren, ziemlich einfach und mit Skriptum auch schnell zu verstehen. Von Radix-Sort hab ich keine Ahnung, ich kenn nur den Radix-Trie
    Das verwirrt mich auch ein bissl.
    Hätten uns Spiele wie Pac-Man in unserer Jugend beeinflusst, würden wir heute durch dunkle Räume irren, elektronische Musik hören und Pillen fressen.

  5. #5

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Burgenland
    Posts
    598
    Thanks
    0
    Thanked 0 Times in 0 Posts
    über Tries hat er nix erzählt
    naja vielleicht haben wir Glück und die kommen nicht - wär mir nur sehr recht, weil ich sie mir noch net angeschaut hab :-)

    Hashverfahren hat er auch net gemacht
    vielleicht weil er die eh schon im Repi vorm 2. UE-Test durchgemacht hat

    Bucket-Sort gehört zu den linearen Sortierverfahren
    im Skript auf Seite 52
    sind eh ganz einfach zu verstehen

  6. #6
    Megabit's Avatar
    Title
    Elite
    Join Date
    Feb 2002
    Location
    VIE / AUT
    Posts
    493
    Thanks
    0
    Thanked 0 Times in 0 Posts
    vergesst die Bäume und die Graphen nicht, die werden auch sicher kommen
    "Die letzte Stimme, die man hört, bevor die Welt explodiert, wird die Stimme eines Experten sein, der sagt: 'Das ist technisch unmöglich!'" Peter Ustinov


  7. #7
    EvilGuyMischa's Avatar
    Title
    Hero
    Join Date
    Mar 2002
    Location
    Wien
    Posts
    221
    Thanks
    0
    Thanked 1 Time in 1 Post
    Von Radix-Sort hab ich keine Ahnung, ...
    Das verwirrt mich auch ein bissl.

    radix sort is nix anderes als sortieren durch fachverteilung

    genauso wie bucket sort ists ein lineares sortierverfahren, das man allerdings nur beschränkt anwenden kann

    z.b.:
    gegeben sei zahlenfolge der form
    { 1246, 1863, 6864, 2648, 4567, 3691, 5846, 7641, 9145, 8546, 9111 }

    was macht nun radix sort

    VERTEILERPHASE
    1.) pro digit ein fach anlegen d.h. 10 fächer (0...9)
    2.) zahlen beginnend mit letzter stelle in fächer ordnen (reihenfolge wichtig)

    SAMMELPHASE
    3.) zahlenfolge werden unter beachtung der reihenfolge (FIFO) wieder 'gesammelt' und als folge angeschrieben

    ==> ganze so oft wie stellen vorhanden (hier: 4. stelle, 3., 2., 1.)



    ...und siehe da die sch***e ist sortiert!!! ach wie schön.

    Code:
     function pass(a, N, dig)  // e.g. in JavaScript              //A C M 1
    // pre:  a[1..N] is sorted on digits [dig-1..0]                l o o 9
    // post: a[1..N] is sorted on digits [dig..0]                  g m n 9
     { var counter = new Array(11); // for digit occurrences         p a 9
       var temp = new Array();                                   //D . s
       var i, d;                                                 //S S h
                                                                 //  c
       for( d = 0; d <= 9; d++ ) counter[d] = 0;                 //  i U
       for( i = 1; i <= N; i++ ) counter[ digit(a[i], dig) ] ++;
       for( d = 1; d <= 9; d++ ) counter[d] += counter[d-1];
    
       for( i = N; i >= 1; i-- )
        { temp[ counter[ digit(a[i], dig) ] -- ] = a[i]; }
    
       for( i = 1; i <= N; i++ ) a[i] = temp[i];
     }//pass
    
    function radixSort(a, N)
     { var p;
       for( p=0; p < NumDigits; p++ )
          pass(a, N, p);
     }//radixSort

    Code:
    			                 __"""""`""""""N_               
    			              _JN`               ""_.            
    			       	    _NNN`                   4L_          
    			         _NNN"F`                    4NL         
    			        JNNNNJ                       ´NL        
    			       ,NNNNN`                        ´NN       
    			       JNNNNN)                          "NN      
    			       NNNNNN`                           (NL     
    			       NNNNN)                             4NL    
    			       NNNNNN                               4.  
    			       NNNNNN)                               L   
    			       NNNNNF                                "`, 
    			       (NNNNN                                 ,J 
    			       (NNNNN`                               (NN 
    			       (NNNNN     "`         ,__ "`          (NN 
     			      (NNNN4)      "                        ´`´ 
    			     __.4NNNF          ´"""`             ,___  ` 
    			    JNNNNNNNN"                       __NNNNNN)   
    			    NNNNNNNNN`       ________.      JNNNNNNNN    
    			    (NNNNNNNF     _JNNNNNNNNNNN.   (NNNNNNN"     
    			     4NNNNNF     (NNNNNNNNNNNNNN    "4NNNNF`   , 
    			      4NNNN       ´"4N""N" NNN ´                 
    			       4N)J)           ,__NF"`                   
    			        4L" "`                          ____  ,_ 
    			        JNF JNN.                        ´NNNNNNN 
    			      _NNL_/NNF´`           _NF          ´"NNNN) 
    			    ,JNNNF` ´)            ,NF" .          _NN\N  
    			  ,(NNNN`              ,,JN`    "NNNLJN,_NF  NF  
    			  NNNNNN.             (F F       JNNNNN"(F   N)  
    			   "4NNNN             ´`   "NNNF""4""" _F   ,N)  
    			  ,_NNNNNL                    ´" __.__."\__ (N`  
    			  (4NNN´NNN_.                        __NNN` NF   
    			    ´    4NJ\.                    4NNNNN"  JN    
    			          ´4_´                      ´""  _JNN    
    			            ´\                        _JNNNNN    
    			              "                NF """"4NNNNNN    
     			                    ,                _NNNNNN    
    			                  ´"___NNN.          _NNNNNNF    
    			                     ""4F`           NNNNNNN)    
    			                                      NNNNNN     
    			                                      """""`     
    			"...NORMAL is just a program on the washing-machine."

    @georg kraml: DANKE fürs rep...echt spitze wie du die dinge erklärst...weiter so....nochmals DANKE!!!
    Last edited by EvilGuyMischa; 20-06-2002 at 01:54.
    "28 days, 6 hours, 42 minutes, 12 seconds - that is when the world will end."
    [Frank, the bunny | Donnie Darko]

  8. #8
    Kakarot's Avatar
    Title
    Hero
    Join Date
    Jun 2002
    Posts
    222
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Danke für die Erklärungen!
    Wennst weißt von wo`s kommt,
    weißt das stimmt

  9. #9

    Title
    Veteran
    Join Date
    Feb 2002
    Location
    Villach
    Posts
    17
    Thanks
    0
    Thanked 0 Times in 0 Posts
    function pass(a, N, dig) // e.g. in JavaScript //A C M 1
    // pre: a[1..N] is sorted on digits [dig-1..0] l o o 9
    // post: a[1..N] is sorted on digits [dig..0] g m n 9
    { var counter = new Array(11); // for digit occurrences p a 9
    var temp = new Array(); //D . s
    var i, d; //S S h
    // c
    for( d = 0; d <= 9; d++ ) counter[d] = 0; // i U
    for( i = 1; i <= N; i++ ) counter[ digit(a[i], dig) ] ++;
    for( d = 1; d <= 9; d++ ) counter[d] += counter[d-1];

    for( i = N; i >= 1; i-- )
    { temp[ counter[ digit(a[i], dig) ] -- ] = a[i]; }

    for( i = 1; i <= N; i++ ) a[i] = temp[i];
    }//pass

    function radixSort(a, N)
    { var p;
    for( p=0; p < NumDigits; p++ )
    pass(a, N, p);
    }//radixSort

    wie schaut dieser code in pseudocode aus??? hat irgendwer eine idee??????

  10. #10

    Title
    Elite
    Join Date
    Dec 2001
    Posts
    340
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Soviel ich weiß haben sie nix gesagt, dass sie für die Prüfung eine bestimmte Art von Pseudcode bevorzugen. Da gäbs mal die Knuth'sche Variante, dann die Pascal-ähnliche und schließlich das aus'm Skriptum, was so eine Art überstetztes C ist.

    Da C ähnlich wie Java und Java ählich wie JavaScript ist würd ich sagen, übersetz einfach
    pass() und radixSort() wären dann zwei verschiedene Algorithmen
    I invented ctrl-alt-del but Bill [Gates] made it famous
    Dave Bradly, IBM PC designer

  11. #11

    Title
    Elite
    Join Date
    Feb 2002
    Posts
    482
    Thanks
    0
    Thanked 0 Times in 0 Posts
    naja, ich würd nicht unbedingt sagen, dass der Pseudocode ausm Skriptum ein übersetztes C ist: in Algorithmus 7 etwa (Merge-Sort) kommt die Anweisung "wiederhole - bis" vor, das gibt es aber so nicht in C, da gibt es bestenfalls "mache - solange" -> das wirkt eher nach Pascal mit seinem "repeat - until"!

    Meiner Meinung nach ist der Algodat Pseudocode einfach nur irgendwas, was entfernt an eine Programmiersprache erinnert und für das ein menschliches Gehirn als Compiler ausreicht i.e. es sollte verständlich sein
    Ich verwend meistens striktes C für meine Pseudocodes (bis auf wirklich abstrakte Anweisungen, etwa "für alle x aus der Nachbarschaft von y"), und hab damit eigentlich immer meine Punkte gekriegt!

    Original geschrieben von Kakarot
    Hat Georg Kraml in den Rep. mal über hash oder Tries gesprochen?
    Und das klingt irgendwie eher nach Karlsplatz als nach Algodat Rep.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •