Ενας πολυ ενδιαφερων τροπος

Εμαθα σημερα για ενα data structure που φαινεται να ειναι ιδανικο για την απεικονιση κατευθυνομενων γραφων. Προκειται για την “συμμετρικη λιστα γειτνιασης” (symmetric incidence list) η οποια φαινεται να ειναι ιδιαιτερα αποδοτικη ειδικα οταν κανεις ενδιαφερεται να κανει διασχιση του γραφου προς οποιαδηποτε κατευθυνση.

Tο μονο προβλημα της συμφωνα με τον Jürgen Ebert ειναι πως δεν ειναι και τοσο αποδοτικη οταν μας ενδιαφερουν υπαρξιακα ερωτηματα του τυπου “υπαρχει η ακμη ταδε?”. Περισσοτερα δεν εχω κουραγιο να γραψω τωρα, και σιγουρα θελω να κατσω να το μελετησω λιγο παραπανω, αλλα η καλυτερη πηγη που βρηκα σχετικα στο δικτυο ειναι ενα πειπερ του Ebert απο το 1987 με τιτλο A Versatile Data Structure For Edge-Oriented Graph Algorithms.

Μη φοβηθειτε την Algol μονο 🙂

(ο διακοσμητικος κατευθυνομενος γραφος στην κορυφη ειναι απο τα commons)

Ενας πολυ ενδιαφερων τροπος

Knuth

πηγη wikicommons, αδεια CC-by-sa-2.5

Την Πεμπτη που μας περασε ο Donald Knuth, ενας απο τους διασημοτερους και σημαντικοτερους computer scientists εβερ, εγινε 70 χρονων. Να τα κατοστησει και μετα να φτασει τα εκατον εντεκα (που λεγανε και οι μικρασιατισσες γιαγιαδες).

Ο Knuth εχει γραψει τουλαχιστον εικοσι σημαντικοτατα βιβλια, αναμεσα στα οποια και το βαρυ, τριτομο The Art of Computer Programming, δυο τομους απο το οποιο εχουμε την τιμη να κατεχουμε οικογενειακως. (Σημειωτεον οτι ο 70χρονος πλεον κυριος Knuth εχει ηδη στα σκαρια τεταρτο τομο, ενω προγραμματιζει να βγαλει και πεμπτο τομο το 2015). Eπισης, ο αξιοτιμος και αξιοσεβαστος κυριος Knuth συμβαινει να διαθετει μια τρομερη αισθηση του χιουμορ.

Αναμεσα στα διαφορα λοιπον, κυκλοφορει μια ωραια ανεκδοτολογικη ιστορια, για το τι εγινε οταν ο Knuth συναντησε τον Steve Jobs (της Apple) (–edit: οχι σορι, το αναποδο, η Apple ειναι του Jobs):

Steve had managed to get Don Knuth, the legendary Stanford professor of computer science, to give a lunchtime lecture to the Mac team. […] I was sitting in Steve’s office when Lynn Takahashi, Steve’s assistant, announced Knuth’s arrival. Steve bounced out of his chair, bounded over to the door and extended a welcoming hand.

“It’s a pleasure to meet you, Professor Knuth,” Steve said. “I’ve read all of your books.”

“You’re full of shit,” Knuth responded.

Knuth

Meet my wiki

πηγη wikicommons, αδεια GFDL

Οταν μεγαλωσω -δηλαδη, πρωτα ο Θεος, σε καναδυο μηνες- θελω να γινω μηχανικος λογισμικου (σοφτγουερ ετζινιρ που λεμε και στα Ελληνικα) και η αγαπημενη μου εξειδικευση ειναι η μοντελοποιηση λογισμικου (σοφτγουερ μοντελιγκ) και τα παρεπομενα. Ιδανικα δηλαδη, οταν μεγαλωσω και με ρωταει ο κοσμος τι δουλεια κανω, θα εχω να επιλεξω πώς θα απαντησω: Αν θελω να το παιξω νερντουλας θα λεω οτι “Ασχολουμαι με μοντελισμο”, με τις προφανεις αναφορες στα πλαστικα αεροπλανακια που φτιαχναμε στο γυμνασιο, ενω αν θελω να το παιξω ιστορια θα λεω οτι “Ασχολουμαι με το μοντελινγκ” και αστους να ψαχνουνε να βρουνε τις σαμπανιες και τα bunnies.

