Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/8631
Title: Πιθανοτική ικανοποιησιμότητα : πολυπλοκότητα και υπολογιστικές προσεγγίσεις
Authors: Αραβαντινού, Άννα
Issue Date: 2015-07-07
Keywords: Πιθανοτική ικανοποιησιμότητα
Ικανοποιησιμότητα μέγιστη
Υπολογιστική πολυπλοκότητα
Συχνά στοιχειοσύνολα
Γραμμικός προγραμματισμός
Προσεγγιστικοί αλγόριθμοι
Keywords (translated): PSAT
Maximum satisfiability problem (MAX-SAT)
Column generation
Abstract: Στην εργασία αυτή ασχοληθήκαμε με το πρόβλημα της Πιθανοτικής Ικανοποιησιμότητας. Παρουσιάσαμε ανάλυση της πολυπλοκότητας του προβλήματος και το επιλύσαμε με την βοήθεια του λογισμικού πακέτου CPLEX. Περιγράψαμε προσεγγιστικούς αλγόριθμους για το πρόβλημα της Μέγιστης Ικανοποιησιμότητας που χρησιμοποιείται στην διαδικασία της Column Generation. Τέλος, πριγράψαμε το αντίστροφο πρόβλημα των συχνών στοιχειοσυνόλων και την σχέση του με το πρόβλημα της Μέγιστης Ικανοποιησιμότητας.
Abstract (translated): This thesis is about the problem of probabilistic satisfiability. We describe its computational complexity, we solve the problem using CPLEX, we discribe some approximations on Maximum Satisfiability. Finally, we describe the connection between the problem of Probabilistic Satisfiability and the inverse frequent itemset mining.
Appears in Collections:Τμήμα Μαθηματικών (ΜΔΕ)

Files in This Item:
File Description SizeFormat 
Αραβαντινού Άννα.pdf1.56 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.