[Διακριτά Μαθηματικά] Παλιά θέματα - Σχολιασμός και απορίες

[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 με προσοχή στα ονόματα των αρχείων!

[Πληροφορίες Καθηγητών]

Πληροφορίες Καθηγητών

[Κηπουρίδης]

Οκτώβριος 2013-Θέμα 2
Με μεγάλη επιφύλαξη..
To γράφημα του σχήματος έχει 10 κορυφές.
Ο πλήρης γράφος Κ10, μόνο και μόνο επειδή είναι πλήρης θα εμπεριέχει όλους του πιθανούς συνδυασμούς
των ισόμορφων υπογράφων.Θα υπάρχει λοιπόν κάθε πιθανή αντιστοιχία 10 από 10 (Διακριτές κορυφές αρα nPr) ..
αρα

α) P(10,10)=3628800

β)Για τον K20 παρόμοια θα ισχύει P(20,10)

Εγινε εδιτ μετά από βοήθεια συμφοιτήτριας...

Περιμένω feedback από τους συναδέλφους των διακριτών να ξεκαθαρίζει σιγά σιγά η κατάσταση...

Ναι, συμφωνω, στην ουσια ειναι προβλημα συνδυαστικης με περιτυλιγμα γραφων.

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

Δινουμε "υπαρξη" και στα κενα, σα να ηταν μια κατηγορια μαθητων, η "Δ". Αρα εχουμε καποιους ιδιους της ομαδας Α, καποιους της Β, της Γ και της Δ, και θελουμε να φτιαξουμε ολα τα permutations. Αυτο ειναι ο τυπος
n! / (n1! n2! n3! n4! ) = 400! / ( 70! * 100! * 80! * 150! ) που ειναι ισο με αυτο που εγραψες εσυ.

Για το θεμα 3ο θεμα, με τους γραφους, οκτωβριος 13,
α) Καθε δεντρο εχει τουλαχιστον 2 φυλλα (κομβους δηλαδη με βαθμο 1, εναν γειτονα). Αυτα τα δυο ειναι και τα σημεια κοπης.

Για να αποδειξουμε οτι υπαρχουν πραγματι δυο φυλλα, μπορουμε να δουλεψουμε ως εξης :
Υπαρχει σιγουρα 1 φυλλο, γιατι αν δεν υπηρχε τοτε ολοι οι κομβοι θα ειχαν βαθμο >= 2.
Αρα οι ακμες θα ηταν τουλαχιστον 2*V / 2 (το /2 επειδη διπλομετραμε τις ακμες, μια φορα απο καθε κομβο στον οποιο εφαπτεται). Αρα οι ακμες τουλαχιστον V, δε στεκει γιατι ξερουμε οτι το δεντρο εχει V-1 ακμες.

Γνωριζοντας οτι υπαρχει ενα φυλλο, μπορουμε να δειξουμε την υπαρξη του 2ου επαγωγικα. Ισχυει για ν=2, κι αν ισχυει για καποιο Ν, τοτε για το Ν+1 το δειχνουμε ετσι :
Πηγαινουμε στο 1 φυλλο που εχουμε σιγουρακι (το αποδειξαμε πιο πανω ), και το αφαιρουμε. Προκυπτει συνδεδεμενος γραφος (αφου το φυλλο ειναι σημειο κοπης, αρα οταν βγαινει δεν χαλαει η συνεκτικοτητα), και παιρνουμε ενα Ν-δεντρο, που ξερουμε οτι εχει τουλαχιστον 2 φυλλα, αρα αποδειχτηκε.

β) Παιρνουμε ενα ελαχιστο γεννητορικο δεντρο του γραφου και συμφωνα με το 1 εχει 2 σημεια κοπης (το δεντρο). Αυτα ειναι και σημεια κοπης για τον γενικο γραφο. Αποδεικνυεται ευκολα, αφου ολος ο υπολοιπος γραφος ειναι ακομα συνδεδεμενος, μεσω των ακμων του ελαχιστου γεννητορικου δεντρου του, που ειναι υπογραφος του.

γ) Αρκει να αποδειξουμε οτι οι γεφυρες ανηκουν παντα στα συνδετικα δεντρα.
Αποδειξη, εστω οτι δεν τις συμπεριλαμβανουν, αρα απ την ιδιοτητα της γεφυρας οτι οταν λειπει ο γραφος ειναι ασυνδετος, καταληγουμε οτι δε μπορει να ηταν συνδεδεμενα δεντρα, ατοπο, αρα ανηκουν οι γεφυρες παντα στα συνδετικα δεντρα.

