Θέμα: Πίνακες Ομοιότητα

Εμφάνιση ενός μόνο μηνύματος
  #12  
Παλιά 01-08-12, 12:52
kapetang Ο χρήστης kapetang δεν είναι συνδεδεμένος
Όνομα: Γιώργος
Έκδοση λογισμικού Office: Ms-Office 2010
Γλώσσα λογισμικού Office: Ελληνική, Αγγλική
 
Εγγραφή: 18-06-2010
Μηνύματα: 3.674
Προεπιλογή

Δημήτρη, Καλημέρα

Παρακάτω εκφράζω κάποιες σκέψεις για τη μαθηματική προσέγγιση του θέματος.

Με βάση τις ιδιότητες τις ομοιότητας (ανακλαστική α~α, αντιμεταθετική α~β => β~α, μεταβατική α~β, β~γ =>α~γ και α~γ, β~γ => α~β) καταλήγουμε στο εξής:

Αν τα σύνολα Α και Β απαρτίζονται από όμοια στοιχεία και έχουν κοινό στοιχείο (η τομή τους δεν είναι το κενό σύνολο) τότε τα στοιχεία της ένωσης των συνόλων θα είναι όμοια.

Υποθέτουμε ότι ο πίνακας στον οποίο θέλουμε να προσδιορίσουμε τα όμοια έχει n γραμμές και μία στήλη του περιέχει την τιμή Α(i) που είναι ένα σύνολο όμοιων στοιχείων.

Συνοπτικά για να προσδιορίσουμε όλα τα όμοια θα μπορούσαμε να εφαρμόσουμε τον ακόλουθο αλγόριθμο:

Κώδικας:
1. Για i=1 έως n-1
	Για j=i+1 έως n
		Αν Α(i) τομή A(j) μη κενό σύνολο
			Θέσε Α(i)= Α(i) ένωση Α(j) και Α(j)= με το νέο Α(i)
2. Αφού τελειώσουν οι παραπάνω βρόχοι και εφόσον υπήρξαν μη κενές τομές θα πρέπει να επαναληφθούν μέχρι σε κάποια επανάληψη οι τομές να γίνουν όλες κενές.

3. Αφαίρεση από τα σύνολα Α(i) του ανακλαστικού (ταυτοτικού) στοιχείου.

Το πλήθος των επαναλήψεων στους δύο βρόχους ισούται με τους συνδυασμούς των n ανά 2 και αυξάνει ραγδαία.

Κατά προσέγγιση είναι n^2/2 (για 100 εγγραφές είναι 5.000 και για 1000 500.000)

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

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

Φυσικά εσύ ξέρεις τις απαιτήσεις της βάσης και εσύ αποφασίζεις.


Φιλικά/Γιώργος
Απάντηση με παράθεση