csd::Τμημα επιστημης υπολογιστων προγραμμα σπουδων

Ξεκίνησε από manoskouts, 06 Μαΐου 2017, 12:47:08 ΠΜ

« προηγούμενο - επόμενο »

manoskouts

Γεια σας, ειμαι 18 και ασχολουμαι εδω και 2 χρονια με το προγραμματισμο και εχω φτασει σε ενα ικανοποιητικο επιπεδο δλδ μπορω να δουλεψω ως freelancher,να φτιαξω διαφορα πολυμπιζιλα προγραμματα ,εφαρμογες κτλ.Σε αυτα τα 2 χρονια εχω μαθει πολλες γλωσσες προγραμματισμου οπως η c++,java,c# και python.
Θα ειθελα την βοηθεια σας με το προγραμμα σπουδων του csd::τμημα επιστημης υπολογιστων του ηρακλειο γιατι δεν βγαζω ακρη.Υπαρχουν μονο 2 μαθηματα προγραμματισμου για c++ kai java αυτο σημαινει οτι δεν κανουνε αρκετη πρακτικη στο τμημα?
ποσο καιρο κανουν πρακτικη στο τμημα γιατι σκεφτομαι να μην περασω καν σε πανεπηστημιο επειδη μπορει  να χασω 4 χρονια τις ζωης μου κανοντας μονο μαθηματικα! Ευχαριστω!

GiannisP

Αρχικα φαινεται οτι εχεις στο μυαλο σου τον αγνο προγραμματισμο και οχι τοσο την επιστημη υπολογιστων. Εχω αποφοιτησει απο αλλο τμημα αλλα ειμαι σιγουρος οτι και στο αντιστοιχο τμημα στην Κρητη κανουν αρκετη θεωρια οπως και καμποσα μαθηματικα. Ειναι Πανεπιστημιο αλλωστε. Αμα δεν θες να μπεις καν σ'αυτη την νοοτροπια τοτε καλυτερα συνεχισε να ασχολεισαι μονος σου με τον προγραμματισμο αυτο καθ'αυτο. Υπαρχουν απειρα tutorials,video και οτιδηποτε θες και αφου τελειωσεις ολα τα βασικα ολα ειναι θεμα εμπνευσης και δημιουργιας. Δουλεια θα βρεις, λεφτα θα εχεις αρα ολα καλα  ;D  ;D

Παρεπιπτοντως μην ακουω "θα χασω 4 χρονια απο τη ζωη μου κανοντας μονο μαθηματικα" γιατι με ποναει λιγο  :'(

apoldem

4 χαμένα χρόνια θα είναι αυτά που θα διαβάζεις "μόνος σου". Εγώ διάβαζα "μόνος μου" 17 χρόνια πριν αποφασίσω να πάω σε πανεπιστήμιο. Τα 17 αυτά χρόνια τα θεωρώ χαμένα.
Το πανεπιστήμιο απευθύνεται κυρίως σε ανθρώπους σαν εσένα. Που έχουν ενδιαφέρον για τον προγραμματισμό. Πρέπει να δεις έναν-έναν τους τομείς, τις κατευθύνσεις, κάποιους βασικούς αλγόριθμους, ..., πριν αποφασίσεις τι σε ενδιαφέρει. Χωρίς να παραβλέψουμε πόσο θα ομορφύνει το βιογραφικό σου με ένα πτυχίο βαθμού πάνω από 8 (και γιατί όχι και 9).
Όσον αφορά τα μαθηματικά, κάνεις τεράστιο λάθος. Ο προγραμματιστής είναι από την φύση του problem solver. Δεν μπορείς να είσαι problem solver και να μην ξέρεις βασικά μαθηματικά. Πάρα πολλοί αλγόριθμοι στηρίζονται σε μαθηματικά. Οι πιο σύγχρονοι αλγόριθμοι στηρίζονται ακόμη περισσότερο σε μαθηματικά. Εσύ μάλιστα θα πρέπει να βρεις δικούς αλγόριθμους ή να συνδυάσεις τους ήδη υπάρχοντες. Δεν μπορώ να καταλάβω πως θα γίνουν αυτά χωρίς μαθηματικά. Εκτός αν με το "προγραμματισμός" εννοείς κατασκευή σελίδων, σχεδίαση φορμών, τι χρώμα θα έχει το background και τι γραμματοσειρά θα έχει το πλαίσιο διαλόγου.

gbougioukas

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

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

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

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