[κύριος Φασόλης]

καμια ιδεα για Θεμα 2β απο σεπτεμβρη του 14 ?

[Λήσταρχος Γιαγκούλας]

καμια ιδεα για Θεμα 2β απο σεπτεμβρη του 14 ?

Γνωρίζεις πως κάθε γράφημα που έχει κύκλους ΑΡΤΙΟΥ μήκους μπορεί να χρωματιστεί μόνο με 2 χρώματα.
Από την στιγμή που αφαιρείς μια ακμή που ανήκει σε όλους τους περιττούς κύκλους πλεόν έχεις μόνο ΑΡΤΙΟΥΣ ΚΥΚΛΟΥΣ-->2 χρώματα.
Χάρη στην υπόδειξη που έχεις καταλαβαίνεις πως πλεόν 3 χρώματα σου είναι αρκετά...

[κύριος Φασόλης]

καμια ιδεα για Θεμα 2β απο σεπτεμβρη του 14 ?

Γνωρίζεις πως κάθε γράφημα που έχει κύκλους ΑΡΤΙΟΥ μήκους μπορεί να χρωματιστεί μόνο με 2 χρώματα.
Από την στιγμή που αφαιρείς μια ακμή που ανήκει σε όλους τους περιττούς κύκλους πλεόν έχεις μόνο ΑΡΤΙΟΥΣ ΚΥΚΛΟΥΣ-->2 χρώματα.
Χάρη στην υπόδειξη που έχεις καταλαβαίνεις πως πλεόν 3 χρώματα σου είναι αρκετά...

ναι οκ ξερουμε οτι το G δεν ειναι διμερες αλλα πως ξερουμε οτι δεν ειναι πληρες ωστε να μπορει να χρωματιστει μονο με 1 χρωμα?

[κύριος Φασόλης]

Οκτώβριος 2013-Θέμα 1

α) P(400,250) / 80!*100!*70!
250 φοιτητές,400 ΔΙΑΚΡΙΤΕΣ Θέσεις

β) P(100,100)/100!(=1) * [ 3*P(100,80)*P(200,70) / (80!70!)  + 3*P(100,70)*P(200,80) / (80!70!) ]

P(100,100)/100! (=1)για τους Β στο Ω
Οι υπόλοιποι σε 3->Λογω διαχωρισμού θα πάνε σε 1 η 2 αμφιθέατρα κάθε έτος.(3+3=6 συνδυασμοί)
Αρα 3*P(100,80)*P(200,70) + 3*P(100,70)*P(200,80)
 Όλο /80!70!

Κάνουμε / 80!70! επειδή θεωρούμε πως μεταθέσεις θέσεων από φοιτητές του ίδιου έτους δεν παίζουν ρόλο..
Αν το έχει κάνει κανείς ας πει αν συμφωνεί ή διαφωνεί να το διορθώσω αν είναι...

**Τα απότελέσματα βγαίνουν πολύ μεγάλοι αριθμοί...

Εγινε εδιτ μετά από βοήθεια συμφοιτήτριας...

βασικα δεν παιζει και το ενδεχομενο να πανε οι του Α ετους σε μια αιθουσα οι του Γ σε μια αλλη και να μεινει μια αιθουσα κενη?

[Λήσταρχος Γιαγκούλας]

καμια ιδεα για Θεμα 2β απο σεπτεμβρη του 14 ?

Γνωρίζεις πως κάθε γράφημα που έχει κύκλους ΑΡΤΙΟΥ μήκους μπορεί να χρωματιστεί μόνο με 2 χρώματα.
Από την στιγμή που αφαιρείς μια ακμή που ανήκει σε όλους τους περιττούς κύκλους πλεόν έχεις μόνο ΑΡΤΙΟΥΣ ΚΥΚΛΟΥΣ-->2 χρώματα.
Χάρη στην υπόδειξη που έχεις καταλαβαίνεις πως πλεόν 3 χρώματα σου είναι αρκετά...

ναι οκ ξερουμε οτι το G δεν ειναι διμερες αλλα πως ξερουμε οτι δεν ειναι πληρες ωστε να μπορει να χρωματιστει μονο με 1 χρωμα?

