15+ years ago as an undergraduate I was interested in graphs. Manos then suggested that I should read Christos‘ PhD thesis. Then came work. Then came this paper. Then came even more work. I forgot about graphs. My interest was renewed after spending family vacations with a theorist’s family. Aris presented me with a challenge, while this fall, this man taught me the foundations from a non-CS perspective.

In the words of Steve Yegge:

“Graphs are, like, really really important. More than you think. Even if you already think they’re important, it’s probably more than you think.”

Notice the “really really important” part. For it is not “really² important”; rather it is more of “reallyⁿ important” (for n >> 2). Go down to your library and read Bela Bollobas’ “Modern Graph Theory” (I found its predecessor “Graph Theory – An Introductory Course”) or even Reinhard Diestel’s “Graph Theory” which is also available online^*. For those who read Greek, here is a quick introduction (definitions and theorems but no proofs): Εφαρμογές Θεωρίας Γραφημάτων.

In an era when (almost) everyone seems to be talking about the social graph, or applications that make use of it, you need the mathematical background. If you have an idea that builds on social networks it is almost inevitable that its development and implementation will make use of theorems or more general results of graph theory. So, since you will have to deal with it, why not be prepared? Or even if you have devised a graph data model that can kill the RDBMS⁺, why not use the theory to support the argument?

[*] – Originally I wanted to write a simple “post-it” on Diestel’s book. However, in the process I decided to make it a typical blog post of three to four paragraphs. You may even want to dig more by reading Bernie Hogan’s “Using Information Networks to Study Social Behavior: An Appraisal “, the stuff over at the NetWiki and the articles in the graph theory section of MarkCC’s Good Math, Bad Math.

[+] – Hank, this is not a polemic on your view on RDBMS; we have already agreed on what parts of this view we disagree.

Μετά από μια συζήτηση την Τρίτη για τους υπολογιστές και το δυαδικό σύστημα θυμήθηκα μια απόδειξη που μας είχαν κάνει στο ΕΜΠ για το ότι το δυαδικό δεν είναι το καλύτερο σύστημα αναπαράστασης της πληροφορίας και πως η επιλογή του ήταν περισσότερο τεχνοοικονομική. Ξέθαψα λοιπόν το βιβλίο της Αρχιτεκτονικής Υπολογιστών και να:

Έστω πως έχουμε ένα σύστημα που αναπαριστά την πληροφορία σε βάση R και με μέγεθος λέξης k. Τότε όλες οι δυνατές αναπαραστάσεις είναι Α = R^k, όπου για κάθε ψηφίο της λέξης υπάρχουν R σύμβολα.

Τότε λοιπόν χρειαζόμαστε Ε = kR σύμβολα για να αναπαραστήσουμε τα R^k string μήκους k. Για παράδειγμα για k = 8 και R = 2 χρειαζόμαστε Ε = 16 σύμβολα^*, ενώ για k = 2 και R = 16 χρειαζόμαστε Ε = 32. (Παρατηρείστε πως στο παράδειγμα ισχύει πως 2⁸ = 16² = 256).

Αναζητούμε λοιπόν τις συνθήκες εκείνες ώστε το kR να είναι minimum, ενώ ταυτόχρονα το R^k να είναι σταθερό:

Από το A = R^k έχουμε πως k = ln(A) / ln (R) το οποίο με βάση τη σχέση E = kR μας δίνει:

E = Rln(A) / ln(R)

Παραγωγίζοντας ως προς R βρίσκουμε πως το E ελαχιστοποιείται για R = e. Για να φανεί και οπτικά, για A = 2⁸, 2¹⁶ και 2³²:

[*] – Σκέψου τα σαν μαύρα και άσπρα πούλια του τάβλι. Χρειάζεσαι 8 μαύρα και 8 άσπρα για να μπορείς να παράγεις όλους τους συνδιασμούς.

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

Να μια συνέντευξη που πρέπει να κάνει κάποιος που θέλει να προάγει το ΕΛ/ΛΑΚ.

Παρακολουθούσα μια διάλεξη για MIS όταν μου πέρασε από το μυαλό μου (όχι μια σφαίρα ρε!) η παρακάτω σκέψη:

“Workflow είναι η (ελλειπής) απεικόνιση της γραφειοκρατίας ενός οργανισμού σε ένα υπολογιστικό σύστημα”

Δεν ήμουνα σε φόρμα μάλλον…

Γράφει ο Raghavendra Rao Loka:

“In my experience, a project eventually completes, but rarely as planned. Occasionally, a brilliant or dedicated software engineer comes along, accidentally recruited or dissatisfied with the project’s general progress, and completes it. In most cases, management takes credit for the fortuitous accident and reaps the rewards.”

Έλα ρε! Γίνονται τέτοια πράγματα;

[via Software Development: What Is the Problem?]

Chstath writes a “compressed” explanantion of non-completeness. Thumbs up!

Αυτή είναι μια ομιλία που έδωσε κάποτε ο Richard Hamming. Καιρό τώρα ήθελα να την αναφέρω. Μόλις έφτασε στο INBOX μου ξανά, αυτή τη φορά από το Interesting-People. Αγαπημένο μου σημείο:

[…] I started asking, “What are the important problems of your field?” And after a week or so, “What important problems are you working on?” And after some more time I came in one day and said, “If what you are doing is not important, and if you don’t think it is going to lead to something important, why are you at Bell Labs working on it?”

Για προφανείς λόγους, το σκέφτομαι κάθε μέρα. Την ομιλία μπορείτε να τη διαβάσετε online και να την κατεβάσετε σε PDF.

[via Interesting-People]