[Δομημένος Πρ.] Εργασία F

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

[Δείτε περισσότερα εδώ...]

Συμβουλές καλής χρήσης του φόρουμ: Youtube embed code and links, Shoutbox, Notify, ...

Δείτε περισσότερα εδώ...

[c0ndemn3d]

Συζήτηση και απορίες για την έκτη εργασία

Σε ένα γράφημα, με άρτιο αριθμό κορυφών, ζητείται να χωριστούν οι κορυφές του σε δύο ομάδες Α και Β, με ίσο αριθμό κορυφών. Η επιλογή των κορυφών που θα ανήκουν στις ομάδες Α και Β να γίνει έτσι ώστε, αν διαγραφούν οι ακμές οι οποίες συνδέουν τις κορυφές της μιας ομάδας με τις κορυφές της άλλης ομάδας, το άθροισμα των βαρών των ακμών που θα διαγραφούν να είναι το ελάχιστο (πρόβλημα της ελάχιστης τομής).    

Ένας αλγόριθμος που θα έδινε μια σχετικά καλή λύση, όχι τη βέλτιστη, επιλέγει την ακμή με το μικρότερο βάρος και καταχωρεί τη μια από τις κορυφές που συνδέει στην ομάδα Α και την άλλη στην Β. Στη συνέχεια διαγράφει από το γράφημα τις κορυφές αυτές και επαναλαμβάνει την διαδικασία με τις υπόλοιπες κορυφές. Οι διαδικασία σταματά όταν όλες οι κορυφές του γραφήματος καταχωρηθούν σε κάποια από τις δύο ομάδες.

Να γραφεί το πρόγραμμα το οποίο να υλοποιεί τον πιο πάνω αλγόριθμο. Το πρόγραμμα να εκτυπώνει, για κάθε ομάδα, τις κορυφές που την αποτελούν καθώς και το άθροισμα των βαρών των ακμών που συνδέουν τις κορυφές της ομάδας Α με αυτές της ομάδας Β. Στην περίπτωση που ο αλγόριθμος διαπιστώσει ότι με τη διαδικασία που ακολουθείται δεν καλύφτηκαν όλες οι κορυφές του γραφήματος να τυπώνεται αντίστοιχο μήνυμα. Για την καταχώρηση του γραφήματος οι κορυφές να αριθμούνται από το 0 έως το n-1 (n ο αριθμός των κορυφών του γραφήματος). Στο πρόγραμμα να οριστούν οι πίνακες connection και weight, δύο διαστάσεων. Ο πίνακας connection να ορίζει μια γραμμή για κάθε κορυφή του γραφήματος και να καταχωρεί ως τιμές για τα στοιχεία της γραμμής τους αριθμούς των κορυφών με τις οποίες συνδέεται η κορυφή που αντιστοιχεί στη γραμμή. Ο πίνακας weight να είναι ίδιος με τον πίνακα connection με τη διαφορά ότι αντί για τους αύξοντες αριθμούς των κορυφών, στις ίδιες θέσεις, να καταχωρούνται τα βάρη των ακμών οι οποίες συνδέουν τις κορυφές με την κορυφή στην οποία ανήκει η αντίστοιχη γραμμή του πίνακα.

Σημείωση

Το πρόγραμμα να διαβάζει τον αριθμό των κορυφών του γραφήματος και να δεσμεύει δυναμικά μνήμη, στο ελάχιστο απαιτούμενο μέγεθος, για όλους τους πίνακες που θα χρειαστούν για την υλοποίηση του προγράμματος.

Για τους πίνακες connection και weight κοιτάξτε το παράδειγμα της άσκησης C.

Ο αλγόριθμος να ελέγχει μόνο ζεύγη κορυφών που συνδέονται μεταξύ τους. Να αγνοεί ζεύγη που δε συνδέονται αν και αυτά θα μπορούσαν να δώσουν καλύτερη λύση.

 

  

[c0ndemn3d]

Επαναλαμβάνω:

Συζήτηση και απορίες για την έκτη εργασία

[vagus]

Tι να πρωτοκαταλαβεις...;

Ας ξεκινησουμε με τα βασικα. Το βαρος των ακμων ειναι το μηκος τους ;

