Projekti pri Računalništvu III

Študijsko leto 2003/04

Okvirni potek izdelave projekta

1. Izbor projekta: Naj bi se zgodil do začetka semestrskih počitnic, torej do 15.1.2004. Izberite si projekt in pošljite sporočilo na naslov drago.bokal@fmf.uni-lj.si. Prednost ima tisti, ki prvi izbere.

2. Spoznavanje projekta: Ugotovite, kaj je dejanska vsebina vašega projekta, in si jo predstavite. Za lažje oblikovanje misli uporabite obrazec v LaTeXu. Ogledate si ga lahko tudi v postscriptu. Opis projekta morate izdelati vsi in poslati na naslov drago.bokal@fmf.uni-lj.si. Predstavitev naj obsega okrog pet do sedem strani (prazen formilar je tri strani).

3. Predstavitev projekta: Projekt boste v kratkem, dvajsetminutnem predavanju predstavili kolegom v okviru vaj. Prve predstavitve bodo tik pred semestrskimi počitnicami, datume za nadaljne predstavitve pa bomo določili na podlagi prispelih opisov projektov.

4. Zagovor: Preden pristopite k ustnemu izpitu, boste projekt zagovarjali. Predstavili boste program, ki ga boste pripravili, njegovo delovanje na nekaj testnih primerih in odgovorili na kakšno vprašanje o njem. V primeru neuspešnega zagovora boste program ali njegovo poznavanje izboljšali in projekt ponovno zagovarjali.

	Projekt	Literatura	Opombe	Program	Študent	Datum
Matematično programiranje
2.	Polinomski algoritmi za linearno programiranje (Karmarkarjev algoritem)	J1, J2, Sch1, AKRV	1. semester		-Vito Vitrih	13.1.
3.	Kvadratično programiranje in optimizacija portfelja	Sh	1. semester		!Pigac Vesna	13.1.
4.	Semidefinitno programiranje	VB	1. semester		!Toni Tina	13.1.
5.	Elipsoidna metoda	KV, 4.pogl.			Tretjak Vesna	13.1.

Algebrajski algoritmi
1.	Faktorizacija polinomov nad Z (LLL algoritem za razcep primitivnih polinomov s celoštevilskimi koeficienti in Berlenkampov algoritem)	[Knu, pogl. 4.6.2] in [KLL, Len, LLL]			!Željko Jure	17.2.
2.	Računanje vsot v zaključeni obliki (Gosperjev algoritem)	GKP, poglavji 5.5 in 5.7			!Zupančič Barbara	17.2.
3.	Razcep celih števil (razcep z eliptičnimi krivuljami)	HTCS, pogl. 12/4.2B, str. 677-681 in pogl. 12/4.4B str. 697-699			!Reščič Miha	17.2.
4.	Kriptografija. RSA in DES	HTCS, pogl. 13/1 do 13/6.2, str. 719-730		Simulacija obeh protokolov	!Žibrat Simon	24.2.
5.	Protokoli brez posredovanja informacije (zero-knowledge protocols)	HTCS, pogl. 13/9.2, str. 744--746 in Lan		Simulacija protokola	!Tešar Miha	24.2.
6.	Polinomski algoritem za preverjanje praštevilskosti	M. Agrawal, N. Kazal, N. Saxena, PRIMES is in P, preprint			!Dakskobler Blaž	23.3.

Algoritmi na grafih
1.	Povezanost grafov (linearni algoritem za 3-povezanost)	HTCS, pogl. 10/2.1, str. 552-555 in HT
2.	Izomorfizem grafov (polinomski algoritem za izomorfizem grafov z omejenimi mnogokratnostmi lastnih vrednosti)	HTCS, pogl. 10/2.6, str. 574-579 in BGM		Program le za enostavne lastne vrednosti
3.	Maksimalno prirejanje v dvodelnih grafih	IM, MTF	**		Jelenčič Sašo	17.2.
4.	Maksimalno prirejanje (v splošnih grafih)	HTCS, pogl. 10/3.2, str. 583-588	konec 1.sem.	Postopek Gabowa	!Barbo Erika	13.1.
5.	Maksimalni pretok	KV, razdelek 8.5	Goldberg-Tarjanov algoritem		Groznik Janez	13.1.