Πιο συγκεκριμένα, ζητείται να συμπληρωθεί η παρακάτω συνάρτηση, ας πούμε σε Java:

     /**
     *
     * @param employees: μονοδιάστατη διάταξη των (500) υπαλλήλων της εταιρείας
     * @param pairs: δισδιάστατη διάταξη με τα ζεύγη τσακωμένων υπαλλήλων - εάν null, τότε δεν υπάρχουν τσακωμένοι υπάλληλοι
     * @return: μονοδιάστατη διάταξη 150 υπαλλήλων που θα πάνε στην δεξίωση - null αν μια τέτοια διάταξη δεν υπάρχει
     */
    String[] get150(String[] employees, String[][] pairs) {
        String[] list150 = null;
        //...
        return list150;
    }
Γιώργος Μπουγιούκας
Computer Science (BSc), Bioinformatics & Neuroinformatics (MSc)
https://gbougioukas.wordpress.com/
https://apothesis.eap.gr/handle/repo/54953

itt

Παράθεση από: gbougioukas στις 09 Μαΐου 2017, 10:54:01 ΠΜ
Τέλος, το "ικανοποιητικό επίπεδο" όσον αφορά τον προγραμματισμό εφαρμογών είναι...σχετικό. Για παράδειγμα, είναι ικανοποιητικό το επίπεδο ενός προγραμματιστή που "δηλώνει παραίτηση" όταν του αναθέσουν να φτιάξει μια εφαρμογή για το παρακάτω σενάριο;

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

Πιο συγκεκριμένα, ζητείται να συμπληρωθεί η παρακάτω συνάρτηση, ας πούμε σε Java:

     /**
     *
     * @param employees: μονοδιάστατη διάταξη των (500) υπαλλήλων της εταιρείας
     * @param pairs: δισδιάστατη διάταξη με τα ζεύγη τσακωμένων υπαλλήλων - εάν null, τότε δεν υπάρχουν τσακωμένοι υπάλληλοι
     * @return: μονοδιάστατη διάταξη 150 υπαλλήλων που θα πάνε στην δεξίωση - null αν μια τέτοια διάταξη δεν υπάρχει
     */
    String[] get150(String[] employees, String[][] pairs) {
        String[] list150 = null;
        //...
        return list150;
    }

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

Αρχικά, κανένας επαγγελματίας προγραμματιστής δεν θα είχε πρόβλημα one way or the other να επιλύσει ένα πρόβλημα που ανάγεται σε SMP. Έπειτα αυτό που έγραψες δεν έχει καμία απολύτως σχέση με το τι προβλήματα αντιμετωπίζεις στην ανάπτυξη εφαρμογών. Τέλος τα παραδείγματα γενικά σε αυτή την συζήτηση δεν έχουν νόημα, δεδομένου ότι υπάρχουν πάρα πολλά διαφορετικά domains για τα οποία αναπτύσσονται εφαρμογές. Διαφορετικό skillset χρειάζεται κάποιος που γράφει ERP, διαφορετικό κάποιος που γράφει device drivers και διαφορετικό κάποιος που αναπτύσσει επιστημονικές εφαρμογές.




gbougioukas

Παράθεση από: itt στις 09 Μαΐου 2017, 01:37:23 ΜΜ
Όχι, δεν είναι καθόλου σχετικό. Η σχολή δεν σου παρέχει ούτε χρειάζεται να σου παρέχει ικανοποιητικό επίπεδο στην ανάπτυξη εφαρμογών, με τον τρόπο που την αντιμετωπίζει το industry. Το πανεπιστήμιο υπάρχει για να σου διδάξει πώς μπορείς να έχεις μια επιστημονική προσέγγιση στην επίλυση κάποιων κλάσεων προβλημάτων. Αυτή την προσέγγιση είναι στο χέρι σου να την εφαρμόσεις στην εργασία σου, το αν θα το καταφέρεις ή όχι δεν έχει καμία σχέση με το πανεπιστήμιο.

Αρχικά, κανένας επαγγελματίας προγραμματιστής δεν θα είχε πρόβλημα one way or the other να επιλύσει ένα πρόβλημα που ανάγεται σε SMP. Έπειτα αυτό που έγραψες δεν έχει καμία απολύτως σχέση με το τι προβλήματα αντιμετωπίζεις στην ανάπτυξη εφαρμογών. Τέλος τα παραδείγματα γενικά σε αυτή την συζήτηση δεν έχουν νόημα, δεδομένου ότι υπάρχουν πάρα πολλά διαφορετικά domains για τα οποία αναπτύσσονται εφαρμογές. Διαφορετικό skillset χρειάζεται κάποιος που γράφει ERP, διαφορετικό κάποιος που γράφει device drivers και διαφορετικό κάποιος που αναπτύσσει επιστημονικές εφαρμογές.