[Exomag]

Tι να πρωτοκαταλαβεις...;
Ας ξεκινησουμε με τα βασικα. Το βαρος των ακμων ειναι το μηκος τους ;

Βάρος της κάθε ακμής (που συνδέει την κορυφή i με την κορυφή j) είναι ο αριθμός που καταγράφεται στον πίνακα weight[j], που είναι ίδιος με τον weight[j]...

[thanospr]

Αν κατάλαβα καλά ψάχνουμε την ράβδο με το μικρότερο βάρος και βαζουμε την μια κορυφη στην ομάδα Α και την άλλη στην ομάδα Β.Δεν καταλαβα αυτο που λεει με την ελαχιστη τομή.

Σε ένα γράφημα, με άρτιο αριθμό κορυφών, ζητείται να χωριστούν οι κορυφές του σε δύο ομάδες Α και Β, με ίσο αριθμό κορυφών. Η επιλογή των κορυφών που θα ανήκουν στις ομάδες Α και Β να γίνει έτσι ώστε, αν διαγραφούν οι ακμές οι οποίες συνδέουν τις κορυφές της μιας ομάδας με τις κορυφές της άλλης ομάδας, το άθροισμα των βαρών των ακμών που θα διαγραφούν να είναι το ελάχιστο (πρόβλημα της ελάχιστης τομής).     

Εχει καταλάβει κανείς για να βοηθήσει;

[elleth]

Θα βρίσκει την ακμή με το μικρότερο βάρος,το βάρος αυτό θα το προσθέτεις σε μια μεταβλητή (πχ sum) και μετά θα βάζεις τις 2 κορυφές της ακμής αυτής στους πίνακες Α κ Β.Μετά θα διαγράφεις τις 2 κορυφές και την ακμή.Στη συνέχεια βρίσκει από αυτά που έχουν μείνει την επόμενη ακμή με το μικρότερο βάρος και πάλι προσθέτει το νέο min  βάρος στο sum κ συνεχίζει.

[thanospr]

Την μία την βάζουμε στην Α ομάδα και την άλλη στην Β τυχαία η όχι?

Η επιλογή των κορυφών που θα ανήκουν στις ομάδες Α και Β να γίνει έτσι ώστε, αν διαγραφούν οι ακμές οι οποίες συνδέουν τις κορυφές της μιας ομάδας με τις κορυφές της άλλης ομάδας, το άθροισμα των βαρών των ακμών που θα διαγραφούν να είναι το ελάχιστο (πρόβλημα της ελάχιστης τομής).

[elleth]

Ε ναι τυχαία.

[nastia]

τους πινακες  connection-weight θα τους βαζει τιμες ο χρηστης?

[autos.gr]

τους πινακες  connection-weight θα τους βαζει τιμες ο χρηστης?

Ναι,ειναι οι ιδιοι ακριβως πινακες απτην ασκηση C.Αποθηκευουν τα ιδια δεδομενα που αποθηκευαν κ στην C.Μπερδεμενη εκφωνηση οπως παντα,αλλα αμα το καταλαβεις τι πρεπει να γινει,η ασκηση ειναι αρκετα ευκολη(χωρια που μπορεις να κανεις copy-paste καποια κομματια απο την ασκηση C [οπως πχ. το τμημα του κωδικα π ειχες γραψει για να γεμισεις τους πινακες weight κ connection]).

Αυτο για το οποιο ομως δεν ειμαι σιγουρος,ειναι αν θα αντιστοιχιζουμε τις κορυφες απτις ομαδες Α <------> Β ως μια προς μια.

δλδ σκεφτομαι οτι η ομαδα Α και η ομαδα Β ειναι μονοδιαστατοι πινακες (τους φανταζομαι σαν 2 στηλες). Η κορυφη στο Α [1] συνδεεται με την κορυφη στο Β [1] με βαρος πχ 3 .Αλλα επισης η κορυφη Α [1] μπορει να συνδεεται κ με την κορυφη που βρισκεται στο Β [4] με βαρος πχ. 5 .Θα παρουμε σαν βαρος μονο το 3,ή θα πρεπει να μετρησουμε και το 5?

