@comment{ generated by }
@Unpublished{ALGO-STUDENT-2009-001,
abstract = {Ce document vous présente mon pro jet de semestre dont
le titre original est Turing machine emulator. Le but de
ce projet a été d'implémenter un système capable d'émuler
certaines abstractions des machines de Turing. La
première étape était de mettre en place un "langage de
programmation simple" pour décrire le comportement d'une
machine de Turing et ensuite implémenter un interpreteur
pour ce langage. Les étapes suivantes ont permis d’écrire
des modules simples qui implémentent des opérations
basiques sur les machines de Turing ainsi qu'un
"compilateur" pour traduire un language de plus
haut-niveau permettant d'écrire des programmes basiques
en des modules fonctionnant sur des machines de Turing
ainsi que de mettre en place une interface d'utilisateur
permettant l'interaction avec les différents systèmes.},
affiliation = {EPFL},
author = {Favre, Ludovic},
details = {http://infoscience.epfl.ch/record/138789},
documenturl = {https://infoscience.epfl.ch/record/138789/files/ProjectSources.tar.gz},
oai-id = {oai:infoscience.epfl.ch:138789},
oai-set = {IC},
status = {PUBLISHED},
title = {Turing {M}achine {E}mulator},
unit = {ALGO},
url = { },
year = 2009
}
@Unpublished{ALGO-STUDENT-2007-002,
abstract = {Implementation of a variety of sorting algorithms, and
look at their behavior and running times on different
inputs.},
affiliation = {EPFL},
author = {Abibou, Ramatou},
details = {http://infoscience.epfl.ch/record/101014},
documenturl = {https://infoscience.epfl.ch/record/101014/files/ramatouFinal.pdf},
oai-id = {oai:infoscience.epfl.ch:101014},
oai-set = {IC},
status = {PUBLISHED},
title = {Sorting {A}lgorithms},
unit = {ALGO},
url = { },
year = 2005
}
@Unpublished{ALGO-STUDENT-2007-008,
abstract = {Since the discovery of the utility of the numbers, the
human being tried to differentiate them. We decide
between them according to whether they are even or odd.
Or, according to the fact that they are prime or
composite. A natural number n >1 is called a prime number
if it has no positive divisors other than 1 and n.
Therefore, other numbers that are not prime have other
divisors. That is why we call them composite numbers
because we can write them : n = p*q with {p,q} ≠ {1,n}.
The problem has always been to decide whether a number is
prime or not. To answer this problem, many algorithms
have been created like the Trial Division. It uses the
property which says that the biggest divisor of n is
smaller or equal to the square root of n. But for numbers
that exceed 30 digits, it will take more than 10^13 years
to know the answer. So, the interest would be to create
an algorithm using mathematical bases which would answer
to this question as fast as possible. This is what we
will see in this project. The study of prime numbers
became really important to code texts. Cryptography is
one of the most important application of prime numbers
theory. At the beginning, it was only used to code texts
during the wars and more recently it was used for other
applications, like the security of an account. Fist of
all, I will focus on randomized algorithms for primality
testing. Then, I will focus on a deterministic algorithm
that I have implemented.},
affiliation = {EPFL},
author = {TAHIRI JOUTI, Kamal},
details = {http://infoscience.epfl.ch/record/101087},
documenturl = {https://infoscience.epfl.ch/record/101087/files/Kamal_TAHIRI.pdf},
oai-id = {oai:infoscience.epfl.ch:101087},
oai-set = {IC},
status = {PUBLISHED},
title = {Primality {T}esting},
unit = {ALGO},
url = { },
year = 2006
}
@Unpublished{ALGO-STUDENT-2007-003,
abstract = {The project consists in the study, implementation and
comparison of binary matrix multiplication algorithms in
C++. We consider Strassen’s algorithm (which is known to
perform well over the real numbers) the Four Russians
algorithm (which is designed for binary matrices) and
compare their performances to that of the naive
multiplication algorithm on binary matrices.},
affiliation = {EPFL},
author = {Pongas, Spyridon},
details = {http://infoscience.epfl.ch/record/101015},
documenturl = {https://infoscience.epfl.ch/record/101015/files/pongasFinal.doc},
oai-id = {oai:infoscience.epfl.ch:101015},
oai-set = {IC},
status = {PUBLISHED},
title = {Matrix {I}mplementations},
unit = {ALGO},
url = { },
year = 2005
}
@Unpublished{ALGO-STUDENT-2007-005,
abstract = {Error correcting codes are combinatorial objects that
allow reliable recovery of information in presence of
errors by cleverly augmenting the original information
with a certain amount of redundancy. The availability of
efficient means of error detection is considered as a
fundamental criterion for error correcting codes. Locally
testable codes are families of error correcting codes
that are highly robust against transmission errors and in
addition provide super-efficient (sublinear time)
probabilistic algorithms for error detection. In
particular, the error detection algorithm probes the
received sequence only at a small (or even constant)
number of locations. There seems to be a trade-off
between the amount of redundancy and the number of probes
for the error detection procedure in locally testable
codes. Even though currently best constructions allow
reduction of redundancy to a nearly linear amount, it is
not clear whether this can be further reduced to linear
while preserving a constant number of probes. We study
the formal notion of locally testable codes and survey
several major results in this area. We also investigate
closely related concepts, and in particular, polynomial
low-degree tests and probabilistically checkable proofs.},
affiliation = {EPFL},
author = {Cheraghchi, Mahdi},
details = {http://infoscience.epfl.ch/record/101080},
documenturl = {https://infoscience.epfl.ch/record/101080/files/cheraghchi_MS_thesis.ps},
keywords = {Error Correcting Codes; Locally Testable Codes;
Probabilistically Checkable Proofs (PCP); Low-Degree
Tests; Hardness of Approximation; algoweb_misc},
oai-id = {oai:infoscience.epfl.ch:101080},
oai-set = {IC},
status = {PUBLISHED},
title = {Locally {T}estable {C}odes},
unit = {ALGO},
url = { , },
year = 2005
}
@Unpublished{ALGO-STUDENT-2007-001,
abstract = {The goal of this project is to present the main
list-decoding algorithms for Reed-Solomon codes,
implement them and study more specifically some of their
properties and possible improvements.},
affiliation = {EPFL},
author = {Marc, Julie},
details = {http://infoscience.epfl.ch/record/101013},
documenturl = {https://infoscience.epfl.ch/record/101013/files/julieFinal.pdf},
keywords = {list-decoding; Reed-Solomon},
oai-id = {oai:infoscience.epfl.ch:101013},
oai-set = {IC},
status = {PUBLISHED},
title = {List-{D}ecoding {A}lgorithms},
unit = {ALGO},
url = { },
year = 2006
}
@Unpublished{ALGO-STUDENT-2007-006,
abstract = {It is well-known that random error-correcting codes
achieve the Gilbert-Varshamov bound with high
probability. In [2], the authors describe a construction
which can be used to yield a polynomially large family of
codes of which a large fraction achieve the
Gilbert-Varshamov bound. In this project, we investigate
ways to obtain codes known to achieve this bound, given
such a family of codes. Since computing the minimum
distance of a code is NP-hard, we work with a class of
Goppa codes described in [1] whose minimum distance is
known. We know that there exist Goppa codes which achieve
the Gilbert-Varshamov bound, but we do not know if there
are codes in this class which achieve it. We investigate
various approaches to determining the rate of a code and
try to apply them to this class of codes in order to
determine if they achieve the Gilbert-Varshamov bound.
These approaches include investigating upper bounds on
the covering radius of a code and refining an existing
lower bound on the code dimension. We also implemented
the described class of Goppa codes using the PARI/GP
computer algebra system [5], in order to obtain numerical
values which would allow us to detect patterns and
formulate conjectures regarding those codes.},
affiliation = {EPFL},
author = {Maatouk, Ghid},
details = {http://infoscience.epfl.ch/record/101083},
documenturl = {https://infoscience.epfl.ch/record/101083/files/maatouk_report.pdf},
oai-id = {oai:infoscience.epfl.ch:101083},
oai-set = {IC},
status = {PUBLISHED},
title = {Good {E}nsembles of {G}oppa {C}odes},
unit = {ALGO},
year = 2007
}
@Unpublished{ALGO-STUDENT-2007-004,
abstract = {After introducing the concept of finite fields and their
properties, we look algebraic constructions of error
correcting codes.},
affiliation = {EPFL},
author = {Burrin, Nelly},
details = {http://infoscience.epfl.ch/record/101017},
documenturl = {https://infoscience.epfl.ch/record/101017/files/nellyFinal.doc},
oai-id = {oai:infoscience.epfl.ch:101017},
oai-set = {IC},
status = {PUBLISHED},
title = {Finite fields {A}nd {E}rror-{C}orrecting {C}odes},
unit = {ALGO},
url = { },
year = 2006
}
@Unpublished{ALGO-STUDENT-2007-007,
abstract = {Binomial heaps are data structures implemented as a
collection of binomial trees, (A binomial tree of order K
can be constructed from two trees of order (K-1)). They
can implement several methods: Min, Insert, Union,
ExtractMin, DecreaseKey and Delete. Fibonacci heaps are
similar to binomial heaps,howevere it figured that they
had a better performance in what regards the amortized
analysis, These methods have a cost of O(1) except for
ExtractMin and Delete (O(lg n)) Fibonacci heaps are used
to improve the cost of Dijikstra and Prim. We implemented
first the algorithms of Binomial and Fibonacci. We then
used ExtractMin of fibonacci so as to implement Prim and
Dijikstra. We have made a bonus algorithm , Kruskal who
is also a "Minimum Spanning Tree" algorithm. },
affiliation = {EPFL},
author = {Chekir, Ali and Slama, Mohamed Slim},
details = {http://infoscience.epfl.ch/record/101085},
documenturl = {https://infoscience.epfl.ch/record/101085/files/fibonacci_heaps_en.pdf},
oai-id = {oai:infoscience.epfl.ch:101085},
oai-set = {IC},
status = {PUBLISHED},
title = {Fibonacci {H}eaps},
unit = {ALGO},
url = { },
year = 2006
}