Ευκλείδειος Αλγόριθμος και η πολυπλοκότητα του

[Guest 990498]

Καλησπέρα και πάλι
κόσμε εθισμένε στις θετικές επιστήμες και στο ίντερνετ.

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

• μιγαδικοί
• πραγματικοί
• σύνολο πολυωνύμων

Θα με βοηθούσε το οτιδήποτε, λινκς, βιβλιογραφία, πληροφορίες.
Ό,τι έχετε ευχαρίστηση.

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


Ευχαριστώ εκ των προτέρων.

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[Guest 990498]

Κανείς;

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[Ciela]

για το R και για τα πολυωνυμα έχει το βιβλιο εδω
στα αντιστοιχα κεφαλαια.
(επειδη βλεπω οτι δε φαινονται τα περιεχομενα κοιταξε στη σελιδα 19+ για το R και στην 108+ για το R[x])

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[Rempeskes]

Θιελα, δεν αναφέρεται σε ζητήματα πολυπλοκότητας το βιβλίο που παραθέτεις


Ούτε και εγώ βασικά είμαι εξπέρ στο ζήτημα, μα σκέφτομαι τα εξής.

- Πραγματικοί. Τα υπόλοιπα θα είναι πραγματικοί αριθμοί επίσης, οπότε ο αλγόριθμος - εξόν από αριθμήσιμο σύνολο- δεν θα τερματίζει σε πεπερασμένο αριθμό βημάτων. Οπότε ο αλγόριθμος είναι έναν βαθμό παραπάνω πολύπλοκος απ' ότι στην περίπτωση των ακεραίων.

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

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


Υγ. τι τα θες αυτά ρε μαν;

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[Guest 990498]

Για μία εργασία Ρεμπ,
χέσε μέσα δηλαδή,
ξέρεις κανένα βιβλίο να πάρω πληροφορίες από εκεί;

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.