Ξερω πως τα λεω λιγο μπερδεμενα,παντως αν κανεις καταλαβαινει τι εννοω,ας πει την αποψη του!

[Exomag]

Αυτο για το οποιο ομως δεν ειμαι σιγουρος,ειναι αν θα αντιστοιχιζουμε τις κορυφες απτις ομαδες Α <------> Β ως μια προς μια.

δλδ σκεφτομαι οτι η ομαδα Α και η ομαδα Β ειναι μονοδιαστατοι πινακες (τους φανταζομαι σαν 2 στηλες). Η κορυφη στο Α [1] συνδεεται με την κορυφη στο Β [1] με βαρος πχ 3 .Αλλα επισης η κορυφη Α [1] μπορει να συνδεεται κ με την κορυφη που βρισκεται στο Β [4] με βαρος πχ. 5 .Θα παρουμε σαν βαρος μονο το 3,ή θα πρεπει να μετρησουμε και το 5?

Ξερω πως τα λεω λιγο μπερδεμενα,παντως αν κανεις καταλαβαινει τι εννοω,ας πει την αποψη του!

Αν κατάλαβα αυτό που εννοείς, οι πίνακες Α και Β θα γεμίζουν καθώς ο αλγόριθμος κάνει την διαδικασία που λέει η εκφώνηση. Η κορυφή Α(i) αντιστοιχεί στην κορυφή B(i), διότι διαγράφηκαν μαζί (λόγω της κοινής τους ακμής) μέσω του αλγορίθμου. Στο αρχικό σχήμα μπορεί όντως η κορυφή Α(i) να συνδεόταν και με άλλες κορυφές, οι οποίες αργότερα θα καταχωρηθούν σε άλλη θέση A(j) μαζί με μια άλλη κορυφή B(j). Βάρος, όμως, της ακμής που συνδέει την κορυφή Α(i) είναι η τιμή της ακμής, την οποία διάλεξε ο αλγόριθμος κατά την εκτέλεση του, και η οποία συνδέει το Α(i) με το B(i)...

Sorry αν σε μπέρδεψα παραπάνω...

[autos.gr]

Βασικα θα γινει μονο 1 προς 1 αντιστοιχιση,γιατι η εκφωνηση λεει πως θα διαγραφουν οι ακμες που συνδεουν τις κορυφες της μιας ομαδας με την αλλη,και ζηταει το αθροισμα των βαρων των ακμων που θα διαγραφουν μονο.Καταλαβαινω τι λες,δεν με  μπερδεψες.Επισης ημουν σιγουρος πως εσυ θα απαντουσες ,αρα κερδισα το στοιχημα. 

[Exomag]

Βασικα θα γινει μονο 1 προς 1 αντιστοιχιση,γιατι η εκφωνηση λεει πως θα διαγραφουν οι ακμες που συνδεουν τις κορυφες της μιας ομαδας με την αλλη,και ζηταει το αθροισμα των βαρων των ακμων που θα διαγραφουν μονο.Καταλαβαινω τι λες,δεν με  μπερδεψες.

Μη ξεχνάς βέβαια, ότι ο αλγόριθμος μπορεί να μη χωρίσει όλες τις κορυφές σε ακριβώς δύο ομάδες. Δηλαδή μπορεί κάποιες να μείνουν "ξέμπαρκες"...

Επισης ημουν σιγουρος πως εσυ θα απαντουσες ,αρα κερδισα το στοιχημα. 

[evripidaros]

Ουσιαστικα δηλαδη, χτιζω το δικτυωμα μου με την διαδικασια που ακολουθει στην C και κατοπιν εργαζομαι για τον διαχωρισμο σε Α και Β;

[Exomag]

Ουσιαστικα δηλαδη, χτιζω το δικτυωμα μου με την διαδικασια που ακολουθει στην C και κατοπιν εργαζομαι για τον διαχωρισμο σε Α και Β;

Ουσιαστικά, διαγράφεις μία μία τις ακμές του δικτυώματος (μαζί με τις δύο κορυφές που ενώνεται) ξεκινώντας από αυτήν με το μικρότερο βάρος. Την μία από τις δύο κορυφές που συνδεόταν η ακμή την βάζεις στην Ομάδα Α, και την άλλη στην Ομάδα Β...