Τελοσπαντων, οπως και με ολα τα πραγματα πλεον σε αυτον τον κοσμο, το πεδιο δοξης λαμπρο του σοφτγουερ μοντελιγκ συνοδευται απο εναν τεραστιο ογκο πληροφοριας απο το δυκτιο. Και οσο προχωραει η διαδικασια εκκολαψης μου, γινεται ολο και πιο εμφανες οτι υπαρχει η μεγαλη αναγκη να μπορω να κουμανταρω αυτην την πληροφορια. Ουσιαστικα αυτο που με ενδιαφερει ειναι να εχω ενα “annotated directory” δηλαδη εναν καταλογο συνδεσμων με σχολια δικα μου, ωστε να μπορω να οργανωσω, να φιλτραρω και να καταλογογραφησω ολη αυτην την πληροφορια. Ιδανικα, αυτο θα μπορουσε καποια στιγμη να φανει χρησιμο και σε αλλους ανθρωπους.

Για τετοιες δουλειες δεν υπαρχει καλυτερο πραγμα απο το να μπορει κανεις να εχει το δικο του wiki. Και αναμεσα στoυς πολλους και διαφορους που προσφερουν τετοιες υπηρεσιες (γιατι το web2.0 δεν ειναι μονο τα blogs, το youtube και το flickr…), διαλεξα ολως τυχαιως το Wikidot το οποιο προσφερει δωρεαν wiki hosting χωρις διαφημισεις και ειναι και κομψο. Επισης, το Wikidot χρησιμοποιει το λογισμικο …wikidot, το οποιο υποτιθεται οτι θα ειχε απελευθερωθει σαν ελευθερο λογισμικο το καλοκαιρι (ή το φθινοπωρο συμφωνα με ενα αλλο FAQ), αλλα εχει καθυστερησει (ή εγκαταλειφθει σαν ιδεα, δεν ξερω).

Τελοσπαντων, με αρκετα λιγη προσπαθεια, σηκωσα το Software Modeling Wiki, ενα “annotated directory” για οτιδηποτε μου χτυπησει στο ματι σαν χρησιμο, ενδιαφερον, δυνητικα χρησιμο ή δυνητικα ενδιαφερον σχετικα με το θεμα. Το χρησιμοτερο προς το παρον κομματι του wiki, μαλλον θα ελεγε κανεις οτι ειναι ο μικρος σχολιασμενος καταλογος για τα σχετικα εργαλεια, με εμφαση σε εκεινα που ειναι ελευθερο λογισμικο.

So, come, meet my wiki! 🙂

Meet my wiki

Ελληνικα στο TeX/LaTeX με το XeTeX

Mε τεσσερεις γραμμες κωδικα, o Μιχαλης Παπακυριακου διελυσε με ενα ποστ του ολους τους φοβους μου οτι για να αρχισω να γραφω στα Ελληνικα την διπλωματικη μου στο TeX/LaTex θα επρεπε να κινησω γη και ουρανο (και να φορτωθω σε ανθρωπους που εχουν καλυτερα πραγματα να κανουν). Με ελαχιστο ψαξιμο παραπανω, μπορω να συμπληρωσω τα κομματια που λειπουν απο το ποστ του Μιχαλη και να γραψω το υπερσυντομο howto που ακολουθει.

Καταρχην, να ξεκαθαρισω οτι μιλαω για linux box που τρεχει Debian Sid. Η εγκατασταση του TeX/LaTeX ειναι απο τα πακετα της διανομης TeX Live τα οποια ειναι διαθεσιμα απο τα repositories του Debian. Με λιγα λογια, ολοκληρη η εγκατασταση του TeX/LaTeX εγινε χρησιμοποιωντας το apt (“μεσα απο το synaptic” που λεμε). Εκτος απροοπτου, αν καποιος τρεχει Ubuntu λογικα θα μπορει να κανει ακριβως την ιδια δουλεια με τον τροπο που περιγραφω εδω. Το κρισιμο πακετο, ειναι το texlive-xetex το οποιο παρεχει το XeTeX. Στο Ubuntu βρισκεται στο universe, με το ιδιο ονομα.

