25ος Πανελλήνιος Διαγωνισμός Πληροφορικής

Ξεκίνησε από Stop GOTO, 28 Οκτ 2012, 09:38:01 ΠΜ

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

Stop GOTO

Ποια είναι η γνώμη σας για το θέμα της Α' φάσης του 25ου ΠΔΠ ;

evry

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

Νίκος Αδαμόπουλος


evry

Στους ενδιαφέροντες συνδέσμους που έδωσε παραπάνω ο Νίκος, ψάχνοντας έριξα μια ματιά στις διαφάνειες του μαθήματος "Προγραμματισμός Ηλεκτρονικών Υπολογιστών" των ΗΜΜΥ του ΕΜΠ.
Έχουν πολύ ενδιαφέρον οι διαφάνειες 5-10 στις οποίες εκτός του οτι μας θυμιζει τι είναι πληροφορική έχει και έναν σχολιασμό σχετικά με το τι διδάσκεται στην δευτεροβάθμια εκπαίδευση και
προτείνει τι θα έπρεπε κανονικά να διδάσκεται.
http://courses.softlab.ntua.gr/progintro/slides-20121026.pdf
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

pgrontas

Φυσικά και έχουν δίκιο για το τι πρέπει να διδάσκεται.
Από την άλλη πρέπει να επισημάνω με αρκετή δόση απογοήτευσης, ότι γενικά οι πανεπιστημιακοί δεν έχουν κάνει τίποτε χειροπιαστό για να βοηθήσουν σε αυτό.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

dski

Παράθεση από: evry στις 07 Νοε 2012, 09:23:30 ΠΜ
Έχουν πολύ ενδιαφέρον οι διαφάνειες 5-10 στις οποίες εκτός του οτι μας θυμιζει τι είναι πληροφορική έχει και έναν σχολιασμό σχετικά με το τι διδάσκεται στην δευτεροβάθμια εκπαίδευση και
προτείνει τι θα έπρεπε κανονικά να διδάσκεται.
http://courses.softlab.ntua.gr/progintro/slides-20121026.pdf

+1 κι από εμένα.

"Δευτεροβάθμια εκπαίδευση
  Σκοπός: να μάθεις να σκέφτεσαι"

Νομίζω αυτή πρέπει να είναι η ουσία και ο κεντρικός στόχος του μαθήματος της πληροφορικής σε Γυμνάσιο και Λύκειο. Δυστυχώς για τον πάρα πολύ κόσμο (Υπουργείο, μαθητές, γονείς αλλά ακόμη και συνάδελφοι καθηγητές άλλων ειδικοτήτων) η πληροφορική παραμένει μάθημα εκμάθησης βασικών δεξιοτήτων χρήσης Η/Υ. Όταν στην Γ' Γυμνασίου, στην ερώτηση των μαθητών "κύριε τι θα μας χρειαστούν όλα αυτά με τη χελώνα κτλ" απαντώ ότι "θα σας μάθουν να σκέφτεστε" οι περισσότεροι με κοιτούν με απορία (τουλάχιστον)... Οι δε γονείς όταν έρχονται να πάρουν βαθμούς αναγνωρίζουν ότι η πληροφορική είναι σημαντικό μάθημα αφού πλέον όλα γίνονται με χρήση Η/Υ και τα παιδιά πρέπει να μάθουν να τους χειρίζονται...

Κατά την ταπεινή (και πιθανώς "αιρετική") μου άποψη η πληροφορική προσφέρεται ως μάθημα για την καλλιέργεια αναλυτικής και μεθοδικής σκέψης το ίδιο ή και περισσότερο από κλασσικά μαθήματα όπως τα μαθηματικά και η γεωμετρία καθώς το πεδίο εφαρμογών της είναι ευρύτερο και με τη χρήση του Η/Υ οι μαθητές δε λύνουν ένα πρόβλημα μόνο στο χαρτί αλλά έχουν τη δυνατότητα να υλοποιήσουν τη λύση τους και να τη δουν σε λειτουργία.

evry

Και μιας και μιλάμε για δύσκολες ασκήσεις (συνέχεια από άλλο Thread)
μόλις βγήκε το θέμα της 2ης φάσης του Πανελλήνιου Διαγωνισμού Πληροφορικής.
http://www.pdp.gr/files/25b/PDP_25_B_LYK.pdf

Τρελαίνομαι για θέματα που απευθύνονται σε μαθητές Λυκείου αλλά όχι με γνώσεις λυκείου
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

Νίκος Αδαμόπουλος

Και μην ξεχνάμε και το Γυμνάσιο, όπου έχει ξεχωριστό θέμα Β:
http://www.pdp.gr/Files/25b/PDP_25_B_GYM.pdf

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

Νίκος Αδαμόπουλος

