REAL

Kombinatorikus optimalizálás alkalmazásai a villamosságtanban = Combinatorial optimization and its applications in electrical engineering

Recski, András and Fogaras, Dániel and Frank, András and Friedl, Katalin and Laborczi, Péter and Mann, Zoltán Ádám and Marx, Dániel and Nagy, Gyula and Orbán, András and Szeszlér, Dávid and Szkaliczki, Tibor and Tapolcai, János and Wettl, Ferenc (2007) Kombinatorikus optimalizálás alkalmazásai a villamosságtanban = Combinatorial optimization and its applications in electrical engineering. Project Report. OTKA.

[img]
Preview
PDF
42559_ZJ1.pdf

Download (35kB)

Abstract

A kombinatorikus optimalizálás eszközeit (gráf- és matroidelméleti algoritmusok, bonyolultságelméleti vizsgálatok) alkalmaztuk villamosságtani és informatikai problémák megoldására, így konkrétan -- a nagybonyolultságú integrált áramkörök 2- és 3-dimenziós huzalozási kérdéseire (csatorna- vagy 'switchbox'-huzalozás, minimális összhosszúságú/területű/térfogatú huzalozás); -- hardware és software komponenseket egyaránt tartalmazó rendszerek szintézisére; -- távközlési hálózatok megbízhatóságának, szolgáltatás-minőségének növelésére; -- közlekedési hálózatok informatikai szolgáltatásaira (pl. haladó járművek adatai alapján a hálózat topológiájának vizsgálata, optimális útvonal javaslása); -- az adaptív elosztott multimédia szerver fejlesztésére; -- web oldalakon hatékonyabb kereső programmok készítésére. Eközben tiszta matematikai és számítástudományi eredményekhez is jutottunk, így konkrétan -- a gráfelméletben (összefüggőséget növelő kiegészítések, Hamilton-körök, gráf-izomorfia); -- a matroidelméletben (gyenge és erős leképezések); -- a kvantumszámításokban (periódikus függvények, rejtett részcsoportok); -- a paraméteres bonyolultságelméletben (gráfok és hipergráfok színezése és listaszínezése); -- rúdszerkezetek és ''tensegrity'' szerkezetek merevségének elméletében. | Methods of combinatorial optimization (algorithms for graphs and matroids, complexity considerations) were applied for various problems in electrical engineering and informatics, in particular -- for the detailed routing of 2- and 3-dimensional VLSI circuits (channel and switchbox routing, minimum length/area/volume routing); -- for hardware/software codesign; -- for improving the quality of service of telecommunication networks; -- for integrated traffic information services (e.g. map generation and route guidance from floating car data); -- for the developments of adaptive distributed multimedia servers; -- for designing more effective search algorithms in the web graph. During these studies we also obtained results in pure mathematics and in theoretical computer science as well, in particular -- in the theory of graphs (connectivity augmentations, Hamiltonian circuits, graph isomorphism); -- in the theory of matroids (strong and weak maps); -- in quantum computing (periodic functions, hidden subgroup properties); -- in parametrized complexity theory (colouring or list-colouring of graphs and hypergraphs); -- in the theory of rigidity of bar-and-joint and tensegrity frameworks.

Item Type: Monograph (Project Report)
Uncontrolled Keywords: Automatizálás és Számítástechnika
Subjects: Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
Depositing User: Mr. Andras Holl
Date Deposited: 08 May 2009 11:00
Last Modified: 30 Nov 2010 21:57
URI: http://real.mtak.hu/id/eprint/669

Actions (login required)

Edit Item Edit Item