Αν το XeTeX ειναι εγκατεστημενο, για να χρησιμοποιησουμε Ελληνικα σε καποιο εγγραφο tex, προσθετουμε στην αρχη τις παρακατω γραμμες:

\usepackage{fontspec}
\setromanfont{FreeSerif}
\setsansfont{FreeSans}
\setmonofont{FreeMono}

Εδω εχω χρησιμοποιησει τις γραμματοσειρες freefont (που ειναι διαθεσιμες με GPL), αλλα μπορει κανεις να χρησιμοποιησει οποιαδηποτε TrueType γραμματοσειρα (γραμματοσειρες που η καταληξη τους ειναι .ttf). Συμφωνα με το FAQ του XeTeX, το συστημα δουλευει και με OpenType γραμματοσειρες, αλλα στο ομολογουμενως ελαχιστο χρονο που ασχοληθηκα με το θεμα δεν τα καταφερα να τις κανω να δουλεψουν καλα.

Υπαρχει ενα σημειο ομως που αξιζει να προσεχτει. Για να αναγνωρισει το XeTeX σωστα τις γραμματοσειρες που του λεμε, πρεπει να γραψουμε “σωστα” το ονομα τους (πχ “FreeSans” και οχι “Freesans” ή “Free Sans”). Ενας ευκολος τροπος για να βρουμε τα σωστα ονοματα ειναι με την εντολη fc-list. Αν για παραδειγμα θελουμε να χρησιμοποιησουμε DejaVu , ενα

fc-list | grep Deja

αρκει για να μαθουμε οτι τα σωστα ονοματα ειναι “DejaVu Serif”, “DejaVu Sans” και “DejaVu Sans Mono”.

Ενα δευτερο σημειο που πρεπει να προσεχτει ειναι οτι πρεπει τα Ελληνικα που θα γραψουμε να ειναι UTF-8 και οχι για παραδειγμα ISO8859-7. Ενας καλος τροπος να το εξασφαλισουμε αυτο (εκτος απο το να χρησιμοποιουμε το αντιστοιχο locale στο συστημα μας) ειναι να δουλευουμε με καποιον editor που να χειριζεται καλα τα encodings (το Kate ερχεται αυθορμητα στο μυαλο).

Η μεταγλωττιση του αρχειου tex γινεται με την εντολη xelatex. Να σημειωθει οτι το xelatex παραγει κατευθειαν pdf (οχι dvi, οχι ps).

Αυτα τα λιγα (και υποψιαζομαι οτι τα παρουσιασα καπως πιο πολυπλοκα απο οσο ειναι στην πραγματικοτητα). Happy TeXing!

Εξωτερικα λινκς:

Ελληνικα στο TeX/LaTeX με το XeTeX

Κατι …βασικο

Τοσο στην Πληροφορικη του ΕΚΠΑ, αλλα και στο Πολυτεχνειο δινονται σαν συγγραματα προγραμματισμου, βιβλια του καθηγητη του ΕΚΠΑ Ν.Μισυρλη. Δεν θελω να σχολιασω την ποιοτητα των βιβλιων γιατι παρολο που εχω ακουσει γενικα αρνητικα σχολια, δεν τα εχω χρησιμοποιησει σαν συγγραματα. Ομως εχει τυχει να πεσουν στα χερια μου μεσω της κοπελας μου και το πιο αξιοπεριεργο με αυτα τα βιβλια ειναι πως ο κωδικας C που περιεχουν ειναι σε greeklish!

