Programutvecklingsteknik 13 februari 2002

Övning 5

  1. Den katolska kyrkans hierarki finns i ett träd med påven i roten, kardinalerna på nivån under, biskopar under dom osv ner till dom enklaste prästerna i löven. Om roten skapats med

       root = new DefaultMutableTreeNode("Johannes Paulus II");

    skriv då kod som Användbara metoder är
         public int getChildCount()
         public TreeNode getChildAt(int i)
         public TreeNode[] getPath()
    



  2. Vid ett anbudsförfarande ska alla anbud ha kommit in med e-post ett visst klockslag. Det är av yttersta vikt att inget anbud läcker ut i förväg och att anbuden blir juridiskt bindande. Föreslå ett krypteringsförfarande!


  3. Allmänna val borde kunna skötas över internet. Tänk efter vilka problem som måste lösas och föreslå lösningar på dom!


Lösningar

  1. Om man tänker sej att class Hierarki extends JTree och att Hierarki kyrkan = new Hierarki() och att kyrkträdet sedan har byggts upp, till exempel genom inläsning från en fil, så vill man ha metoder som kan anropas så här:
    Man bör tänka på att JTree är en grafisk komponent som alltid är kopplad till dom osynliga objekt som ingår i datastrukturen. Det är den uppdelning mellan VIEW och MODEL som gäller alla swingklasser.
       _____          _________           ________ 
      |JTree|1      1|TreeModel|1       1|TreeNode|*-----
      |_____|--------|_________|---------|        |      |
         ^                               |________|1-----
       __|_____
      |Hierarki|  Från JTree kommer man åt höger med getModel() och
      |________|  från TreeModel kommer man åt höger med getRoot().
    
    REKURSIV TANKE: Totalantalet för trådet under (och inklusive) noden p är (1 + summan av totalantalen för barnens träd)
    ... men om p är null är totalantalet noll.
      private int total(TreeNode p)         {
        if(p==null) return 0                ;
        int antal=1                         ;
        for(int i=0;i<p.getChildCount();i++){
          antal+=total(p.getChildAt(i))     ;} 
        return antal                        ;}                         
    
      public int getTotalCount()            {
        return total(getModel().getRoot())  ;}
    
    REKURSIV TANKE: Antal nivåer är (1 + max(antal nivåer under barnen))
    ... men om p är null är antal nivåer noll.
      private int nivåer(TreeNode p)        {
        if(p==null) return 0                ;
        int rekord=0                        ;
        for(int i=0;i<p.getChildCount();i++){
          int antal=nivåer(p.getChildAt(i)) ;
          if(antal>rekord) rekord=antal     ;} 
        return 1+rekord                     ;}                         
    
    REKURSIV TANKE: Att skriva ut alla löven under nod p är detsamma som att skriva ut alla löv under alla barnen
    ...men om p är null skrivs ingenting
    ...men om p inte har några barn skrivs p själv ut.
      private void skrivLöv(TreeNode p)               {
        if(p==null) return                            ;
        if(p.getChildCount()==0) System.out.println(p);
        else for(int i=0;i<p.getChildCount();i++)     {
          skrivLöv(p.getChildAt(i))                   ;}}
    
    För att hitta Rune P Thuringer går man igenom trädet på samma sätt som i dessa tre uppgifter och när man hittar honom anropar man getPath() och skriver ut resultatet.
      private void skrivKedja(TreeNode p, String namn){
        if(p==null) return                            ;
        for(int i=0;i<p.getChildCount();i++)          {
          TreeNode q=p.getChildAt(i)                  ;
          if(q.toString().equals(namn))               {
            TreeNode[] path=q.getPath()               ;
            for(int i=0;i<path.length;i++)            {
              System.out.println(path[i])             ;}}
          else skrivKedja(q,namn)                     ;}}
    



  2. Man får anta att anbudsgivarna Skanska och NCC har skaffat sej krypteringsnycklar - public key och private key - och att det också gäller beställaren Göran Persson. Alla har förstås sin public key på sin webbsida, men DET RÄCKER INTE. Någon kan ha hackat sej in och ändrat på nyckeln, därför bör alla inblandadet ha certifierat sin nyckel via den nationella certifieringsmyndigheten (Riksskatteverket?) eller genom personligt besök hos varandra.

    Om Skanska krypterar sitt anbud med Göran Perssons public key och skickar det över nätet kan inte en tjuvlyssnare tolka det. Men hur ska GP veta att anbudet kommer från Skanska och inte från någon skojare? Skanska måste därför även kryptera med sin private key och när GP dekrypterar med Skanskas public key är han absolut säker på att anbudet är autentiskt.

    Ett problem återstår - om GPs sekreterare känner till GPs private key och låter sej mutas kan NCC få reda på anbudets innehåll i förväg. Därför bör Skanskas meddelande först krypteras med vanlig lösenordskryptering (DES) och inte förrän anbudstiden har gått ut ringer man upp GP och meddelar att lösenordet är BANAN.


  3. Det svåra är att kolla att ingen röstar två gånger och ändå bevara rösthemligheten. Riksskatteverket kan skicka ut digitala röstkort krypterade med den röstberättigades public key. Den som ska rösta dekrypterar röstkortet (ett stort tal), lägger till sin digitala valsedel efteråt (partinumret), krypterar allt med RSVs public key och skickar in det. Om flera röster kommer in med samma röstkort är det bara den sista som räknas.

    Röstkorten är stora slumptal som genererats av ett program som kommer ihåg vilka röstkort det finns men inte vem som fått vilket röstkort.

    Det finns massor av andra aspekter och säkert plats för ännu otänkta geniala ideer.

^ Upp till kurssidan.


Sidansvarig: <henrik@nada.kth.se>
Senast ändrad 18 februari 2004
Tekniskt stöd: <webmaster@nada.kth.se>