Algorithms_and_complexity

View on GitHub
HOME EXERCISE SOLUTION ZIP TWITTER Techical Report Release Έκδοση App Installation


Algorithms and complexity course

  1. Ανάγνωση αρχείων-Εύρεση Cv-Πίνακας Γειτνίασης

    2. *Δημιουργία λογαριασμού στο GitHub.

    *Δημιουργία repository στο Github για την εργασία του μαθήματος.

    * Ενεργοποίηση Github pages για το repository.

    * Εγκατάσταση git, clone του repository τοπικά.

    * Κώδικας για ανάγνωση δεδομένων γραφήματος εργασίας.

    * Δημιουργία του πίνακα γειτονικότητας AdjMatrix (δισδιάστατος πίνακας, |V|x|V| με AdjMatrix[i][j] = 1 αν υπάρχει ακμή ανάμεσα στις κορυφές i και j, αλλιώς AdjMatrix[i][j] = 0).

    * Υπολογισμός του Conflict Density.

  2. Εύρεση στατιστικών στοιχείων

    • Αριθμός κορυφών.
    • Πυκνότητα. Για τον υπολογισμό της πυκνότητας θα πρέπει να κατασκευαστεί ο πίνακας συ‐ γκρούσεων. Ο πίνακας συγκρούσεων είναι ένας δισδιάστατος πίνακας c στον οποίο κάθε στοιχείο cij = 1 αν η εξέταση i βρίσκεται σε σύγκρουση με την εξέταση j ενώ ισχύει ότι cij = 0 σε άλλη περίπτωση. Η πυκνότητα συγκρούσεων υπολογίζεται διαιρώντας τον αριθμό των στοιχείων του πίνακα συγκρούσεων που έχουν την τιμή 1 με το συνολικό πλή‐ θος των στοιχείων του πίνακα.
    • Για τους βαθμούς (degrees) των κορυφών η ελάχιστη τιμή (min), η διάμεσος τιμή (median), η μέγιστη τιμή (max), η μέση τιμή (mean) καθώς και ο συντελεστής διακύμανσης (CV=coefficient of variation) που ορίζεται ως η τυπική απόκλιση προς τη μέση τιμή.


  3. Υλοποιήση Αλγορίθμων Χρωματισμού

    • FIRST FIT
    • DSATUR
    • RLF
    • BDSATUR

  4. Γειτονικές Κορυφές-Βάση δεδομένων

    • Υλοποιούνται

      • Εύρεση γειτονικών κορυφών για κάθε κορυφή.
      • Υλοποίηση In-Memory database με χρήση sqlite αποθήκευση στατιστικών στοιχείων από κάθε αρχείο.
      • Εμφάνιση όλων των αποθηκευμένων δεδομένων από την βάση δεδομένων.


  5. Εξτρα ΕΚΔΟΣΕΙΣ

    • Fixed Data Reading Problems
    • Extra Edition RLF Algorithm


  6. Αρχεία κώδικα που χρησιμοποιήθηκαν στην εφαρμογή