Γραφω με αφορμη το οτι σε μια προσφατη δικτυακη κουβεντα καποιοι πρωτοετεις φοιτητες ελεγαν οτι τα greeklish τους βοηθησαν γιατι ευρισκαν τον κωδικα ευκολοτερο στο διαβασμα. Διαφωνω καθετως, οριζοντιως και διαγωνιως. Ο προγραμματισμος, οπως και τα μαθηματικα, δεν ειναι προζα. Μπορει κατα βαση να μην ειναι κατι περισσοτερο απο κειμενακι το οποιο το δινουμε στον compiler και μας το κανει γλωσσα μηχανης αλλα ενα εξισου σημαντικο χαρακτηριστικο του κωδικα ειναι οτι πρεπει να μπορει να διαβαζεται και απο αλλους ανθρωπους εκτος απο εκεινον που τον εγραψε. Και στην συγχρονη δικτυακη εποχη που χουμε, αυτοι οι αλλοι ανθρωποι μπορει να βρισκονται στην αλλη ακρη του πλανητη. Αρα, οπως στα μαθηματικα γραφουμε sin, cos, div, rot και grad, ετσι και στον προγραμματισμο πρεπει να τηρουμε τους κανονες και να χρησιμοποιουμε την lingua franca, δηλαδη τα αγγλικα.

Τα greeklish περα απο το οτι ειναι ασχημα, δυσαναγνωστα και εκνευριστικα ειναι εξ’ορισμου παρα πολυ κακος προγραμματισμος. Και το βασικο λαθος ειναι στη χρησιμοποιηση της ελληνικης γλωσσας μεσα σε προγραμμα. Θα ηταν το ιδιο λαθος ακομα και αν ο compiler της εκαστοτε γλωσσας υποστηριζε πραγματικα ελληνικα. Αλλωστε υπαρχει αυτη η δυνατοτητα, οχι με τον gcc βεβαια, αλλα με τον javac, τον compiler της Java, o οποιος υποστηριζει πληρως Unicode. Επιτρεπει δηλαδη ο compiler να γραψουμε ενα προγραμμα που θα οριζει για παραδειγμα μεταβλητες σαν “int μεταβλητή”.

Ειναι ευκολο να καταλαβει κανεις γιατι ειναι λαθος να γραφει κωδικα σε γλωσσα αλλη απο τα αγγλικα. Ο παρακατω trivial Java κωδικας, ειναι γραμμενος εξολοκληρου στα ρωσικα (με την ευγενικη χορηγια τυχαιων λεξεων απο την εφημεριδα Πραβντα). Κανει μια χαρα compile με τον javac 1.6. Εχοντας ενα αρχειο Лавров.java το περναμε στον javac και καταληγουμε με ενα Лавров.class. Αυτο τωρα μπορουμε να το εκτελεσουμε με “java Лавров” και να παρουμε μια ωραιοτατη εκτυπωση του αριθμου 42, που εκτος των αλλων ειναι και η απαντηση στο Ερωτημα για τη Ζωη, το Συμπαν και τα Παντα.

class Лавров {
      private int смогли, соблюдать;
      private boolean  тоМоскве;

      public Лавров(int наращивают) {
           this.смогли = наращивают ;
           this.соблюдать = 1;
           this.тоМоскве = false ;
     }

     public int дальности (int наращивают, Лавров уже){
          Лавров решил = уже;
          return наращивают++;
     }

     public static void main(String args[]){
          Лавров уже = new Лавров(5);
          System.out.println(уже.дальности(41, уже));
     }
}

ΟΚ, το παραδεχομαι οτι φαινεται πραγματικα πολυ κουλ, σαν να ειναι βγαλμενο απο κομικ του Μπιλαλ. Αλλα εκτος και κανεις ξερει Ρωσικα, κωδικας γραμμενος ετσι ειναι περα για περα αχρηστος…

Κατι …βασικο

Κανοντας αιτηση στο savannah.gnu.org

Διαβαζοντας για το μαθημα Διαδικτυο και Εφαρμογες, βρηκα την ευκαιρια να παιξω επιτελους λιγο παραπανω με το Qt Jambi. Εκατσα λοιπον και εφτιαξα ενα (σχεδον παιδαριωδες) telnet, που το ονομασα qTelnet. Προς το παρον, τον κωδικα μπορει κανεις να τον βρει στην προσωπικη μου σελιδα στο users.ntua.gr.