Το παράδειγμα του προβλήματος που παρέθεσα παραπάνω μου το έθεσαν σε συνέντευξη - προγραμματιστή εφαρμογών ζητούσαν. Είναι αρκετά δύσκολο να ανταπεξέλθει κανείς σε μια τέτοια ερώτηση χωρίς ένα γενικότερα ισχυρό υπόβαθρο στα μαθηματικά - μια σχολή πληροφορικής παίζει καθοριστικό ρόλο σε τέτοια θέματα όπως είπα και παραπάνω (και όπως θεωρεί άλλωστε και ο ερωτών), αλλά δεν είναι απαραίτητη, όλα τα μαθηματικά είναι εδώ στο διαδίκτυο. Υπενθυμίζω ότι το αρχικό ερώτημα του thread έχει να κάνει ακριβώς με την γενικότερη σχέση προγραμματισμού-μαθηματικών.
Γιώργος Μπουγιούκας
Computer Science (BSc), Bioinformatics & Neuroinformatics (MSc)
https://gbougioukas.wordpress.com/
https://apothesis.eap.gr/handle/repo/54953

bugman

Το πρόβλημα πάντως είναι ωραίο και θα μπορούσε να μπει σαν άσκηση σε νέο θέμα!

itt

Παράθεση από: gbougioukas στις 09 Μαΐου 2017, 02:26:11 ΜΜ
Το παράδειγμα του προβλήματος που παρέθεσα παραπάνω μου το έθεσαν σε συνέντευξη - προγραμματιστή εφαρμογών ζητούσαν. Είναι αρκετά δύσκολο να ανταπεξέλθει κανείς σε μια τέτοια ερώτηση χωρίς ένα γενικότερα ισχυρό υπόβαθρο στα μαθηματικά - μια σχολή πληροφορικής παίζει καθοριστικό ρόλο σε τέτοια θέματα όπως είπα και παραπάνω (και όπως θεωρεί άλλωστε και ο ερωτών), αλλά δεν είναι απαραίτητη, όλα τα μαθηματικά είναι εδώ στο διαδίκτυο. Υπενθυμίζω ότι το αρχικό ερώτημα του thread έχει να κάνει ακριβώς με την γενικότερη σχέση προγραμματισμού-μαθηματικών.

Ναι οκ και εμένα μου έχει ζητηθεί να φτιάξω AVL δέντρο, να λύσω ένα σχετικά εύκολο VRPTW και άλλα τέτοια χαριτωμένα. Καμία από τις θέσεις εργασίας δεν είχε κάποια χρησιμότητα για αυτά τα πράγματα. Με αυτές τις ερωτήσεις υποτίθεται ότι τεστάρεις τον άλλον σε general problem solving.

Γενικά νομίζω ότι πάντως συμφωνούμε. Είναι πολύ πιο λογικό και desirable να θες το πανεπιστήμιο να σου δώσει ένα δυνατό background στα μαθηματικά με ότι αυτό συνεπάγεται και όχι να βρεθεί άλλος ένας καημένος να σου διδάσκει τη java του 2004.

evry

Σχετικά με το πρόβλημα με τους υπαλλήλους της εταιρίας. Τι λύση περιμένουν να δώσει κάποιος στη συνέντευξη? Αν δώσεις λύση brute force με κάποιες μικροβελτιώσεις, π.χ. ξεκινάω από αυτόν με τα λιγότερα constraints (ή φτιάχνω μια καλύτερη ευριστική συνάρτηση) σε σχέση με αυτούς που έχω ήδη θεωρείται αποδεκτό? Θέλουν βέλτιστη λύση?
Επίσης το πρόβλημα όπως τέθηκε μπορεί να έχει πολλές λύσεις. Θα περίμενα να ζητήσουν τον μεγαλύτερο αριθμό υπαλλήλων που μπορούν να είναι μαζί. Περιμένουν να το συνδέσεις με το max clique πρόβλημα ή να το δεις σαν csp?
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

bugman

Το πρόβλημα μου άρεσε και το έλυσα.