Αν ήταν πλήρες θα είχες σίγουρα και κύκλους περιττού μήκους και πολλά χρώματα θα ήταν απαραίτητα...
Σε κάθε περίποτωση δεν θα μπορούσες να αποφύγεις περιτού μήκους κύκλους..

βασικα δεν παιζει και το ενδεχομενο να πανε οι του Α ετους σε μια αιθουσα οι του Γ σε μια αλλη και να μεινει μια αιθουσα κενη

Το ενδεχόμενο αυτό περιλαμβάνεται στους υπολογισμους...

[AstralWind]

Παιδες ξερει κανεις τι παιζει με το θεμα 1 ερωτημα β) και γ) απο σεπτεβρη του 14;

[nvog1993]

Παιδες ξερει κανεις τι παιζει με το θεμα 1 ερωτημα β) και γ) απο σεπτεβρη του 14;

Για το 1β) νομιζω για κάθε μετάθεση των 500 επιβατών (500!) έχεις πρόβλημα 500 διακεκριμένων ατόμων σε 10 διακεκριμένα ταμεία που μας βγάζει 500^10 τρόπους. Άρα συνολικά έχεις 500!*500^10 τρόπους.
Το 1γ) σε ενδιαφέρει και πόσοι και ποιοι επιβάτες πάνε στα ταμεία. Άρα είναι διακεκριμένοι για το πρόβλημα. Άρα θα πάρουμε εκθετική γεννήτρια συνάρτηση που θα αρχίζει από τον τον όρο x²⁰/20! και θα τελειώνει στο όρο x¹⁰⁰/100! και για τα 10 ταμεία. Άρα θα έχεις (x²⁰/20! +x²¹/21!+....+x¹⁰⁰/100!)¹⁰ και θα σε ενδιαφέρει ο συντελεστής του x⁵⁰⁰/500!

[Κηπουρίδης]

Παιδες ξερει κανεις τι παιζει με το θεμα 1 ερωτημα β) και γ) απο σεπτεβρη του 14;

Για το 1β) νομιζω για κάθε μετάθεση των 500 επιβατών (500!) έχεις πρόβλημα 500 διακεκριμένων ατόμων σε 10 διακεκριμένα ταμεία που μας βγάζει 500^10 τρόπους. Άρα συνολικά έχεις 500!*500^10 τρόπους.

Για το 1β νομιζω παει διαφορετικα. Γιατι αν σκεφτουμε το πολυ απλουστερο προβλημα των 2 ανθρωπων σε 2 ταμεια, η λυση σου βγαζει 8 ενω η σωστη ειναι 6. Αυτο βγαινει γιατι δυο διαφορετικα permutations μπορει να καταληγουν στο ιδιο πραγμα (πχ η διαταξη 1-2, αν μετα μοιρασεις τον πρωτο της διαταξης στο πρωτο ταμειο και τον δευτερο της διαταξης στο δευτερο ταμειο, ειναι ιδια με την διαταξη 2-1, που στελνεις τον πρωτο της διαταξης στο δευτερο ταμειο και τον πρωτο της διαταξης στο πρωτο ταμειο).

Προτεινω, χωρις να ειμαι σιγουρος, μεσα στους 500 επιβατες να μπλεξουμε 11 φορες τον αριθμο 0. Ο αριθμος 0 ειναι διαχωριστικο, δηλαδη οτι βρισκεται αναμεσα σε δυο μηδενικα, πηγαινει στο αντιστοιχο ταμειο (επειδη παντα η πρωτη κι η τελευταια θεση θα ειναι μηδενικα με αυτη την θεωρηση, ειναι χαζο να βαλουμε 11 μηδενικα, βαζουμε 9 λοιπον! ).
Πλεον ειναι ενα προβλημα αντιμεταθεσεων, οπου ενα αντικειμενο εμφανιζεται 9 φορες, δηλαδη 509! / 9!
Στην προηγουμενη περιπτωση θα εβγαζε 3! / 1! = 6, που ειναι κι η σωστη απαντηση.

[Λήσταρχος Γιαγκούλας]

Παιδες ξερει κανεις τι παιζει με το θεμα 1 ερωτημα β) και γ) απο σεπτεβρη του 14;

