Μάθημα 4 (Μέρος Β) / Ευσταθές Ταίριασμα
Ευσταθές Ταίριασμα: Αυτός ήτανε ο αλγόριθμος προτάσεις και απόρριψης των VLTS αυλαία τον είδαμε και στην αναμένουμε στην εφαρμογή στο παράδειγμα πάμε να δούμε τώρα την ορθότητα και την ανάλυση της πολυπλοκότητας των αγορών φορέα το πάμε σιγά σιγά καταρχήν μου γιώργος τερματίζει και πολλά τερμάτισε έ...
| Κύριος δημιουργός: | |
|---|---|
| Γλώσσα: | el |
| Φορέας: | Πανεπιστήμιο Πατρών |
| Μορφή: | Video |
| Είδος: | Ανοικτά μαθήματα |
| Συλλογή: | Τμήμα Mηχανικών Η/Υ & Πληροφορικής / Εισαγωγή στους Αλγόριθμους |
| Ημερομηνία έκδοσης: |
ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ
2014
|
| Θέματα: | |
| Άδεια Χρήσης: | Αναφορά-Μη-Εμπορική Χρήση-Όχι Παράγωγο Έργο |
| Διαθέσιμο Online: | http://delos.upatras.gr/opendelos/videolecture/show?rid=78440e58 |
| Ευσταθές Ταίριασμα: Αυτός ήτανε ο αλγόριθμος προτάσεις και απόρριψης των VLTS αυλαία τον είδαμε και στην αναμένουμε στην εφαρμογή στο παράδειγμα πάμε να δούμε τώρα την ορθότητα και την ανάλυση της πολυπλοκότητας των αγορών φορέα το πάμε σιγά σιγά καταρχήν μου γιώργος τερματίζει και πολλά τερμάτισε έτσι η πρώτη παρατήρηση είναι ότι αυτό το έργο διότι όπως τον αλγόριθμο οι άνδρες κάνουν πρόταση στις γυναίκες ωραία σε φθίνουσα σειρά προτίμησης πολύ σαφές το δεύτερο είναι ότι όταν μια γυναίκα βρείτε ταίρι δεν μένει ποτέ μόνη της μόνο μπορεί να αλλάξει αυτό το ταίρι με κάποιον καλύτερο σύντροφο σαφές δεν παρατηρείς τον θυμάστε γιατί είναι τα κλειδιά για τις αποδείξω ταυτότητας που θα συζητήσουμε παρακάτω καταγγέλλει είναι σαφής αυτή δύο παρατηρήσεις από τον αλγόριθμο προηγουμένως περιέγραψα Βαλαβάνη ποιοι είναι και οι δύο είναι εγγενής παρατηρήσεις που προκύπτουν από τον αλγόριθμο δηλαδή ότι οι άνδρες κάνουν προτάσεις σε φθίνουσα σειρά προτίμησης και όταν μια γυναίκα βρει ένα ταίρι έτσι καπνιστής ταιριάξει με κάποιον το μωρό μπορεί να καλυτερέψει το σύντροφό της με κάποιον άλλον δεν μένει ποτέ μόνοι μας περίπτωση του ωραία και ισχυρίζομαι ωδείο αλγόριθμος τερματίζει και μάλιστα τερματίζει μετά από το πολύ μια τετράγωνη παραλείψεις επαναλαμβάνω είναι οι γυναίκες και έμεινε γιατρός μπορεί κάποιος να μου πει γιατί θα κάνει του τραβούν επαναλήψεις επαναλαμβάνω αυτός εδώ έχουμε ξεχάστε πρέπει προς το παρόν πόσο χρόνο περνούν οι ενδιάμεσες πράξεις που βρίσκονται στο σώμα του βρόχου wine λέμε ακριβώς πόσες παρά το ερώτημα είναι πόσες επαναλήψεις Κανέλλη βρόχος μανούβρα και εγώ ισχυρίζομαι ότι κάνει τον πολύν δρόμο παρακαλώ πολύ σωστά ακριβώς πολύ σωστά έτσι στη χειρότερη περίοδο 2009 δίνει μείον ένα προτάσεις έτσι έχουν σαν τάξη μεγέθους κυριαρχεί καθώς εδώ χώρος από το τραγούδι σε κάθε επανάληψη ένα άντρας κάνει πρόταση σε μια γυναίκα και επειδή έχουμε η τραγωδία της πρότασης αυτό συμβαίνει στη χειρότερη περίπτωση σε κάθε επανάληψη ώρα παρών αλγόριθμος τερματίζει μετά από ένα πολύ γενικό αριθμό τετραγωνικό αριθμός το πλήθος των ανδρών πάρτι γυναικών παραλείψεις τώρα είναι σαφές ότι αυτό συνεχίζουμε την απόδειξη ορθότητας θέλει θέλουμε έναν ατελείωτο ταίριασμα σημαίνει ότι δεν έχουμε ακριβή ασθενούς άνδρες γυναίκες δηλαδή όλοι εργάζονται τώρα η απόδειξη εδώ θα είναι με την απαγωγής ατό που δηλαδή θα υποθέσουμε ότι υπάρχει ένα άντρας ας πούμε την εκπρόσωπο το παράδειγμά μας δεν έχει σημασία το όνομα ο οποίος δεν έχει ταιριάξει μέχρι το τέλος του αγώνα ώρα τι σήμαινε αυτό το πράγμα επειδή υπάρχει ίσος αριθμός ανδρών και ισάριθμων γυναικών θα υπάρχει άλλη ένα άλλη ένα αυτή του θα υπάρχει μια γυναίκα έτσι Εστουδιαντίνα η οποία επίσης δεν έχει ταιριάξει με το τέλος το τέλος του αγώνα καταλαβαίνουμε και γιατί οι υπόλοιπες γιατί είναι ένα έχουν βρει ταίρι με τους λείπει ένα άνδρες αυτό σημαίνει ότι από τη δεύτερη παρατήρηση ότι όταν μια γυναίκα που εργάζεται δεν ξέραμε τίποτε μόνη της μοντέλα σε μεγαλύτερους τροχούς ωραία ούτε το γεγονός ότι η Άννα δεν έχει ταίρι στην άννα δεν έγινε ποτέ πρόταση γιατί αποκλείεται ακόμα χειρότερα να τις κάνει πρόδωσαν ελεύθεροι είναι αυτήν παραδοχή μας ωραία άρα για να μείνει μια γυναίκα ελεύθερη μετά το τέλος του αλγόριθμου σημαίνει πιστή γυναίκα αυτή δεν έγινε ποτέ πρόταση αυτών άτοπο γιατί ξέρουμε πυρετός έχει κάνει προτάσεις σε όλες τις γυναίκες αφού καταλήγει χωρίς πρέπει ώρα επαναλαμβάνονται ράβουν εξ πόνου για να αποδείξουμε ότι όλοι άντρες και γυναίκες εργάζονται θα χρησιμοποιήσουμε τον μηχανισμό της αποδείξεις με την είσοδο του αγωγή την οποία θεωρώ ότι ξέρετε κ πάλι για τόσα χρόνια και σίγουρα την έχετε συναντήσει και σε άλλα μαθήματα του πρώτου έτους της έτσι κάνουμε μια υπόθεση η οποία μας οδηγεί σε μια εσφαλμένη παραδοχής από άρα οι υποθέσεις μας είναι λάθος έτσι αυτό σημαίνει το πράγμα αυτούς αυτή τεχνική αποδείξεις έστω λοιπόν λέμε τώρα υπάρχει ένα άντρας είναι αυτός που δεν έχει ταιριάξει δεν έχει ευρύτερη μέχρι τέλος του αλγόριθμου ωραία επιτελεί άνδρας συναινεί και γυναίκες συναινεί λίγα έχουν ευρύτερη προφανώς έχουν ευρύτερη με τη διπλή ανάγκη να Καίσαρα πρέπει υποχρεωτικά να αφού μέχρι τώρα δεν έχει ταίρι να υπάρχει και μια άλλη γυναίκα που δεν έχει ταίρι τι είπαν ωραία τώρα από τη δεύτερη παρατήρηση που λέει ότι όταν γυναίκα της γίνει πρόταση έστω από τον χειρότερο στυλίστα της πάντα λέει είναι για να μη μείνει στο ράφι φτάνει παραδοχή μας ωραία τότε σημαίνει ότι για να μείνει οι αναρχο οποιαδήποτε αναχωρεί στερημένο τέλος αλγόριθμο στην άννα δεν έγινε ποτέ πρόταση από κάποιον άντρα ωραία αυτό όμως δεν είναι σωστό διότι ο έκτορας είπαμε ότι κάθε άντρας κάνει προτάσεις σε όλες τις γυναίκες κατά φθίνουσα σειρά προτίμησης από γλυκάνισο προστέθηκαν έστηναν έτσι επομένως οδηγούμαστε σε ένα τόπο αφού ούτε ο οποιοσδήποτε γάτος αρχιτέκτονας είχε κάνει πρόταση σε όλες τις γυναίκες επομένως ο ισχυρισμός ότι όλοι άντρες και γυναίκες εργάζονται αγώνα δεν έχουμε το τέλειο ταίριασμα είναι σωστός πάμε να αποδείξουν τώρα την ευστάθεια δηλαδή ότι δεν έχουμε ασταθής ζευγάρια ΗΠΑ επιδέχεται υπάρχει μια απορία μου ως προς το προηγούμενο μοντέλο το ναι παρακαλώ είναι όχι με ρωτήσατε πολύ δεν υπάρχει μόνο ένα τέλειο κάποιας υπάρχουνε εδώ δύο παραδοχές που καθορίζουμε το ποια λύση θα βρούμε το πρώτο καταρχήν είναι κάπως ασύμμετρο από την πλευρά των ανδρών ωραία δηλαδή οι άνδρες κάνουν πρόταση και γυναίκες παθητικά δέχονται θα μπορούσε βέβαια να είναι και ανάποδα αν οι γυναίκες που κάνουν πρόταση 1000 παθητικά να δέχονται έτσι δεν απλώς το ένα μέρος στο συγκεκριμένο πρόβλημα κάνουμε την παραδοχή ότι αυτό κάνει πρόταση και το αποδέχεται την καλύτερη δυνατή επιλογή που θα έρθει το δεύτερο είναι ότι μπορεί πείραμα η σειρά με την οποία οι άνδρες αρχίζουν και επιλέγουν είναι αυθαίρετο προφανώς αυτή η σειρά μια άλλη σειρά προτίμησε μια διαφορετική λύση αλλά δε μας ενδιαφέρει εμάς να δούμε να βρούμε μια μοναδική λύση δεν έχει μοναδική λύση το πρόβλημα το θέμα είναι να τους διώξουμε όλους να υπάρχει δηλαδή αυτό που λέμε τελειότητα και αυτό που λέμε ευσταθούν δηλαδή να μην έχουμε σταθεί ζευγάρια να μην έχει κανείς κινήτρων άλλαξε με κάποιον καλύτερο σύντροφο αυτός στόχος αλλά και να βρούμε το μοναδικό ταίριασμα κάνει αν αυτό υπάρχει οπότε ζητώ συγνώμη από τις κύριες γυναίκα απόφαση μέχρι τον αγκώνα να παραλαμβάνω άλλαξε τους ρόλους και πάλι θα γίνει συγκέντρωση εγώ το πλοίο των γυναικών λίγο πάμε πάλι με τι να αποδείξουν ότι δεν υπάρχουν στάθης έβγαλε με την ίδια μέθοδο με την εις άτοπον απαγωγή έτσι αυτοί όπως και οι η επαγωγή απαγωγής ακόμα και η παθούσα OS είναι δύο κλασικές τεχνικές που χρησιμοποιούνται στις αποδείξεις θα υποθέσουμε και πάλι ότι έχουμε ένα ασταθές έβγαλε ανά έτος δηλαδή λέει ο αλγόριθμος λοιπόν έχει ταιριάξει δίνει μια λύση αστεράκι ο αλγόριθμος κι όσα βλέπουμε και έχει ταιριάξει δίναμε τον δημήτρη και τη βάσω των ακτών της υποθετικά και λέει ότι στο η ανακοινώνεται ένα είναι ένα ασταθές το ζευγάρι που σημαίνει ότι ένα προτιμάει δηλαδή αν προτιμάει τον έκτορα τον έχεις μεγαλύτερη προτίμηση από το δημήτρη και O έκτορας έχει την ανάσα καλύτερη προτίμηση από τη βάσω αυτό σημαίνει πράγμα λέμε ότι έστω ότι υπάρχει κάποιος σαφές κατανοητό διά και πάμε να δούμε πως θα καταλήξουμε στη υπάρχουν δύο περιπτώσεις ότι γιατί ο έκτορας βρέθηκε με τη βάσω γιατί δεν έκανε ποτέ πρώτα στην άννα φορέα που σημαίνει ότι για να μην έχει κάνει ο έκτορας πρόταση στην άννα και έχει κάνει πρόταση στη βάσω η βάσω θα πρέπει να προηγείται στην προτίμηση των πρότειναν μάλιστα είχε κάνει τίποτα στην καταλαβαίνουμε επομένως ζευγάρια ανά ανάκτορα του υποθεσω οτι είναι ασταθές είναι σταθερές επαναλαμβάνω για ένα έχει ο έκτορας εργαστεί με τη βάσω στη λίστα προτίμησής τους και να μην έχει γίνει ακόμα πρόταση στην άννα θα πρέπει η βάσω να είναι σε καλύτερη θέση στη λίστα προτίμησης πρέπει τώρα από την άννα αφού δεν έκανε προσφορά στην μάλιστα είχε κάνει την πρώτη της επομένως δεν υπάρχει αστάθεια στο ζευγάρι αυτό ώρα ή να έχετε εργαστεί με ένα γυναίκα του Βάσου την οποία θεωρεί καλύτερη από την χαρά οδηγούμαστε σε αυτό η δεύτερη περίπτωση είναι ότι ναι μα μιλάμε ότι που το ζευγάρι είναι ανά έκτορας οι άνδρες κάνουν προτάσεις έτσι προφανώς αναμένεται το δίμηνο κόσμος δεύτερη περίπτωση που η δεύτερη περίπτωση είναι ότι όντως ο έκτορας έκανε πρόταση στην γκάμα αλλά προφανώς για να μην έχουν καταλήξει σε γάτες να γίνουν ζευγάρι στο τέλος του αλγόριθμου σημαίνει ότι ανά απέρριψε την πρόταση του ούτε μπορεί να απορρίψει την πρόταση έτσι του οι αμέσως αργότερα όταν έχει εργασθεί με κάποιον καλύτερο αποκτώντας έκανε πρόταση καπνός κάλυπτε που σημαίνει δηλαδή ότι δημήτρης είναι καλύτερος από τον απλό επομένως το ζευγάρι και πάλι άννα πράσινες θέσεις δεν υπάρχει αστάθεια αλλά σε κάθε περίπτωση ξεχύνονται υποθεσω οτι έχουμε ένα ασταθές έβγαλε μετά το τέλος του αλγόριθμου παρατηρούμε ότι οδηγούμαστε σε άτοπο δηλαδή και σε κάθε περίπτωση το ζευγάρι αυτό είναι ευπαθές που προσέχουμε και ορθότητα αλγόριθμοι εργαζόμενους περιέγραψα βρίσκει ένα τελείως και ευστάθειας ταίριασμα υπάρχει κάποια απορία σχετικά με την απόδειξη χώρα τώρα ο αλγόριθμος αυτός εγγυάται την ορθή λύση για οποιοδήποτε στιγμιότυπο του προβλήματος τώρα λοιπόν φθάσαμε όμως απασχόληση στο υπόλοιπο του μαθήματος είναι πως θα υλοποιηθεί ο αλγόριθμος μπήκε σαν πλέι είπε αποδοτικά ωραία θα δούμε δηλαδή την ανάλυσή της πολυπλοκότητας η ανάλυση αυτό το πράγμα δύσκολο λόγω της επτά Θυμηθείτε λίγο τον αλγόριθμο ο αλγόριθμος έχει ένα βρόχο while όποιος τρέχει ενώ υπάρχουν ελεύθεροι άνδρες και ο άνδρας πρέπει να επιλέξουμε έναν ελεύθερο άντρα να βρει την πρώτη γυναίκα στη λίστα προτίμησης του και μετά να δει αν αυτοί είναι ελεύθεροι δεσμευμένοι κι αν τον προτιμά σε σχέση είτε όχι σε σχέση με κάποιον άλλον έτσι αυτές είναι βασικές πράξεις μέσα στο μπρόντγουεϊ ο οποίος βρόγχους by αποδείξαμε ότι θα κάνει τετράγωνο παραλείψεις και τώρα αυτό που θα δούμε είναι ότι μπορούμε να υλοποιήσουμε όλο τον αλγόριθμο σε χρόνο τάξη μεγέθους του τετραγώνου που σημαίνει ότι θα πρέπει να υλοποιήσουμε αποδοτικά με σταθερό αριθμό πράξεων όλες αυτές τις πράξεις που είδαμε στις τις εντολές που ζητάμε συγγνώμη στο ευρωκο δικά στο σώμα του βρόχου είναι πάμε να δούμε καταρχήν πόσα να παριστάνουμε τους στις γυναίκες με αρίθμηση από ένα σπίτι the master διαφωνούν ομάδα τώρα στον υπολογιστή γιάννης γιώργος κλπ βάζουμε 1.3 έως έως ν κορέα και έχουμε τις εξής πως αυτό είναι πολύ σημαντικό πως αποθηκεύουμε της λίστας προτίμησε δηλαδή έχουμε για κάθε άνδρα ένα ουσιαστικά αφαιρεί ένα μητρώο έτσι έτσι ένα έως μη εδώ έχουμε τον άνδρα ανοίγει και εδώ έχουμε τη λίστα πρώτης προτίμησης του και αντιπρότεινε κάποιο anniversary τσάι είναι τρίτη κλπ ποια είναι η μείωση και γράφει ονόματα γυναικών πρώτα θέλω την τέσσερις μετά θέλω την 15 μετά την δύο κλπ και ούτω καθεξής της αυτή είναι η λίστα προτίμησης για κάθε έναν βάζουμε όλα μαζί ξένα διασπά το μητρώο παραείναι γίναμε χρόνια ποινή δηλαδή αναφορά στην τετράγωνο αντίστοιχα και γυναίκες έχουν επίσης ένα λίστα προτίμησης πάλι με τον ίδιο τρόπο όπου εδώ έχουμε και πάλι ελέγχουμε τη λίστα προτίμησης των γυναικών Κέλεϊ ξέρουμε αρέσει πρώτα μου 17 μετά 32 μετά δύο ένα κλπ ωραία αυτοί οι νόμοι που έχουν δηλαδή δύο τέτοια αμυδρό όπου κάθε γραμμή αντίστοιχη σε έναν άνδρα μια γυναίκα και για τους άλλους άντρες είναι οι γυναίκες ευθύνες ώστε να προτιμήσεις για δε τις γυναίκες είναι οι άντρες πεθαίνουν σταθεροποίησης είναι κατανοητό φορέα τώρα θέλουμε να υλοποιήσουμε σταθερό χρόνο για να βγάλω κόβουμε τετράγωνα παραλείψεις θα πρέπει αυτές οι πράξεις που σας είπα οι εντολές σε ψευδό κώδικα να εκτελούνται σταθερό χρόνο θέλουμε να βρίσκουμε έναν ελεύθερο ανδρών διαπιστώνουν ποιος είναι ελεύθερος και δεν έχει εργαστεί ακόμα είτε γιατί ακόμα δεν έχουμε εξετάσει είτε για τον απέρριψε ένα γυναίκα έχει μείνει ελεύθερος και πρέπει να δούμε τελικά το δεύτερο είναι για έναν άνδρα πρέπει να βρούμε τη γυναίκα με την υψηλότερη κατάταξη στη λίστα στην οποία δεν έχει κάνει ακόμα πρόταση πρέπει να το ξέρει αυτό σε άμεσα σε ένα βήμα τόση σταθερός χρόνος μένει σταθερός αριθμός πράξεων που εξαρτά το μέλλον σου αυτό σημαίνει του συμβολισμός ο κεφάλαιο του αν τώρα για ένα γυναίκα τι θέλουμε να ξέρουμε τι θέλουμε να ξέρουμε αν είναι δεσμευμένη ωραία και αν ναι ποιος είναι ο σύντροφος της γιατί το θέλουμε αυτό γιατί στην περίπτωση που έχουμε μια γυναίκα και δύο άνδρες πρέπει να αποφασίσουμε ποιον από τους δύο ό πρόβλημα ήταν δηλαδή πρέπει να δούμε ποιος θα τον ενώ σύντροφός και λάθος μου κάνει πρόταση είναι καλύτερος το τωρινό ταξινόμηση τροφών όχι ωραία αυτές είναι βασικές πράξεις του βρόχου while που πρέπει να μας απασχολούν θυμάστε ένα ελεύθερος άντρας κάνει πρόταση στην ανά γυναίκα πούνε ψηλότερα στη λίστα προτίμησης του και είναι ελεύθερη μετά πρέπει να δούμε να διαθέτει αυτή τη γυναίκα μετανάστρια αυτήν δεσμευμένη όχι αντί να δεσμευτεί γίνονται εταίροι αν δεσμευμένη πρέπει να δούμε εάν αυτός ο άντρας που κάνει τώρα πρόταση είναι καλύτερο στιλίστα προτίμησή της από αυτόν που έχει ήδη τέλη ωραία αν γίνονται τέτοια ανοχή των απορρίπτει πάμε λοιπόν να δούμε πως αυτά ζητήματα μπορούμε πάντα να τα υλοποιήσουμε σε σταθερού αριθμού πράξη φορέα καταρχήν έχει κάνεις κάποια ιδέα για το για το πρώτο την ερώτηση αυτή μπορείτε να την απαντήσετε με βάση αυτά που ξέρατε μέχρι τώρα στο μάθημα δεν θέλω κάτι παραπάνω λέω πώς μπορούμε σε σταθερό χρόνου να αποφασίζουμε ποιος είναι ο ελεύθερος άντρας είναι διαθέσιμος και επιστάτη μια δομή θέλουν ουσιαστικά να το πω έτσι και μετά αν κάποιος άνδρας μένει ελεύθερος να προστίθεται επίσης ταυτοχρόνως από τη δομή ένα λίστα χρέος χρειάζονται ακριβώς ένα λίστα δηλαδή έχουμε μια λίστα από ελεύθερους άνδρες αρχικά στη λίστα αυτή ανήκουν όλοι άνδρας κάθε φορά διαγράφουμε το πρώτο από τη λίστα λέμε ότι αυτός θα κάνει πρόταση σε κάποια γυναίκα και μόλις δεσμευθεί των διαγραφών από τη λίστα όταν κάποιος άνδρας αργότερα μείνει ελεύθερος τον βάζουν στο τέλος λύσεις ωραία άρα διαγραφή στοιχείων πολίστας όταν την περασμένη εβδομάδα η έμφαση στοιχείου σε μια λίστα είναι ένα σταθερός αριθμός από πράξεις είναι τρεις τέσσερις δείκτες που πρέπει να αλλάξουν τη ν επομένως διατηρώντας αυτή τη λίστα των ελεύθερων ανδρών με διαγραφές και ύφεσης μπορούμε να μπορούμε να βλέπουμε τους δεσμευμένους αν τους ελευθέρωσαν τώρα το δεύτερο είναι ότι θέλουμε να δούμε για έναν άνδρα να βρούμε τη γυναίκα που έχει υψηλότερη κατάταξη στη λίστα στην οποία δεν έχει κάνει ακόμα πρόταση δηλαδή αυτή είναι η λίστα πως παρά τον βρίσκουμε και πάλι με βάση αυτά που κοίταξε λοιπόν μπορούμε να τι πρέπει να κάνουμε για να βρίσκουμε κάθε φορά την επόμενη στην φθίνουσα σειρά προτιμήσεις μου που δεν έχω κάνει ακόμα προτάσεις στη δράμα για ποιο λόγο manhattan το έξοδο του συνέχισαν την πληροφορία πιστεύω ότι διάφορα αφού έκανε θα μπορούσαν θα μπορούσε να είναι μια λύση κάθε φορά νούμερα θα αφαιρούσε κάτι έχει κάνει προτάσεις θα μπορούσαν να ήταν και μια λύση στην παραμονή και ν διαφορετικές στιγμές αλλά να κόρη κορίνα περίπου αυτό χρειάζεται παιδεία είναι διαισθητικά το λέω είναι ένα δείκτης στην αρχή προς την επόμενη που δεν έχω μου που είναι ίση προς την τελευταία που έχουν κάνει προτάσεις κάθε φορά όταν όπως λένε όπως κάνω προτάσεις δείκτης αυτός αυξάνεται κατά ένα να ίσως την κύλιση με τη στοίβα απλώς αντιγράφει θα πρέπει να χρησιμοποιήσει τις στιγμές δηλαδή έχουμε ένα μονοδιάστατο διαγώνισμα για τον κάθε άνδρα μη πως υλοποιούμε τώρα με το δίκτυο της Hellas press τρόπους υλοποίησης θα μπορούσαν να κατέχει έναν δείκτη στη σειρά αυτή από την κεφαλή κόστος στοιχείου αλλά το όλο πράγμα των έξι που δίνει την επόμενη διάθεση που δεν έχει στην οποία δεν έγινε ο πρώτος αρχικά είναι η πρώτη τον 6ο μήνα ένα και τον εκ του μη θολά κρατάει ακόμα τη θέση της επόμενης γυναίκας της οποίας συγκεκριμένος άντρας ο άντρας θα κάνει προτάσεις όταν λοιπόν πώς θα κάνει προτάσεις θα πρέπει να προσπεράσει εδώ είναι που το σύστημα δεν μας βοηθούσε πολύ κατάλαβες θα πρέπει να προσπεράσει το στοιχείο μη κόμμα είμαστε στη γραμμή και πρέπει να πάρει το στοιχείο βρίσκεται στη στήλη Next To me και του έχει φορέα το στοιχείο λοιπόν αυτό είναι η τελευταία μου κάνει προτάσεις και μεταθέτει τον μετρητή αυτόν τον το διανύσει αυτό το ταξίδι σινεμά ουσιαστικά κρατάς δηλαδή πρόσεξε λίγο αυτό αυτό που θέλω να σου πω εγώ είναι ότι κρατάς εδώ ένα διαγώνισμα Next που έχει μέγεθος ν ωραία και φυλάσσουν όλη αυτή την πληροφορία που θέλεις σε ένα δομή μεγέθους ν όχι σε νησίδες ακριβώς θα πρέπει να έχει τη δική του στιγμή εντάξει ουσιαστικά δηλαδή είναι σαν διπλασιάζει σε αυτόν το χώρο εκεί μεγάλωσα στους χώρους πράγμα ένα προσθέτουμε το ένα ατομική ουσιαστικά αυτός μου λέει ποια είναι η επόμενη θέση στην οποία θα κάνω υλοποιεί αυτό το πορτοκαλί δείκτη που αυτές είναι σαν τα παιδιά και μόλις κάνει πρόταση απλά αυξάνει τον επίτιμη υποδομεσ Αθήνα δαπάνη άφεση δεξιότερα από την εξωτερική στην είναι σαφές επομένως γιατί αυτό παίρνει τώρα σταθερό χρόνο γιατί γιατί ξέρουμε να προσπέλαση με την επομένη που θα κάνω πρόταση είναι ουσιαστικά μια με είναι ένα προσπέλαση κοινού στοιχείου στη θέση γραμμή ενοικιαστή Linux του ν και μετά κάνω μια πρόταση και μια καταχώρηση αλαζονεία τιμή εδώ δηλαδή έχω τρεις πράξεις ένα ανάγνωση ωραία ένα προσδώσει και ένα καταχώρηση τρεις στοιχειώδεις πράξεις πάμε να δούμε τώρα για τις γυναίκες να δούμε αν είναι δεσμευμένες και πιο σύνοδο ενώ σύντροφός αυτό είναι πιο απλό μπορεί κανείς να μπει που νέα που είμαι πολύ ωραία αυτό είναι για μια γυναίκα μια μεταβλητή έτσι επειδή έχουμε πολλές γυναίκες έχουμε γυναίκες θα κάνουμε και πάλι ένα δίπλα ένα αντίστοιχο διαγωνισμό προσδοκάται το λέμε καθαρά αν ωραία πάλι από τη θέση ένα μέχρι τη χθεσινή και δω αρχικά αυτών ένα διαγώνισμα θα που παίρνει δύο τιμές θα μπαίνει όλες αρχικά φέρνουν την διμήνου ο κενός δείκτης δηλαδή έτσι μια κοινή 0 όποτε θέλετε που σημαίνει ότι είναι αδέσμευτη παλαιός θα η τιμή Κάντε Download για τη συγκεκριμένη γυναίκα tablet θα περιέχεται στο τον συγκεκριμένο σύντροφος μα τους συντρόφους δύο ετών αλλά και τιμή δύο είναι πατέρας δύο για παράδειγμα αν ο άντρας Διώτης είχε κάνει πρόταση και ήτανε προς το παρόν δεσμευμένη με αυτό ωραία και εδώ λοιπόν μπορούμε σταθερό χρόνο κοιτάνε ένα θέση ξέρουμε ποια γυναίκα 91 κοιτάμε τη θέση Καρατζόγλου ανεκτίμητη συναινούν είναι αδέσμευτη αν δεν είναι διόλου μας επιστρέφει τον Τορίνο δεσμευμένο τον τον σύντροφο με τον οποίο είναι δεσμευμένη κατανοητό δηλαδή πάλι θέλει μια ανάγνωση αυτού ναι υπάρχει κάποια πορεία νότια μέχρι εδώ γιατί έχει σημασία να καταλαβαίνετε γιατί αυτό γίνεται σταθερό χρόνο με δομές και πάλι αυτή έχει έχει μέγεθος δηλαδή να γράψω κιόλας για να μείνουμε ότι αυτές εδώ οι δομές αυτή εδώ η δομή έχει μέγεθος μην τον άγονο αυτή εδώ έχει μέγεθος μικρότερο άγονο και προφανώς αυτοί εδώ έχει μέγεθος μ και αυτή έχει μέγεθος ν φορέα επομένως μας έχει μείνει το τελευταίο βήμα το οποίο είναι και το πιο συγνώμη 0 τριμμένο είναι ότι εάν έχουμε τώρα μια γυναίκα η οποία είναι δεσμευμένη με έναν άντρα Μ και τις κάνει με τον γκόμενο πρόταση η αντίστροφα να δει ποιος είναι καλύτερος στη λίστα προτίμησης στις μπορεί να μη θυμάται από μνήμης έχει μια τεράστια λόγω λίστα χίλιους άνδρες στη λίστα της μαθήματα από μνήμης ωραία έχει κάνεις καμία ιδέα πως αυτό μπορεί να υλοποιηθεί ναι πολύ σωστά αλλά θα πρέπει λοιπόν εσύ να διατρέξει όλη αυτή τη λίστα για να δεις ποια θέση είναι οι δύο άντρες και να δεις αν ένα είναι μικρότερος από τον άλλο πόσο χρόνο θα σου πάρει όμως αυτό σωστό είναι αυτό που λες ναι αλλά εμείς θέλουμε σε σταθερό χρόνο έγιναν όχι γιατί οι γυναίκες δεν έχουν βάναυσα δεν είναι πώς το λένε ναι οι τιμές εδώ δεν είναι κατά φθίνουσα είναι κατά φθίνουσα σειρά προτίμησης δεν είναι κατά φθίνουσα σειρά αξίας καταλαβαίνεις θα είχε νόημα να κάναμε διάδικοι αναζήτηση εάν ήταν κατά φθίνουσα σειρά αξίας αλλά εδώ μέσα βλέπεις ότι είναι πρώτο 17 32002 με τα ωραία δεν υπάρχει ταξινόμηση άλλη ιδέα ορίστε φόροι σε σταθερό χρόνο με με δέντρο στο σωρό για παράδειγμα ήδη λειτουργίας μονάδας όσο έπαιρναν λογαριασμό ΥΚΩ χρόνο δεν είναι σταθερός όπως πόνος ας ακούσουμε το κανένα άλλο σου λέει ποιος είναι ο σύντροφος δε σου λέει αν αυτός νούμερο δύο είναι καλύτερος από το νούμερο τρεις 17 32 και απ όσο μπορώ πολύ μακριά μεταξύ τους με με ναι σωστή ναυτιλία χτυπούσε αδελφό σου αλλά αυτή λύση μας παίρνει πολύ χρόνο μας παίρνει τόσο χρόνο εμείς θέλουμε σε σταθερό χρόνο ικανό να θερμάνει άντε να ξοδέψουν χρόνο γραμμικό στο μέγεθος της λίστας δεν ήταν πολύ σωστή αυτή λύση είναι ακριβώς αυτήν τη λύση κατάλαβε τότε μπορείς να κάνεις το πράγμα έτσι δηλαδή χρειάζεται την αντιστροφή της λίστας προτίμησης φορέα τι σήμαινε αυτό το πράγμα να δημιουργήσουμε να δημιουργήσουμε δηλαδή έχετε τη λίστα η άννα λέει ο πρώτος συναινούμε 8 ο δεύτερος νούμερο τρεις ο τρίτος νόμος επτά και ούτω καθεξής ωραία και άλλα έχουμε και την αντιστροφή την ονομάζουμε μπαίνει στη λίστα προτίμησης δηλαδή ο νούμερο ένα άντρας συναντά στην προτίμηση πολλών άλλων δύο είναι γνωστή προτίμηση νούμερο τρεις είναι δεύτερος στην προτίμηση ανωτερότητας αλλά είναι πέντε στην προτίμηση και ούτω καθεξής αυτήν την λίστα μπορούμε πολύ εύκολα να δημιουργήσουμε με ένα τροχοφόρων πολύ απλά τι κάνουμε διατρέχουμε την παραλία στα από έντυπες ένα έως μίνιμουμ και το στοιχείο που είναι έστω στη θέση στη στήλη αλλά δηλαδή στο ο πρώτος άνδρας το πρώτο σε προτίμηση είναι το νούμερο 8 έτσι επομένως συγνώμη ο τέταρτος ο άνδρας κινούμενος ένα είναι ο τέταρτος προτίμηση άρα στη στήλη ένα που αυτό επιδοτείται ως προς τους άντρες θα δει το τέσσερις το περιεχόμενο δηλαδή της πάνω λίστας που έλαβαν εδώ έχουμε δεικτών τότε συνήθως σειρά προτίμησης εντός έχουμε δεικτών τότε εσύ ως προς τα ονόματα των ανδρών γιατί αυτό τώρα μας διευκολύνει διότι όταν λέει έχουν δύο άνδρες των μου ήδη ότι τρεις και έξι και επιτόκιο τρεις ενώ τρέχουν σύντροφος και ότι όντας έτσι κάνει πρόταση στήναμε αυτή κοιτάει τον αντίστροφο πίνακας και κοιτάει το έμβασμα τρεις και το βραστό έξι και παρατηρεί ότι τρεις ενώ δεύτερη στην προτίμηση και έξι είναι έβδομος την προτίμηση ανάβουν το δύο είναι μικρότερο από του επτά πορεία τότε στέκεται με αυτόν που έχει με τον άντρα μου μάρω βλέποντας μόνο τρεις το καταλαβαίνουμε αυτό δεν είναι τόσο απλό αλλά ούτε και πολύ δύσκολο δημιουργείται δηλαδή όταν έχετε αυτές τις λίστες δημιουργείται ουσιαστικά άλλον ένα τέτοιο διαγωνισμό γιατί είναι μια γραμμή για κάθε γυναίκα τρέχοντας για κάθε γραμμή του μητρώου αυτόν τον ψευδό κώδικα και δημιουργεί για κάθε σειρά προτίμησης την αντιστροφή της πουλερικών επιμένει ο σαμαράς επομένως όταν μου κοιτώντας τρεις κιλά σε έξι κοιτάω τον αντίστροφο καταγγέλλοντας τρεις προτεραιότητα δημιουργώντας έτσι 37 παραμένω με τον Ρήγα και απορρίπτω τον έξι με το κάνεις όμως ένα φορά αυτός την αρχή δηλαδή όταν σου δίνεται η είσοδος αυτών των προτιμήσεων των γυναικών τρέχεις για κάθε γυναίκα αυτήν εδώ την αυτό το φορτίο αυτό δίνει το βρόχο for θα σου πάρει συνολικά για κάθε γυναίκα δυναμική χρόνου για όλες είτε τραγουδά κανείς ένα φορά όταν τρέχει αλγόριθμος το μόνο που κάνεις είναι όταν έχεις μια γυναίκα ναύλου δεσμευμένη με τόλμη ποὺ κάνει πρόταση κοιτάς το τον είναι βέρες και αποφασίζεις αλλά αυτός τους κάνει πρόταση είναι καλύτερος χειρότερος από αυτόν που έχεις τώρα υπάρχει κάποια άλλη απορία με διάμετρο εδώ συνοψίζονται είδαμε έναν αλγόριθμο για κάθε ταίριασμα με πάρα πολλές εφαρμογές είδαμε απόδειξη ορθότητας και ανάλυση χρονικής πολυπλοκότητας |