οι  κανόνες ((1,3),(7,4),(6,3),(3,2),(6,1),(4,7),(1,7),(4,6),(1,4),(3,7), (8,9),(7,8),(5,2),(10,3))
Στην εικόνα είναι η λύση για 10 άτομα από τα οποία βγάζουμε τέσσερα (μπορεί κανείς να το μεγαλώσει)
Πρέπει να έχει κανείς μια λίστα με κλειδί το καθένα άτομο που αναφέρεται στα ζεύγη πχ (1,3) θα υπάρχει και για 1 και 3, και σε κάθε κλειδί θα υπάρχει άλλη λίστα με όλα τα άτομα που εξαιρούνται.
Αρχικά ανακατεύουμε τη δομή με τα 10 (ή 500) νούμερα -κωδικούς υπαλλήλων- για να έχουμε μια εκ των λύσεων.
θέλει πέρασμα σε διπλή επανάληψη (η πρώτη από 1 έως 9 και η δεύτερη από +1 στο προηγούμενο έως 10 ). Απλά σε κάθε διπλή επανάληψη θα κοιτάμε αν υπάρχει το κλειδί στην λίστα, αν ναι τότε θα κοιτάμε αν το δεύτερο υπάρχει στην λίστα που γυρίζει το κλειδί, αν ναι τότε το δεύτερο το μηδενίζουμε (από το νούμερο που δείχνει τον υπάλληλο σε μηδέν). Στο τέλος έχουμε ένα πίνακα (ή ότι άλλη δομή) που περιέχει αριθμούς υπαλλήλων (κωδικούς) και μηδενικά. Βγάζουμε τα μηδενικά (στη περίπτωση εδώ έχουμε μια στοίβα) και μένουν μόνο οι αριθμοί. Διαλέγουμε τους πρώτους έστω 4 (ή 150 για το πρόβλημα με τους 500 υπαλλήλους).
Σε ΓΛΩΣΣΑ θα έπρεπε ο πίνακας κανόνων αντί σε λίστα με λίστες να γίνει σε 500Χ500 και να μπεί 1 αν ισχύει ή 0 αν όχι. Απλά τα κλειδιά απαραίτητα θα είναι αντίστοιχα με τους δείκτες (ενώ με την λίστα έχούμε ότι θέλουμε). Άρα ένας πίνακας 500 νούμερα με 1 οκ και αργότερα 0 (εκτός) και ένας δυο διαστάσεων 500Χ500

gbougioukas

@bugman

Είναι εύκολο να παραθέσεις τον κώδικα, να το κάνουμε λίγο πιο συγκεκριμένο;


Γιώργος Μπουγιούκας
Computer Science (BSc), Bioinformatics & Neuroinformatics (MSc)
https://gbougioukas.wordpress.com/
https://apothesis.eap.gr/handle/repo/54953

bugman

Η λύση είναι στο blog σε Μ2000. Με πίνακες όμως γράφεται και σε Γλώσσα.

gbougioukas

Δυστυχώς δεν γνωρίζω την γλώσσα M2000. Anyway, είσαι σίγουρος ότι ο κώδικας που παρουσιάζεις δουλεύει και για 500 υπαλλήλους, από τους οποίους ζητάμε 150 με 100.000 ας πούμε μη-επιτρεπόμενα ζεύγη? "Δουλεύει", εννοώ δίνει αποτέλεσμα σε εύλογο διάστημα, όχι σε ένα δισεκατομμύριο χρόνια...
Γιώργος Μπουγιούκας
Computer Science (BSc), Bioinformatics & Neuroinformatics (MSc)
https://gbougioukas.wordpress.com/
https://apothesis.eap.gr/handle/repo/54953

bugman

Ναι σίγουρα. Στην αρχή το είχα φτιάξει πιο χρονοβόρο αλλά βελτιώθηκε με τη λίστα. Δουλεύει εσωτερικά με συνάρτηση κατακερματισμού. Επειδή βγαίνουν νωρίς κάποια νούμερα, γίνονται 0, τα αφήνει η επανάληψη με μια εντολή Συνέχεια. Λογικά σε Γλώσσα με μια Αν θα βγάζει εκτός το κώδικα που κοιτάμε τον πίνακα (λίστες δεν έχουμε στη Γλώσσα).

gbougioukas

Παράθεση από: bugman στις 10 Μαΐου 2017, 01:05:40 ΜΜ
Ναι σίγουρα. Στην αρχή το είχα φτιάξει πιο χρονοβόρο αλλά βελτιώθηκε με τη λίστα. Δουλεύει εσωτερικά με συνάρτηση κατακερματισμού. Επειδή βγαίνουν νωρίς κάποια νούμερα, γίνονται 0, τα αφήνει η επανάληψη με μια εντολή Συνέχεια. Λογικά σε Γλώσσα με μια Αν θα βγάζει εκτός το κώδικα που κοιτάμε τον πίνακα (λίστες δεν έχουμε στη Γλώσσα).