Περισσοτερο για να δω τη διαδικασια του να εχεις ενα software project σε ενα ονλαιν revision control συστημα (οπως πχ το Sourceforge), αποφασισα να αποκτησει το qTelnet ενα ωραιο δικτυακο σπιτακι. Και μιας και ειναι περα για περα free software αποφασισα να κανω αιτηση για hosting στο Savannah. Το Savannah συντηρειται απο το GNU Project και εκτος απο web hosting για free software projects, παρεχει πολλα εργαλεια, οπως για παραδειγμα version control και αλλα πολλα.

Το κυριοτερο χαρακτηριστικο του Savannah, που το διαφοροποιει απο το Sourceforge, ειναι οι “περιοριστικες” απαιτησεις που θετει οσον αφορα το τι λογισμικο μπορει να φιλοξενηθει στις απεραντες πεδιαδες του. Στη Σαβανα δεν μπορουν να βολταρει οτι κι οτι, υπαρχουν απαιτησεις για να μπεις στο οικοσυστημα:

  • Πρεπει η αδεια του λογισμικου να ειναι συμβατη με την GNU GPL.
  • Πρεπει το λογισμικο να ειναι free software, και μαλιστα πρεπει να ειναι καταρχην γραμμενο για να τρεχει σε καποιο ελευθερο λειτουργικο συστημα. Αν θελουμε να τρεχει και σε καποιο μη ελευθερο λειτουργικο, δεν υπαρχει προβλημα, αρκει το βαρος να βρισκεται στο ελευθερο λειτουργικο.
  • Πρεπει το λογισμικο να μην εξαρταται απο μη ελευθερες βιβλιοθηκες. Αυτο ειναι υποπεριπτωση της προηγουμενης απαιτησης, αν καταλαβουμε οτι το GNU project εννοει ελευθερο λειτουργικο συστημα εκεινο το οποιο ειναι εξολοκληρου ελευθερο.
  • Πρεπει να χρησιμοποιουνται μονο ανοιχτα formats. Formats οπως πχ flash τα μασανε τα λιονταρια.
πηγη: gnu.org, αδεια: GNU GPL και GNU FDL

Η αιτηση για να βαλει κανεις το project του στη Σαβανα ειναι μια διαδικασια εξι βηματων.

  1. Καταρχην πρεπει να αποκτησει κανεις ενα account. Απλη υποθεση, με ενα απλο email notification.
  2. Στη συνεχεια μπορουμε να ξεκινησουμε το application. Αφου διαβασουμε τα εισαγωγικα και καταλαβουμε που παμε να μπλεξουμε, κανουμε login και καλουμαστε να περιγραψουμε σε 20 το πολυ γραμμες μια συνοψη του τι κανει το λογισμικο μας, δινοντας ταυτοχρονα ενα λινκ στον κωδικα (που αν δεν εχουμε προσβαση σε καποιο δικο μας πχ ftp στο ιντερνετ, μπορουμε να χρησιμποιησουμε δωρεαν file hosting, οπως πχ το rapidshare).
  3. Επισης δηλωνουμε ακριβως τις εξαρτησεις βιβλιοθηκων του λογισμικου μας, και τις αντιστοιχες αδειες των βιβλιοθηκων. Νομιζω οτι ειναι καλη ιδεα να προσθεσουμε εδω και κανενα λινκ στον κωδικα των βιβλιοθηκων, ειδικα αν προκειται για καποια λιγοτερο γνωστη βιβλιοθηκη.
  4. Δηλωνουμε ενα ονομα για το project μας. Οπως ειχε πει και ο κυριος Αλεξης Ζαβρας στην ημεριδα της Κοινοτητας Ελευθερου Λογισμικου ΕΜΠ τον Ιουνιο, η ονομασια του project μας ειναι αρκετα σημαντικη υποθεση, αφου ενα προγραμμα που λεγεται “tsgswptrtu” (συντομογραφια για το “The Super Great SoftWare Project That Rules The Universe”) μαλλον παει απατο (και ακλαφτο).
  5. Διαλεγουμε με ποια απο τις GPL-compatible αδειες θα διανεμεται το προγραμμα μας.
  6. Δηλωνουμε τι σχεση εχει το project μας με το GNU Project (για παραδειγμα αν ειναι επισημο προγραμμα του GNU Project, που συνηθως δεν ειναι), ελεγχουμε αν τα στοιχεια που δωσαμε σε ολα τα προηγουμενα βηματα μας καλυπτουν και υποβαλλουμε την αιτηση.

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

