1 |
Υλοποίηση διαδικτυακού προσομοιωτή για αλγορίθμους επίλυσης προβλημάτων SATΧαρατσάρης, Δημήτριος 08 January 2013 (has links)
Η παρούσα διπλωµατική εργασία ασχολείται με το θέμα των Αλγορίθμων Επίλυσης Προβληµάτων SAT. Η εργασία αυτή εκπονήθηκε στα πλαίσια του Εργαστηρίου Ενσύρµατης Επικοινωνίας του Τµήματος Ηλεκτρολόγων Μηχανικών και Τεχνολογίας Υπολογιστών της Πολυτεχνικής Σχολής του Πανεπιστηµίου Πατρών. Σκοπός της είναι η δημιουργία ενός Προσομοιωτή των αλγορίθμων αυτών, ο οποίος να μπορεί να προσπελαστεί από οποιονδήποτε μέσω του διαδικτύου. Αρχικά έγινε µία εισαγωγή στο αντικείμενο της Τεχνητής Νοημοσύνης και πιο συγκεκριµένα στην Προτασιακή Λογική, ενώ δόθηκε και το απαραίτητο υπόβαθρο για να κατανοηθεί το πρόβληµμα και οι τεχνικές λύσης του. Τέλος, επιλέχθηκε να γίνει η υλοποίηση του Προσωμοιωτή σε Java. / This diploma dissertation deals with SAT solvers, algorithms for the Boolean satisfiability problem. It was produced in the Wire Communications Laboratory of the Electrical and Computer Engineering Department of the University of Patras. Its aim is to create a simulator for these algorithms, accessible to anyone via the Internet. An introduction to the field of Artificial Intelligence and more specifically to Propositional Calculus was given as well as the necessary groundwork to understand the problem and its solution approaches. The simulation implementation was developed in Java
|
2 |
The Generalized Splitting method for Combinatorial Counting and Static Rare-Event Probability EstimationZdravko Botev Unknown Date (has links)
This thesis is divided into two parts. In the first part we describe a new Monte Carlo algorithm for the consistent and unbiased estimation of multidimensional integrals and the efficient sampling from multidimensional densities. The algorithm is inspired by the classical splitting method and can be applied to general static simulation models. We provide examples from rare-event probability estimation, counting, optimization, and sampling, demonstrating that the proposed method can outperform existing Markov chain sampling methods in terms of convergence speed and accuracy. In the second part we present a new adaptive kernel density estimator based on linear diffusion processes. The proposed estimator builds on existing ideas for adaptive smoothing by incorporating information from a pilot density estimate. In addition, we propose a new plug-in bandwidth selection method that is free from the arbitrary normal reference rules used by existing methods. We present simulation examples in which the proposed approach outperforms existing methods in terms of accuracy and reliability.
|
3 |
Neuro-inspired computing enhanced by scalable algorithms and physics of emerging nanoscale resistive devicesParami Wijesinghe (6838184) 16 August 2019 (has links)
<p>Deep ‘Analog
Artificial Neural Networks’ (AANNs) perform complex classification problems
with high accuracy. However, they rely on humongous amount of power to perform
the calculations, veiling the accuracy benefits. The biological brain on the
other hand is significantly more powerful than such networks and consumes
orders of magnitude less power, indicating some conceptual mismatch. Given that
the biological neurons are locally connected, communicate using energy
efficient trains of spikes, and the behavior is non-deterministic, incorporating
these effects in Artificial Neural Networks (ANNs) may drive us few steps
towards a more realistic neural networks. </p>
<p> </p>
<p>Emerging
devices can offer a plethora of benefits including power efficiency, faster
operation, low area in a vast array of applications. For example, memristors
and Magnetic Tunnel Junctions (MTJs) are suitable for high density,
non-volatile Random Access Memories when compared with CMOS implementations. In
this work, we analyze the possibility of harnessing the characteristics of such
emerging devices, to achieve neuro-inspired solutions to intricate problems.</p>
<p> </p>
<p>We propose
how the inherent stochasticity of nano-scale resistive devices can be utilized
to realize the functionality of spiking neurons and synapses that can be
incorporated in deep stochastic Spiking Neural Networks (SNN) for image
classification problems. While ANNs mainly dwell in the aforementioned
classification problem solving domain, they can be adapted for a variety of
other applications. One such neuro-inspired solution is the Cellular Neural
Network (CNN) based Boolean satisfiability solver. Boolean satisfiability
(k-SAT) is an NP-complete (k≥3) problem that constitute one of the hardest
classes of constraint satisfaction problems. We provide a proof of concept
hardware based analog k-SAT solver that is built using MTJs. The inherent
physics of MTJs, enhanced by device level modifications, is harnessed here to
emulate the intricate dynamics of an analog, CNN based, satisfiability (SAT)
solver. </p>
<p> </p>
<p>Furthermore,
in the effort of reaching human level performance in terms of accuracy,
increasing the complexity and size of ANNs is crucial. Efficient algorithms for
evaluating neural network performance is of significant importance to improve
the scalability of networks, in addition to designing hardware accelerators. We
propose a scalable approach for evaluating Liquid State Machines: a
bio-inspired computing model where the inputs are sparsely connected to a
randomly interlinked reservoir (or liquid). It has been shown that biological
neurons are more likely to be connected to other neurons in the close
proximity, and tend to be disconnected as the neurons are spatially far apart.
Inspired by this, we propose a group of locally connected neuron reservoirs, or
an ensemble of liquids approach, for LSMs. We analyze how the segmentation of a
single large liquid to create an ensemble of multiple smaller liquids affects
the latency and accuracy of an LSM. In our analysis, we quantify the ability of
the proposed ensemble approach to provide an improved representation of the
input using the Separation Property (SP) and Approximation Property (AP). Our
results illustrate that the ensemble approach enhances class discrimination
(quantified as the ratio between the SP and AP), leading to improved accuracy
in speech and image recognition tasks, when compared to a single large liquid.
Furthermore, we obtain performance benefits in terms of improved inference time
and reduced memory requirements, due to lower number of connections and the
freedom to parallelize the liquid evaluation process.</p>
|
Page generated in 0.1032 seconds