ΘΕΜΑ B1

Β1. Ένας πίνακας λέγεται αραιός (sparse) αν ένα μεγάλο ποσοστό των  στοιχείων του έχουν μηδενική τιμή. Ένας δισδιάστατος αραιός πίνακας  μπορεί να αναπαρασταθεί από έναν μονοδιάστατο όπου κάθε μη μηδενικό  στοιχείο του δισδιάστατου αντιπροσωπεύεται στον μονοδιάστατο από μία  τριάδα στοιχείων, δηλαδή <γραμμή, στήλη, τιμή>. Για παράδειγμα, ο  παρακάτω πίνακας Α [4,5] που θέλουμε να τον διαχειριστούμε ως αραιό 

0
-3
0
0

 

αντιπροσωπεύεται από τον μονοδιάστατο Β[15].  

-3  4

 

Η αντίστροφη διαδικασία είναι από τον μονοδιάστατο πίνακα να παραχθεί  ένας ισοδύναμος αραιός δισδιάστατος. 

Έστω ένας πίνακας Μ[18] που αναπαριστά 6 μη μηδενικά στοιχεία. Δίνεται ο παρακάτω αλγόριθμος, ο οποίος από τον μονοδιάστατο Μ[18]  δημιουργεί τον αραιό δισδιάστατο Δ[10,20]. 

Αλγόριθμος αντίστροφος 
Δεδομένα // Μ // 
Για i από 1 μέχρι 20 
    Για j από 1 μέχρι 10 
        Δ[…(1), … (2)] <- 0 
    Τέλος_επανάληψης 
 Τέλος_επανάληψης 
Για i από 1 μέχρι 18 με_βήμα … (3) 
    α <- Μ[i] 
    β <- Μ[i + … (4)] 
    γ <- Μ[i + … (5)] 
    Δ[α, β] <- γ 
 Τέλος_επανάληψης 
 Αποτελέσματα // Δ // 
 Τέλος αντίστροφος 

Ο παραπάνω αλγόριθμος έχει 5 κενά αριθμημένα από (1)μέχρι (5). Για καθένα από τα κενά, να γράψετε στο τετράδιό σας τον αριθμό του και ό,τι χρειάζεται να συμπληρωθεί για να λειτουργήσει σωστά ο αλγόριθμος.
Μονάδες 10

Share This