Για το 1β) νομιζω για κάθε μετάθεση των 500 επιβατών (500!) έχεις πρόβλημα 500 διακεκριμένων ατόμων σε 10 διακεκριμένα ταμεία που μας βγάζει 500^10 τρόπους. Άρα συνολικά έχεις 500!*500^10 τρόπους.

Για το 1β νομιζω παει διαφορετικα. Γιατι αν σκεφτουμε το πολυ απλουστερο προβλημα των 2 ανθρωπων σε 2 ταμεια, η λυση σου βγαζει 8 ενω η σωστη ειναι 6. Αυτο βγαινει γιατι δυο διαφορετικα permutations μπορει να καταληγουν στο ιδιο πραγμα (πχ η διαταξη 1-2, αν μετα μοιρασεις τον πρωτο της διαταξης στο πρωτο ταμειο και τον δευτερο της διαταξης στο δευτερο ταμειο, ειναι ιδια με την διαταξη 2-1, που στελνεις τον πρωτο της διαταξης στο δευτερο ταμειο και τον πρωτο της διαταξης στο πρωτο ταμειο).

Προτεινω, χωρις να ειμαι σιγουρος, μεσα στους 500 επιβατες να μπλεξουμε 11 φορες τον αριθμο 0. Ο αριθμος 0 ειναι διαχωριστικο, δηλαδη οτι βρισκεται αναμεσα σε δυο μηδενικα, πηγαινει στο αντιστοιχο ταμειο (επειδη παντα η πρωτη κι η τελευταια θεση θα ειναι μηδενικα με αυτη την θεωρηση, ειναι χαζο να βαλουμε 11 μηδενικα, βαζουμε 9 λοιπον! ).
Πλεον ειναι ενα προβλημα αντιμεταθεσεων, οπου ενα αντικειμενο εμφανιζεται 9 φορες, δηλαδη 509! / 9!
Στην προηγουμενη περιπτωση θα εβγαζε 3! / 1! = 6, που ειναι κι η σωστη απαντηση.

+1
Oυσιαστικα έχουμε το πρόβλημα τοποθέτησης n διακεκριμένων σφαιριδίων σε m διακεκεριμένα κουτιά όπου ΕΧΕΙ σημασία η σειρά      =(m+n-1)! / (m-1)!   άρα τελική λύση 500!*[ 509! / 9! ]

Παιδες ξερει κανεις τι παιζει με το θεμα 1 ερωτημα β) και γ) απο σεπτεβρη του 14;

Για το 1β) νομιζω για κάθε μετάθεση των 500 επιβατών (500!) έχεις πρόβλημα 500 διακεκριμένων ατόμων σε 10 διακεκριμένα ταμεία που μας βγάζει 500^10 τρόπους. Άρα συνολικά έχεις 500!*500^10 τρόπους.
Το 1γ) σε ενδιαφέρει και πόσοι και ποιοι επιβάτες πάνε στα ταμεία. Άρα είναι διακεκριμένοι για το πρόβλημα. Άρα θα πάρουμε εκθετική γεννήτρια συνάρτηση που θα αρχίζει από τον τον όρο x²⁰/20! και θα τελειώνει στο όρο x¹⁰⁰/100! και για τα 10 ταμεία. Άρα θα έχεις (x²⁰/20! +x²¹/21!+....+x¹⁰⁰/100!)¹⁰ και θα σε ενδιαφέρει ο συντελεστής του x⁵⁰⁰/500!

Για το 1β δες αυτό που έγραψα παραπάνω.Η λύση σου θα ήταν σωστή αν ΔΕΝ μας ενδιέφερε η σειρά στα ταμεία.Για το 1γ  +1 συμφωνώ μαζί σου.

[nvog1993]

Παιδες ξερει κανεις τι παιζει με το θεμα 1 ερωτημα β) και γ) απο σεπτεβρη του 14;

Για το 1β) νομιζω για κάθε μετάθεση των 500 επιβατών (500!) έχεις πρόβλημα 500 διακεκριμένων ατόμων σε 10 διακεκριμένα ταμεία που μας βγάζει 500^10 τρόπους. Άρα συνολικά έχεις 500!*500^10 τρόπους.