Ravninski grafi
1.	Linearni algoritmi za vlaganje grafa v ravnino	NC			!Zalokar Nikolaj	24.2.
2.	Risanje grafov	KW, pogl. 4.1-4.2, 6		Baricentrični postopek, Tamassia-Tollis, Biedl-Kant, tehnika parov	!Umek Lan	24.2.
3.	Konveksno risanje ravninskih grafov	KW, pogl. 2.6 in 2.7		De Fraysseix- Pach-Pollack, Schnyder, Kant	Berlič Primož	23.3.
4.	Separatorji v ravninskih grafih (Linearni algoritem za iskanje majhnega separatorja (izrek 9.5), uporaba pri iskanju min pokritja točk v ravninskih grafih (O(n log n) aproksimacijski algoritem, razd. 9.6))	NC, pogl. 9			-
5.	Iskanje Hamiltonovega cikla v 4-povezanem ravninskem grafu	NC
6.	Primarno-dualni algoritem za risanje grafov
7.	Predstavitev ravninskega grafa kot grafa dotikanj podobnih trikotnikov v ravnini	FMR	-		Boštjan Ramšak	4.5.
8.	Večkratni pretoki v ravninskem grafu	Sch2, poglavje 9			Plankl Matevž	30.3.
9.	T-spoji in problem poštarja	CCPS, poglavje 5.4			Papler Tanja	13.4.

Aproksimacijski algoritmi
1.	Aproksimacijski algoritem za problem maksimalnega prereza grafa	GW			!Vuksanovič Miloš	6.4.
2.	Aproksimacijski algoritem za Minimalno Steinerjevo k-drevo	Epp	-		!
3.	Problem Steinerjevega drevesa	KV, poglavje 20.1			Maja Ulčnik	6.4.
3.	Aproksimacijski algoritem za vsoto podmnožice	Prz	-
4.	Aproksimacijska shema za večkratne pretoke	KV, razdelki 19.1. - 19.2.			!

Vzporedni algoritmi
1.	Vzporedni algoritmi in NC, osnovni vzporedni algoritmi na grafih (povezanost, tranzitivno zaprtje, najkrajše poti)	[Koz, poglavja 28 in 30-34] in [Lei, str. 338-341 in 125-132]		Simulacija vzporednosti	!Andrej Lindič	11.5.
2.	Najcenejše vpeto drevo; prirejanja v grafih	[Lei, str. 136-138 in 324-338] in [Lei, str. 341-353]		Simulacija vzporednosti
3.	Hitra Fourierova transformacija	Lei, str. 439-446 in 711-717	-	Simulacija vzporednosti
4.	Urejanje	Lei, str. 621-657		Simulacija vzporednosti	Nataša Tabakovič	18.5.
5.	Konstrukcija ekspanderjev in koncentratorjev	Mor

Kombinatorična geometrija
1.	Delitev točk v ravnini v uravnotežene skupine	BKS

Ostalo
1.	Generatorji naključnih števil. Primerjava različnih generatorjev in statistični testi	Knu	-	Vsi testi za razne generatorje	Primož Kocbek	25.5.
2.	Dinamično programiranje	GL, poglavje 5	-		Stanek Maruša	20.4.
3.	Popolna prirejanja v heksagonalnih sistemih	HZ	-
4.	Razcep grafov na faktorje glede na kartezični produkt grafov		-
5.	Voronojevi diagrami. (a) Deli in vladaj (b) Sprotno (on-line) dodajanje točke (in brisanje)	PS	-
6.	Hevristični algoritmi za problem trgovskega potnika	CCPS, razdelek 7.2	Lin-Kernighan

Uporabni projekti
1.	Hiter (de)kompresijski algoritem	opis projekta (MS Word datoteka)	Hermes Softlab	Potrebno bo izdelati hitro 16-bitno kompresijo v C	Koncilja Andrej	25.5.
2.	Optimalni kontrolni obhodi po omrežju	opis projekta (PS datoteka)	IMFM		Magajna Adrijan; Urlep Matjaž	13.4.
3.	Rekonstrukcija omrežja iz netočnih kartografskih podatkov	opis projekta (PS datoteka)	IMFM
4.	Algoritmi na usmerjenih grafih	opis projekta (PDF datoteka)	Društvo Abak		Luka Goljevšček	25.5.
5.	Iskanje ciklov v grafu iz podatkovne zbirke	opis projekta (DOC datoteka)	Hermes Softlab
5.	Obrazec za opis projekta - uporabite za podroben opis projekta, ki ga boste izdelali.	obrazec (PS datoteka) obrazec (LaTeX datoteka)

Bibliografija