Τότε, τσέκαρε μήπως μπορείς να αιτηθείς το βραβείο του ενός εκατομμυρίου δολαρίων από το Clay.

http://www.claymath.org/millennium-problems/p-vs-np-problem

Γιώργος Μπουγιούκας
Computer Science (BSc), Bioinformatics & Neuroinformatics (MSc)
https://gbougioukas.wordpress.com/
https://apothesis.eap.gr/handle/repo/54953

bugman

Αν παρατήρησες στην εικόνα παραπάνω το πρόβλημα δίνει μια λύση (από τις πολλές) βάσει ενός πίνακα (με λίστες γίνεται αυτός), όπου τα ζευγάρια πχ 1,3 δηλώνονται και ως 3,1, και έτσι η σειρά 1 έχει το 3 ως μη αποδεκτό και η σειρά 3 το ένα ως μη αποδεκτό.
Αντί να ψάχνουμε τις λίστες αυτές σειριακά, δουλεύουμε με πίνακα κατακερματισμού και βγαίνει άμεσα η αναζήτηση (αν υπάρχει ή όχι). Υπάρχει και άλλος τρόπος, να κοιτάμε τα νούμερα της λίστας "αποκλεισμών" (για κάθε νούμερο που εξετάζουμε), αλλά με την προυπόθεση ότι και η λίστα των υπαλλήλων είναι και αυτή με κλειδί. Έτσι αν έχουμε π.χ. 30 σχέσεις (τριάντα ζευγάρια όπως το (1,3)), ξεκινάμε από το πρώτο που θεωρούμε ότι θα μείνει, έστω το 1 και "αποκλείουμε" το 3 (βάζουμε 0 εκεί που ήταν 3), μετά πάμε στο επόμενο ζευγάρι, αν το πρώτο νούμερο το βρίσκουμε στο πίνακα 0 τότε το αφήνουμε και πάμε στο επόμενο, μέχρι που και τα τριάντα θα τελειώσουν. Εδώ οι διαφορετικές λύσεις βγαίνουν με ανακάτεμα των κανόνων (των ζευγαριών).
Και ο πρώτος τρόπος (όπως την υλοποίησα) όπως και ο άλλος τρόπος, έχουν την εφαρομογή ανάλογα με το τι έχουμε. Αν έχουμε περισσότερα ζευγάρια από του υπαλλήλους τότε συμφέρει ο πρώτος, αν έχουμε πολλούς υπαλλήλους με μικρό αριθμό ζευγαριών συμφέρει ο δεύτερος.

Ασφαλώς αν μιλάμε για έναν αλγόριθμο που θα έβρισκε όλες τις λύσεις..τότε θέλουμε χιλιετίες για να τις βρούμε! Να προσθέσω εδώ ότι στο δικό μου αλγόριθμο δεν επιλέγω μια τυχαία λύση, ώστε να δω αν βγαίνει, αλλά ξεκινάω με την παραδοχή ότι ο πρώτος διαθέσιμος από μια στοίβα είναι "καλεσμένος", και αποκλείω από τη στοίβα όσους δεν είναι συμβατοί με αυτόν, μετά πάω στον επόμενο (αν είναι 0 τότε πάω στο επόμενο κ.ο.κ). Για το λόγο αυτό πριν ξεκινήσω κάνω ένα ανακάτεμα. Έτσι κάθε φορά που τρέχουμε το πρόγραμμα έχουμε άλλη λύση! Επειδή γράφονται σε στοίβα, στο τέλος αφαιρούνται τα κενά και ζητάμε έναν αριθμό, αλλά θα πάρουμε λιγότερα αν δεν υπάρχει αυτός ο αριθμός, άρα ενδέχεται η λύση που θα βρεθεί να μην είναι ικανοποιητική! Οπότε πάμε για άλλη!



gbougioukas

Παράθεση από: bugman στις 10 Μαΐου 2017, 02:50:43 ΜΜ
Ασφαλώς αν μιλάμε για έναν αλγόριθμο που θα έβρισκε όλες τις λύσεις..τότε θέλουμε χιλιετίες για να τις βρούμε!