Για το 1β νομιζω παει διαφορετικα. Γιατι αν σκεφτουμε το πολυ απλουστερο προβλημα των 2 ανθρωπων σε 2 ταμεια, η λυση σου βγαζει 8 ενω η σωστη ειναι 6. Αυτο βγαινει γιατι δυο διαφορετικα permutations μπορει να καταληγουν στο ιδιο πραγμα (πχ η διαταξη 1-2, αν μετα μοιρασεις τον πρωτο της διαταξης στο πρωτο ταμειο και τον δευτερο της διαταξης στο δευτερο ταμειο, ειναι ιδια με την διαταξη 2-1, που στελνεις τον πρωτο της διαταξης στο δευτερο ταμειο και τον πρωτο της διαταξης στο πρωτο ταμειο).

Προτεινω, χωρις να ειμαι σιγουρος, μεσα στους 500 επιβατες να μπλεξουμε 11 φορες τον αριθμο 0. Ο αριθμος 0 ειναι διαχωριστικο, δηλαδη οτι βρισκεται αναμεσα σε δυο μηδενικα, πηγαινει στο αντιστοιχο ταμειο (επειδη παντα η πρωτη κι η τελευταια θεση θα ειναι μηδενικα με αυτη την θεωρηση, ειναι χαζο να βαλουμε 11 μηδενικα, βαζουμε 9 λοιπον! ).
Πλεον ειναι ενα προβλημα αντιμεταθεσεων, οπου ενα αντικειμενο εμφανιζεται 9 φορες, δηλαδη 509! / 9!
Στην προηγουμενη περιπτωση θα εβγαζε 3! / 1! = 6, που ειναι κι η σωστη απαντηση.

+1
Oυσιαστικα έχουμε το πρόβλημα τοποθέτησης n διακεκριμένων σφαιριδίων σε m διακεκεριμένα κουτιά όπου ΕΧΕΙ σημασία η σειρά      =(m+n-1)! / (m-1)!   άρα τελική λύση 500!*[ 509! / 9! ]

Παιδες ξερει κανεις τι παιζει με το θεμα 1 ερωτημα β) και γ) απο σεπτεβρη του 14;

Για το 1β) νομιζω για κάθε μετάθεση των 500 επιβατών (500!) έχεις πρόβλημα 500 διακεκριμένων ατόμων σε 10 διακεκριμένα ταμεία που μας βγάζει 500^10 τρόπους. Άρα συνολικά έχεις 500!*500^10 τρόπους.
Το 1γ) σε ενδιαφέρει και πόσοι και ποιοι επιβάτες πάνε στα ταμεία. Άρα είναι διακεκριμένοι για το πρόβλημα. Άρα θα πάρουμε εκθετική γεννήτρια συνάρτηση που θα αρχίζει από τον τον όρο x²⁰/20! και θα τελειώνει στο όρο x¹⁰⁰/100! και για τα 10 ταμεία. Άρα θα έχεις (x²⁰/20! +x²¹/21!+....+x¹⁰⁰/100!)¹⁰ και θα σε ενδιαφέρει ο συντελεστής του x⁵⁰⁰/500!

Για το 1β δες αυτό που έγραψα παραπάνω.Η λύση σου θα ήταν σωστή αν ΔΕΝ μας ενδιέφερε η σειρά στα ταμεία.Για το 1γ  +1 συμφωνώ μαζί σου.

A εντάξει. Είχα δει άλλο τύπο από τις ασκήσεις που έλεγε για τοποθέτηση διακεκριμένων σφαιρών σε διακεκριμένα κουτιά αλλά δεν είχα δει ότι έλεγε οτι δεν μας ενδιαφέρει η σειρά τοποθέτησης! Thanks!

[alextsigilis]

Ρε αδέρφια τι παίζει με το 2ο 2ο Θέμα του Ιουνίου του 2017;

Μόλις βρήκα ένα 4 κανονικό γράφημα, διμερές.

Το Κ_4,4

[blackmirror]

γνωμη για λύσεις θεμαΑ Σεπτ2014;

[panos98]

γνωμη για λύσεις θεμαΑ Σεπτ2014;

ολα σωστα εκτος απο το γ) θεωρω οτι πρεπει  να παρεις γενητρια της μορφης  χ^20/20! +...+χ^100/100!

[blackmirror]

ολα σωστα εκτος απο το γ) θεωρω οτι πρεπει  να παρεις γενητρια της μορφης  χ^20/20! +...+χ^100/100!

οντως.. το λεγαν και πιο πανω τα παιδια δεν το προσεξα