Göm meny

Temarapport 2

Temarapport 2 handlar om att strukturera och dela upp ett problem i mindre delar. Ni kommer jobba med samma problemdomän som i Temauppgift 2.

(Nu uppdaterad för VT18)

Lärandemål för Temarapport 2

Att dela upp ett problem i mindre delar och att använda denna uppdelning är en av de viktigaste färdigheterna att bemästra när man programmerar. Generellt pratar man om programabstraktion och data-abstraktion. I denna temarapport ska ni öva på programabstraktion, dvs att skapa en hierarkisk struktur för programmet. Data-abstraktion handlar om att strukturera den information som manipuleras, något ni övade på i Temarapport 3 i förra kursen, och som vi kommer fortsätta med i Tema 3. I Temarapport 2 kommer ni mer specifikt öva på:

  • Uppdelning av problem i i delproblem; dela upp kod i mindre funktioner
  • Namngivning av problem och delproblem/funktioner
  • Beskrivning av problem och delproblem/funktionskommentarer
  • Beskrivning av algoritm med hjälp av tidigare definierad uppdelning

Temarapporten

Grupper och algoritmvariant för temarapporten

  • Alla grupper ska beskriva en algoritm som klarar av kvadrater som har olika storlekar (dvs random i gränssnittet)
  • Om ni löste antingen varianten row_layout eller column_layout i temauppgiften ska ni beskriva varianten zigzag_layout.
  • Om ni löste varianten zigzag_layout i temauppgiften får ni välja om ni vill beskriva row_layout eller column_layout i temarapporten.

Brons-, Silver- och Guldnivåer

För alla nivåer gäller att

  • Alla delar av rapporten som beskrivs i rapportdispositionen ska finnas med.
  • Problembeskrivningen ska ta upp och beskriva alla begrepp/termer ni använder er av i övriga beskrivningar.
  • Namnen på de funktionerna ni beskriver ska beskriva det som funktionerna gör. Användningen av funktionerna i algoritmkoden ska alltså motsvara deras namn och beskrivning.
  • Välj hellre ett längre, men mer beskrivande namn framför korta och intetsägande namn.

Brons

  • Problemuppdelning har gjorts så att minst två funktioner är benämnda med väl valda namn som passar ihop med deras funktionsbeskrivningar.
  • Mindre brister får finnas i funktionsbeskrivningarna, men det ska gå att förstå vad funktionen gör (och vad den inte gör).
  • Delar av algoritmkoden får ersättas av kommentarer som tydligt beskriver det som ska göras, dvs inga luckor i algoritmen får finnas och inga vaga beskrivningar (som “fixa resten”) får användas

Silver

  • Problemuppdelning har gjorts så att minst tre funktioner är benämnda med väl valda namn som passar ihop med deras funktionsbeskrivningar.
  • Inga brister får finnas i funktionsbeskrivningarna.
  • Delar av algoritmkoden får ersättas av kommentarer som tydligt beskriver det som ska göras, dvs inga luckor i algoritmen får finnas och inga vaga beskrivningar (som “fixa resten”) får användas

Guld

  • Problemuppdelning har gjorts enligt behov för att täcka alla delproblem, (dock minst tre) där alla funktioner är benämnda med väl valda namn som passar ihop med deras funktionsbeskrivningar
  • Inga brister får finnas i funktionsbeskrivningarna.
  • Inga delar av algoritmkoden (koden tillhörande rubriken “Algoritmkod” i dispositionen nedan) får ersättas av kommentarer. Jämför koden för brons och guld i Exempel 2

Rapportdisposition

OBS! Alla delar av rapportdispositionen ska finnas med i rapporten.

Se till att nedanstående information finns med:

  • namn på gruppmedlemmarna i början av rapporten
  • vilken variant ni löste i temauppgiften
  • vilken variant ni beskriver i temarapporten
  • vilken nivå ni siktar på (Brons, Silver, Guld)

Rubrik: Problembeskrivning

Börja med att beskriva er problemvariant med egna ord. Ni får använda figurer om ni vill.

Syftet med att beskriva problemet är benämna och förklara alla begrepp ni kommer använda er av i era algoritmer (ungefär som att en beskrivning av sorteringsproblemet från Quick Sorts perspektiv behöver beskriva pivot value, left mark och right mark)

Rubrik: Problemuppdelning

Dela upp problemet i mindre delar och beskriv dessa delar. För varje delproblem,

  • ta fram ett beskrivande namn på en funktion som löser det problemet, samt
  • en kort beskrivning av problemet

Sammanställ dessa i en tabell med tabellrubrikerna funktion och funktionskommentar. I kolumnen funktion skriver ni namnet på funktionen, samt de argument som funktionen tar. I kolumnen funktionskommentar skriver ni funktionskommentaren för funktionen. Funktionskommentaren ska följa PEP257.

Huvudfunktionen (t.ex. row_layout) och dess funktionskommentar behöver ej finns med i tabellen.

Exempel

(presenteras inte i tabellform av pinsamma tekniska skäl)

Funktion:

insert_value(value, index, values)

Funktionskommentar:

Infoga value efter index i listan values.

value är ett heltal
index är det index i listan values som value kommer infogas efter
values är en lista av heltal

Rubrik: Algoritmkod

Skriv kod som med hjälp av de funktioner ni namngivit och beskrivit i tabellen löser löser layoutproblemen. Infoga kommentarer så att koden blir läsbar. Se exempelena nedan och observera kraven för Brons, Silver och Guld beroende på vilken nivå ni siktar på.

Exempel på kod tillhörande algoritmkodsrubriken

Exempel 1

Nedan följer ett exempel på en sorteringsalgoritm som delats upp i delproblem som tas hand om av separata funktioner. Uppdelning av ett problem i delproblem har man som mest nytta av när man även kan använda funktionerna som löser delproblemen på flera ställen i koden.


def slow_insertion_sort(list_of_values):
    """Sortera heltalen i listan list_of_values."""
    index = 1
    while index < len(list_of_values):
       current_value = list_of_values[index]
       sorted_index = get_sorted_index_for_value(current_value, list_of_values[0:index])
       insert_value(current_value, sorted_index, list_of_values)
       index += 1

Ovanstående sorteringsalgoritm är långsammare än den insertion sort ni sett tidigare, då den version ni sett tidigare både letar efter rätt index och infogar värdet på samma gång. Det är alltså inte säkert att man kan skriva kod som både är optimerad och “lättläst”, utan det är en avvägning som får göras.

Exempel 2

Nedan följer en layoutalgoritm som placerar ut kvadraterna i diagonala rader som går från den vänstra kanten till den botten (dvs ungefär som backslashtecken \). Till skillnad från algoritmerna från Temauppgift 2 som ni ska beskriva, är denna algoritm till ett gränssnitt där man endast kan välja om raderna ska börja nerifrån eller uppifrån. Den första koden är för guld, den andra är för brons.

Guld-variant

def diagonal_layout(squares, frame_width, frame_height, start_at_top):
    """Placera kvadraterna i listan squares i diagonala rader.

    squares  är en lista med kvadrater (tkinter.Label-objekt)
    frame_width är bredden på den yta som kvadraterna ska placeras ut på
    frame_height  är höjden på den yta som kvadraterna ska placeras ut på
    start_at_top  är True om de diagonala raderna går uppifrån och ner, och
                  False om de går nerifrån och upp.
    """
    # antalet kvadrater som finns kvar att placera
    squares_left = len(squares)

    # fortsätt att placera ut kvadrater tills det inte finns några kvar
    while squares_left > 0:
        # beräkna startpositionen för nästa rad (alla rader börjar längst till
        # vänster)
        line_start_y = calculate_next_line_start_y(line_start_y, start_at_top)

        # plocka fram de kvadrater som får plats på nästa rad
        next_squares = get_squares_for_next_line(squares, line_start_y,
                                                 frame_width, frame_height)
        # avbryt layout-loopen om det inte gick att placera ut någon kvadrat
        if len(next_squares) == 0:
            break

        # ta bort kvadraterna next_squares från listan squares och uppdatera
        # squares_left med antalet kvadrater som är kvar efter denna rad
        remove_squares(next_squares, squares)
        squares_left = len(squares)

        # placera ut kvadraterna i en diagonal rad
        place_squares(next_squares, line_start_y, start_at_top)

Brons-variant

def diagonal_layout(squares, frame_width, frame_height, start_at_top):
    """Placera kvadraterna i listan squares i diagonala rader.

    squares       är en lista med kvadrater (tkinter.Label-objekt)
    frame_width   är bredden på den yta som kvadraterna ska placeras ut på
    frame_height  är höjden på den yta som kvadraterna ska placeras ut på
    start_at_top  är True om de diagonala raderna går uppifrån och ner, och
                  False om de går nerifrån och upp.
    """
    # antalet kvadrater som finns kvar att placera
    squares_left = len(squares)

    # fortsätt att placera ut kvadrater tills det inte finns några kvar
    while squares_left > 0:
        # beräkna startpositionen i y-led för nästa rad (alla rader börjar
        # längst till # vänster)
        pass

        # plocka fram de kvadrater som får plats på nästa rad
        next_squares = get_squares_for_next_line(squares, line_start_y,
                                                 frame_width, frame_height)

        # om  det inte går att placera ut fler kvadrater avbryts funktionen
        pass

        # ta bort kvadraterna i next_squares från listan squares
        pass

        # placera ut kvadraterna i en diagonal rad
        place_one_line_of_squares(next_squares, line_start_y, start_at_top)

Inlämning

  • Temarapporten skickas in som PDF till 729G75@ida.liu.se. Använd “Temarapport 2” följt av era LiU-IDn samt er handledares handledarkod som ämnesrad.
  • Evelina Rennes har handledarkod [evere22]. Jody Foo har handledarkod [jodfo01].
  • Rapportmall. Mallen behöver inte användas så länge som ni följer rapportdispositionen. Observera att dokumentet ska skickas in som PDF.
  • Deadline hittar du på deadlinesidan.

Sidansvarig: Jody Foo
Senast uppdaterad: 2018-04-04