Όχι, δεν μιλάμε για αλγόριθμο που θα έβρισκε όλες τις λύσεις, μία αρκεί.
Γιώργος Μπουγιούκας
Computer Science (BSc), Bioinformatics & Neuroinformatics (MSc)
https://gbougioukas.wordpress.com/
https://apothesis.eap.gr/handle/repo/54953

bugman

Η δεύτερη λύση, με την χρήση μόνο των κανόνων είναι πολύ γρήγορη, με το που πατάς το enter παίρνεις την απάντηση!
Αυτό μάλιστα έτρεξε σε Linux με Wine. Δεν χρειάστηκε λίστα, μόνο πίνακες!

ο κώδικας είναι στο blog.

gbougioukas

Από όσο μπορώ να καταλάβω από τον κώδικα, πρόκειται για 11 μη-επιτρεπτά ζεύγη. Τι γίνεται για 100.000 μη-επιτρεπτά ζεύγη;
Γιώργος Μπουγιούκας
Computer Science (BSc), Bioinformatics & Neuroinformatics (MSc)
https://gbougioukas.wordpress.com/
https://apothesis.eap.gr/handle/repo/54953

apoldem

Το πρόβλημα με την δεξίωση είναι πρόβλημα γράφων. Κατασκευάζουμε αρχικά έναν πλήρη γράφο με τους 500 υπαλλήλους (όλοι είναι συνδεδεμένοι με όλους). Μετά αφαιρούμε τις ακμές με αυτούς που είναι μαλωμένοι. Στον γράφο που θα μείνει ψάχνουμε αν υπάρχει έστω μία κλίκα μεγέθους 150.
Για το πρόβλημα της εύρεσης κλίκας δεδομένου μεγέθους: https://en.wikipedia.org/wiki/Clique_problem#Cliques_of_fixed_size.

Απ' ότι λέει η wikipedia δεν υπάρχει κανένας έξυπνος αλγόριθμος. Το μόνο που μπορούμε να κάνουμε είναι να αποκλείσουμε τους υπαλλήλους με λιγότερες από 150 ακμές, αφού αυτοί σίγουρα δεν μπορούν να να συμμετέχουν σε καμιά κλίκα μεγέθους 150.

Στην χειρότερη περίπτωση (δλδ, κανένας δεν αποκλείεται & όλοι οι έλεγχοι αποτυγχάνουν λίγο πριν βρούμε μια κλίκα & κλίκα τελικά δεν υπάρχει) θα χρειαστούμε (500^150)*(150^2) συγκρίσεις. Παρόλα αυτά το πρόβλημα θεωρείται πολυωνυμικό ως προς το μέγεθος των υπαλλήλων, αφού το 150 είναι fixed και έτσι και το 500^150 είναι ένα πολυώνυμο βαθμού 150.

evry

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

Αυτά σε περίπτωση που κάποιος δεν ξέρει κάποιον γρήγορο αλγόριθμο για εύρεση μιας 150-κλίκας.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

bugman

Έχω βάλει δυο εκδόσεις. Η "Αργή" κάνει 2.2 δευτερόλεπτα για να δώσει τα 150 νούμερα (ταξινομημένα, γιατί στην αρχή τα έχει ανακατεμένα).
Η δεύτερη έκδοση είναι ακαριαία, και με πολύ μικρό κώδικα (μόνο πίνακες). Σε αυτήν ανακατεύω τη σειρά των κανόνων και μετά τους εφαρμόζω άμεσα, δηλαδή παίρνω το πρώτο νούμερο κοιτάω αν δεν έχει αποκλειστεί (Δεν έχει το 0 δηλαδή) και αν όντως δεν έχει παίρνω το δεύτερο και άμεσα αποκλείω το δεύτερο. Ουσιαστικά οι επαναλήψεις είναι όσοι οι κανόνες αλλά όχι σε όλο το μέγεθος του κώδικα γιατί αν έχει αποκλειστεί κάποιο άτομο, τότε δεν κοιτάμε το δεύτερο στο ζευγάρι (του κανόνα). Εδώ η τεχνική λέγεται lookup table. Οι υπάλληλοι είναι σε έναν πίνακα με σημαίες, έτσι ο υπάλληλος 123 έχει σημαία που δείχνει αν έχει αποκλειστεί ή όχι. Οι δείκτες του πίνακα είναι οι κωδικοί των υπαλλήλων. (το πρώτο πρόγραμμα δουλεύει και με νούμερα άσχετα μεταξύ τους, δηλαδή πραγματικούς κωδικούς).

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