Να σημειώσουμε ότι στο πλαίσιο προετοιμασίας του ΠΣΔ, λειτουργεί και το HelleniCO ( http://www.hellenico.gr/contest/ ), όπου όποιος θέλει κάνει εγγραφή και μπορεί να παίρνει μέρος σε online διαγωνισμούς επίλυσης ακήσεων.

Μάλιστα αυτή τη στιγμή είναι στον αέρα ο διαγωνισμός Ιανουαρίου (Online Διαγωνισμός Εξάσκησης Ιανουαρίου 2013 (Διάρκεια 19 Ιαν, 14:00 - 22 Ιαν, 22:00). Από τη στιγμή που θα κατεβάσεις τα θέματα (3 ασκήσεις) έχεις 4 ώρες να ανεβάσεις τις λύσεις σου.

Ψήνομαι  να δοκιμάσω αν και δεν έχω μεγάλο χρονικό περιθώριο, και θα πρέπει να βρω μια καλή δικαιολογία στη σύζυγο!

Νίκος Αδαμόπουλος

Παράθεση από: Νίκος Αδαμόπουλος στις 21 Ιαν 2013, 09:25:46 ΜΜ
Μάλιστα αυτή τη στιγμή είναι στον αέρα ο διαγωνισμός Ιανουαρίου (Online Διαγωνισμός Εξάσκησης Ιανουαρίου 2013 (Διάρκεια 19 Ιαν, 14:00 - 22 Ιαν, 22:00). Από τη στιγμή που θα κατεβάσεις τα θέματα (3 ασκήσεις) έχεις 4 ώρες να ανεβάσεις τις λύσεις σου.

Ψήνομαι  να δοκιμάσω αν και δεν έχω μεγάλο χρονικό περιθώριο, και θα πρέπει να βρω μια καλή δικαιολογία στη σύζυγο!

Διορθώνω: 4 είναι οι ασκήσεις...

Νίκος Αδαμόπουλος

Παράθεση από: Νίκος Αδαμόπουλος στις 21 Ιαν 2013, 09:25:46 ΜΜ
Ψήνομαι  να δοκιμάσω αν και δεν έχω μεγάλο χρονικό περιθώριο, και θα πρέπει να βρω μια καλή δικαιολογία στη σύζυγο!

Λοιπόν, δοκίμασα!

Ανέβασα λύσεις στα 3 από τα 4 θέματα. Στο 1ο θέμα μου πήρε περίπου 25 λεπτά, στο 2ο περίπου 50 λεπτά, στο 3ο πάνω από ώρα. Όμως το 3ο με ταλαιπώρησε γιατί ενώ ανέβασα τη λύση, μου την έβγαζε "απέτυχε". Αφού ασχολήθηκα με τη μελέτη του 4ου θέματος, και είδα ότι δεν θα προλάβαινα να βρω λύση, επανήλθα στο 3ο θέμα, και αφού έφαγα πάνω από μισή ώρα ψάχνοντας μήπως έχω κάνει κάποιο λογικό λάθος στη σκέψη, διαπίστωσα ότι απλώς είχα αφήσει σαν όνομα του αρχείου εξόδου, το όνομα του αρχείου εξόδου του 2ου θέματος. Το διόρθωσα και το πήρε! Τελικά μου απέμειναν περίπου 20 λεπτά, και εγκαταλείπω τελείως το 4ο θέμα. Αναμένουμε τα τελικά αποτελέσματα!

evry

Μια και χθες το βράδυ από ότι είδα τέλειωσε η προθεσμία για την υποβολή του θέματος της Β' φάσης του ΠΔΠ,
επαναφέρω το θέμα μήπως ασχολήθηκε κανείς με αυτό.

Λοιπόν για να είμαι ειλικρινής στην αρχή μόλις το είδα το μυαλό μου πήγε σε αλγορίθμους σχετικές με συνεκτικές συνιστώσες στην αρχή αλλά τελικά κατέληξα στον αλγόριθμο του floyd για την εύρεση (όχι του συντομότερου) αλλά του μεγαλύτερου μονοπατιού σε γράφο.
Μετά όμως είδα ότι οι περιορισμοί του προβλήματος δεν μου επέτρεπαν να ορίσω πίνακα 2 διαστάσεων αυτού του μεγέθους, εκτός φυσικά αν είχα μνήμη μερικών TeraByte  :laugh:

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

http://www.pdp.gr/files/25b/PDP_25_B_LYK.pdf

Νομίζω ότι είναι το καλύτερο πρόβλημα που έχω δει σε Πανελλήνιο Διαγωνισμό Πληροφορικής, επειδή απαιτεί αρκετή σκέψη και αυτό που λείπει από πολλά προβλήματα. ΑΝΑΛΥΣΗ.
Η λύση του είναι ουσιαστικά 5-6 γραμμές, αλλά η ιδέα είναι που μετράει.
Θα μπορούσε να μπει ως άσκηση και στην Ανάπτυξη Εφαρμογών, αλλά με κάποιες υποδείξεις γιατί έτσι είναι αρκετά δύσκολο για μαθητές. Έχουν όμως τις γνώσεις να το λύσουν.

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

Stop GOTO

Μήπως ξέρετε πότε θα αναρτηθούν λύσεις του θέματος της Β΄φάσης γιατί , το δούλεψα αρκετά (δεν πέρασα) και είμαι πολύ περίεργος να δω τη λύση του (πιστεύω ότι οι γνώσεις του Λυκείου δεν αρκούν ούτε στο ελάχιστο)

evry

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

#include <fstream>

using namespace std;

int dist[1000001];
int N, M, x, y, longestPath, count;
int main()
{
    ifstream fin("scidinner.in");
    ofstream fout("scidinner.out");
    fin >> N >> M;
    for (int i=1; i<=N; i++) dist[i] = 0;

    for (int i=1; i<=M; i++) {
        fin >> x >> y;
        dist[y] = x;
    }
    longestPath=0;
    for (int i=1; i<=N; i++) {
        count = 1;  int j = i;
        while (dist[j]>0) {
            j = dist[j];
            count++;
        }
        if (count>longestPath)
            longestPath = count;
    }

    fout << longestPath << endl;

    return 0;
}
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

Stop GOTO