[HTCS] Handbook of theoretical computer science, Volume A: Algorithns and complexity, Editor J. van Leeuwen, Elsevier, 1990.
[AKRV] I. Adler, N. Karmarkar, M.G.C. Resende, G. Veiga, An implementation of Karmarkar's algorithm for linear programming, preprint.
[BGM] L. Babai, D. Yu. Grigorjev, D. M. Mount, Isomorphism of graphs with bounded eigenvalue multiplicity, pp. 310-324.
[BKS] S. Bespamjatnikh, D. Kirkpatrick, J. Snoeyink, Generalized ham sandwich cuts to equitable subdivisions, Discr. Comput. Geom. 24 (2000) 605-622.
[Ch] V. Chvatal, Linear programming, W. H. Freeman and Co., New York, 1983.
[CCPS] W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver, Combinatorial Optimization, Wiley, 1998.
[Epp] D. Eppstein, Faster geometric k-point MST approximation, Tech. Report 95-13, Univ. of California.
[FMR] H. de Fraysseix, P. Ossona de Mendez, P. Rosenstiehl, On triangle contact graphs, Combin. Probab. Comput.
[GW] M. Goemans, D. Williamson, .878-approximation algorithms for MAX CUT and MAX 2SAT, 26th STOC, 1994, pp. 422-431.
[GKP] R. L. Graham, D. E. Knuth, O. Patashnik, Concrete mathematics, Addison-Wesley, 1989.
[GL] M. Grotschel, L. Lovasz, Combinatorial optimization: A survey, DIMACS Technical report 93--29, 1993.
[HZ] P. Hansen, M. Zheng, A linear algorithm for perfect matchings in hexagonal systems, Discrete Math. 122 (1993) 179-196.
[HT] J. E. Hopcroft, R. E. Tarjan, Dividing a graph into triconnected components, SIAM J. Comput. 2 (1973) 135-158.
[IM] O. H. Ibarra, S. Moran, Deterministic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplication, Inform. Process. Lett. 13 (1981), 12-15.
[J1] J. Jamšek, Karmarkarjev algoritem za reševanje linearnih programov, magistrsko delo, Univerza v Ljubljani, 1991.
[J2] J. Jamšek, OMF 38, št. 6.
[KLL] R. Kannan, A. K. Lenstra, L. Lovasz, Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers, Math. of Computation 50 (1988) 235-250.
[KW] M. Kaufmann, D. Wagner, Drawing Graphs. Methods and Models, Springer, 2001.
[KV] B. Korte, J. Vygen, Combinatorial Optimization - Theory and Algorithms, Springer, 2000.
[Koz] D. C. Kozen, The design and analysis of algorithms, Springer-Verlag, 1992.
[Knu] D. E. Knuth, The art of computer programming, Vol. 2. Seminumerical algorithms, Addison-Wesley, Reading, Mass., 1973.
[Lan] S. Landau, Zero knowledge and the department of defense, Notices AMS 35 (1988) 5-12.
[Lei] F. T. Leighton, Introduction to parallel algorithms and architectures: Arrays, trees, hypercubes, M. Kaufmann Publ., 1992.
[Len] A. K. Lenstra, A recent algorithm for the factorization of polynomials, CWI-Newslett. 8 (1983) 15-20.
[LLL] A. K. Lenstra, H. W. Lenstra, Jr., L. Lovasz, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982) 515-534.
[Mor] M. Morgenstern, Explicit construction of natural bounded concentrators, preprint.
[MTF] K. Makino, T. Takabatake, S. Fujishige A simple matching algorithm for regular bipartite graphs, Inform. Process. Lett., 84 (2002), 189-193.
[NC] T. Nishizeki, N. Chiba, Planar graphs: Theory and algorithms, North-Holland, 1988.
[PS] F. P. Preparata, M. I. Shamos, Computational geometry, Springer-Verlag, 1985.
[Prz] B. Przydatek, A fast approximation algorithm for the subset-sum problem.
[Sch1] A. Schrijver, Theory of linear and integer programming, Wiley-Interscience, 1986.
[Sch2] A. Schrijver, A course in combinatorial optimization, zapiski predavanj.
[Sh] J. F. Shapiro, Mathematical programming: Structures and algorithms, Wiley, 1979.
[VB] L. Vandenberghe, S. Boyd, Semidefinite programming, SIAM Rev. 38 (1996) 49-95.

Projekti pri Računalništvu III

Okvirni potek izdelave projekta

Matematično programiranje

Algebrajski algoritmi

Algoritmi na grafih

Ravninski grafi

Aproksimacijski algoritmi

Vzporedni algoritmi

Kombinatorična geometrija

Ostalo

Uporabni projekti

Bibliografija