Kostenoptimierung Flashcards
Was ist das Problem mit den Primimplikanten aus den Minimierungsverfahren
Sie sind in der Regel nicht frei von Redundanz
Wie wird die minimale Überdeckung der Primimplikanten gefunden?
Aufbau von Tabelle. Danach Wechselseitige Anwendung von verschiedenen Methoden. Wenn die Tabelle leer ist sind die ausgewählten Primimplikanten die minimale Lösung
Welche vier Methoden gibt es ber der Kostenoptimierung?
- wesentlicher Primimplikant
- Reihendominanz
- Spaltendominanz
- Branching
wesentlicher Primimplikant - Definition
- ein wesentlicher Primimplikant überdeckt als einziger einen Minterm einer Funktion
- wenn P_i als einziger Primimplikant m_i überdeckt, muss P_i ein Bestandteil der minimalen Überdeckung sein.
- Alle Spalten (Minterme), die von P_i überdeckt werden, können dann eliminiert werden.
Während des Optimierungsproblem können Primimplikanten entstehen, die keine Minterme mehr überdecken. Was passiert mit diesen?
Ihre Zeile wird Eliminiert
Reihendominanz - Definition
- Eine Reihe P_i dominiert die Reihe P_j, wenn P_i alle 1-Punkte / MInterme von P_j abdeckt
- P_i muss hierbei geringere oder gleihe Kosten aufweisen (Kosten (P_i) <= Kosten(P_j)).
- Die dominierte Reihe P_j kann entfernt werden
Spaltendominanz - Definition
- Eine Spalte m_i dominiert eine Spalte m_j, wenn alle Primimplikanten zur Überdeckung von m_i auch m_j überdecken
- Die Spalte m_j kann eliminiert wrden, denn jede Überdeckungsmenge der reduzierten Tabelle überdeckt auch m_i.
Wann wird Branching angewendet?
Wenn keine andere Methode angewendet werden kann ist die Tabelle zyklische -> es muss branching angewendet werden
Branching - Definition
- Man wählt einen möglichst wenig überdeckten Minterm aus und alle dazugehörigen Primimplikanten kommen in die Menge R
- Es wird ein Primimplikant P_i aus R gewählt und die von ihm überdeckten Spalten eliminiert
- P_i ist nun Teil der Lösung
