14 | 

9 4

 

 

1.  Εισαγωγή 

 

Η  συνεχής  ανάγκη  για  παραγωγή  νέων  ψηφιακών  κυκλωμάτων  μας  έχει  οδηγήσει 

στην  αυτοματοποίηση  αυτής  της  διαδικασίας.  Μία  αυτοματοποιημένη  διαδικασία  μας 

προσφέρει  συνέπεια  στην  ποιότητα  και  ταχύτητα.  Συνέπεια  στην  ποιότητα    σημαίνει,  ότι 

ανάλογα  με  τις  προδιαγραφές  που  έχουμε  ορίσει,  το  αποτέλεσμα  θα  είναι  πάντα  στο  ίδιο 

επίπεδο  ποιοτικώς.  Αυτά  τα  δύο  χαρακτηριστικά  είναι  αρκετά,  ώστε  να  μας  ωθήσουν  να 

μελετήσουμε και να βρούμε αποδοτικότερους τρόπους αυτοματοποίησης μιας διαδικασίας. 

 

1.1 

Το πρόβλημα 

 

Ως δεδομένα του προβλήματος που έχουμε να αντιμετωπίσουμε θεωρούμε ότι έχουμε 

τα  κυκλωματικά  στοιχεία  ενός  ψηφιακού  κυκλώματος  και  τις  διασυνδέσεις  μεταξύ  τους. 

Παράδειγμα:  Το  κύκλωμα  έχει  δύο  πύλες  AND  με  δύο  εισόδους  και  μία  πύλη  OR  με  δύο 

εισόδους. Η έξοδος της πρώτης AND πύλης συνδέεται με την δεύτερη είσοδο της πύλης OR 

κ.ο.κ.  Ο  σκοπός μας  είναι,  έχοντας  αυτά  τα δεδομένα, να  τοποθετήσουμε  τα  στοιχεία  στον 

καμβά  και να τα συνδέσουμε με τέτοιον τρόπο, ώστε να βελτιστοποιήσουμε κάποια μεγέθη, 

όπως  το  συνολικό  εμβαδόν  που  καταλαμβάνει  το  κύκλωμα  να  είναι  το  ελάχιστο,  το μήκος 

των  καλωδίων  να  είναι  το  ελάχιστο  και  παράλληλα  το  κύκλωμα  να  διατηρεί  την 

αναγνωσιμότητα  του,  την  λειτουργικότητά  του  και  την  αισθητική  του.  Το  πρόβλημα  που 

αντιμετωπίσαμε  είναι  γενικό  και  θεωρητικά  θα  πρέπει  η  επίλυση  του  να  ισχύει  για  κάθε 

κύκλωμα  ανεξαρτήτου  μεγέθους  και  πολυπλοκότητας.  Πρακτικά  όμως  υπάρχουν 

περιορισμοί,  όπως  η  πεπερασμένη  υπολογιστική  ισχύς  και  οι  περιορισμοί  που  εισέρχονται 

από  την  χρήση  του  λογισμικού  Logisim.  Το  Logisim  επιβάλλει  κάποια  όρια  ως  προς  τα 

μεγέθη των στοιχείων και τον τρόπο με τον οποίο μπορούν να γίνονται διασυνδέσεις μεταξύ 

τους. Όλα αυτούς τους περιορισμούς θα πρέπει να λάβουμε υπόψη και κατά την σχεδίαση του 

αλγόριθμου  αλλά  και  ως  προς  την  χρονική  πολυπλοκότητα  που  θα  προσθέσουν  στο 

πρόγραμμα. Πιο συγκεκριμένα για να καταλάβουμε την απαίτηση για υπολογιστική ισχύ, εάν 

δοκιμάζαμε να επιλύσουμε το πρόβλημα δοκιμάζοντας όλους τους πιθανούς συνδυασμούς το 

πρόγραμμα  δεν  θα  τερμάτιζε  ποτέ.  Γι  αυτόν  τον  λόγο  έπρεπε  να  βρούμε  μια  λύση 

προσεγγιστικά.