Και σε αυτο ακριβως το σημειο βρισκεται αυτη τη στιγμη (02:14, 17/8/07) και η αιτηση για το qTelnet μου 🙂 Οταν (Stallman θελοντος) μου απαντησουν θα ενημερωσω το μπλογκοχωριο για τα περαιτερω.

Κανοντας αιτηση στο savannah.gnu.org

Πες ρε καμια ιδεα…

Παει και αυτη η εξεταστικη. Τι ωραια τι καλα και ολα τα σχετικα. Πωπω αυτη η καταραμενη ζεστη με εχει κανει λιγο γκρινιαρη. Τελοσπαντων, παει και αυτη η εξεταστικη, αλλη μια στους γερασμενους και καλα ωμους μου, καιρος να ηρεμησουμε. Οχι οτι θα κατσω να αραξω τωρα, εχω ενα σωρο δουλειες να κανω, ειδικα αν σοβαρολογω οτι θελω να παρω το πτυχιο μου το Φλεβαρη (αχ Παναγιτσα μου, αχ και συ αη Γιαννη μου).

Δουλειες με φουντες λοιπον: διπλωματικη, εργασιες και διαβασμα. Αλλα οπως και να το κανουμε, το διμηνο μεχρι τη μαχη των Θερμοπυλων το Σεπτεμβρη (οπου εγω ο ενας ηρωικος Μιχαλης θα κατατροπωσω τις στρατιες των βαρβαρικων μαθηματων ελπιζοντας να μην εχω την τυχη του μπαρμπαλεωνιδα) ειναι χαλαρωτικο. Και μιας που ειμαι κολημενος μπροστα στην οθονη λεω να ασχοληθω με πραγματακια που μου αρεσουν.

Plagal’s Summer of Code, λοιπον. Να το todo:

  • Να μαθω να χρησιμοποιω version control, κατα προτιμηση SVN.
  • Να μαθω να δουλευω σε ικανοποιητικα επιπεδα το TeX/LaTeX
  • Να παιξω με το Qt Jambi, γραφοντας ενα προγραμμα
  • Nα γραψω ενα προγραμμα σε python, μπας και μαθω τιποτα
  • Να παιξω με το καινουριο Ocaml παιχνιδι μου, το OcaIDE, γραφοντας ενα προγραμμα στην καμηλα, να την θυμηθω κιολας

Χα, να δουμε ποσα απο αυτα θα εχω κανει το Σεπτεμβρη! Τελοσπαντων, εχω ενα προβλημα: δεν εχω ιδεες για προγραμματα…

Oταν καποια στιγμη αποφασισα να μαθω να δουλευω το Swing, εκατσα και εφτιαξα το MySQL-Browser ενα προγραμμα για να κανω browse MySQL βασεις. Την ιδεα δεν ηταν δυσκολο να την βρω: ηθελα κατι τετοιο και ταυτοχρονα ξερω αρκετα καλα πώς να δουλευω το JDBC.

Αλλα τωρα? Τωρα τι? Εχω κολλησει διαολε και δεν μου’ρχεται καμια ιδεα… Το μονο που εχω σκεφτει ειναι ενα προγραμμα Οcaml που να δουλευει με συμβολικες αλγεβρικες παραστασεις, πχ να υπολογιζει οριζουσες που θα περιεχουν μεταβλητες και να επιστρεφει αλγεβρικες, συμβολικες παραστασεις. Αλλα μεχρι εκει.

Και το πακετο ειναι οτι θελω να ξεκινησω με το Qt Jambi και δε μου ερχεται καμια ιδεα για ενα γραφικο προγραμματακι, οχι πολυ μεγαλο, αλλα οχι και hello world. Για πειτε ρε καμια ιδεα…

Πες ρε καμια ιδεα…