Institute Of Computer Science
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Institute Of Computer Science as PDF for free.
More details
- Words: 6,558
- Pages: 35
Institute of Computer Science
Academy of Sciences of the Czech Republic
Fuzzy Class Theory: A Primer v1.0 Libor Bˇehounek and Petr Cintula1 Technical report No. 939 December 2006 Abstract: Fuzzy Class Theory was proposed as a formal background of an axiomatic approach to fuzzy mathematics built inside a sufficiently strong formal fuzzy logic. The goal of this text is to provide a thorough introduction to this theory for non-specialists in formal fuzzy logic. First, we give an informal exposition of the apparatus of the theory and explain how its results can be interpreted from the point of view of traditional fuzzy mathematics. Secondly, we address notable features of this theory, starting with the importance of graded theories, continuing through natural embedding and then fuzzifying of classical mathematical theories, ending with basic methodological guidelines regarding the latter. Finally, we show how to prove the results in Fuzzy Class Theory, by employing not only proof methods for particular first-order logic but also new strong methods which heavily utilize the advantages of formal build-up of the Fuzzy Class Theory. This is version 1.0 of the Primer. A newer version may be downloadable from www.cs.cas.cz/hp. Keywords: Fuzzy Class Theory, graded properties, proof methods
1 Institute of Computer Science, Academy of Sciences of the Czech Republic, P. O. Box 5, 182 07 Prague 8, Czech Republic, {behounek,cintula}@cs.cas.cz. The work of Libor Bˇ ehounek was supported by the grant No. B100300502 of the Grant Agency of the Academy of Sciences of the Czech Republic. The work of Petr Cintula was partly supported by the grant No. B100300502 of the Grant Agency of the Academy of Sciences of the Czech Republic and partly by by the Institutional Research Plan AV0Z10300504.
Institute of Computer Science Academy of Sciences of the Czech Republic
Correlation Dimension-Based Classifier Marcel Ji ina and Marcel Ji ina, jr.
Technical Report No. V-945
January 2006
Abstract An innovative approach that utilizes the correlation dimension (CD) both for probability density estimate of data and consequently for classification is suggested. The idea of correlation dimension classifier directly follows the principle of classifier, which uses the distribution mapping exponent (DME). The basic difference between these two approaches is that DME is a local feature while CD is global feature. A new "hyperbolic" approximation of the correlation integral for the correlation dimension estimation is suggested. It is shown that CD-based classifier outperforms DME classifier and many other classifiers published on Machine Learning Repository pages.
Keywords: Multivariate data; Correlation dimension; Nearest neighbors; Distribution mapping exponent; Power approximation, Classification, ML Repository. Pod Vodárenskou v ží 2, 182 07 Prague 8, phone: +420 266 051 111, fax: +420 286 585 789 e-mail: [email protected]
2
Institute of Computer Science
Academy of Sciences of the Czech Republic
European Summer School in Information Retrieval ESSIR 2005 Zdeˇnka Linkov´a1 Technical report No. 949 February 2006 Abstract: Information Retrieval (IR) as a process of searching relevant information is a significant discipline of a data processing field. European Summer School in Information Retrieval ESSIR provides students, academic and industrial researchers and developers a grounding in the core objects of IR (models, architectures, algorithms), as well as covering some current topics, e.g. information retrieval from the Web. We have participated its 5th year that was held at Dublin City University in Dublin, Ireland. Keywords: Summer school, Information Retrieval.
1 Institute
of Computer Science, Academy of Sciences of the Czech Republic,182 07 Prague 8, Czech Republic
! " #%$'& (*),+.-0/,1324$56)878$'):9;/,1=8)A@CBD)E$:>GF) HJILK*MN56$
O
PQRS! TVU%=R W=XTYZR[ \T]J
bfdZceg h ij J lk U;da=dYZrG.s
m n8o.ÎYZ hpq` a
jkZp
vlwyx{z[|}yE¤C Ò z |*
^_ :º a
u
} |x{}}
} =
d` ¢¡¤£¥¦§£©¨,ª§¬«®¯ °` ±L²£i³´´®¤µ¬£¶S· ¸º¹ »½ ¾*³´´¿ ~²Ä¸¨j£ j¨ Ï ©'¨j ¸Ò¦ ¢¦£ µÃyĹ ¦§¡ ¾¢º§¤±8 ¢¡ ¨T×±'S§¤º¸¨j£ Æ j¨Tײ¢¡ ~ ¨ ¨T׺ÍE¸ S¨dÓ §£Î£¥`¸¨j£Ô j¨`¹L£¥º ¹Ö6§ SE²£¶¢ ×ÄÍ8¦£¥§Í£ ¢±:¸ §Ó ¹¨j*¯¤« ?S¾ 磶¹¸`Ï
°£ ¢ ¹§¤±8 È º¨T §{µ¬ ¨ ¨T×ÄÍ"¸ ¨ µÎ²£¶¢ ×ÄÍ ¦£¥§Í£ ¢±:¸'§Ó'²§¤Æ ¹`¹ ¹¨j
!"! #$% '&() *,+#$ .-/10324&(567 "&(0 83& " 1#39: &;) <>=Ò?(?(@(?(?(AºCB 0 *, D/10 % "&(0E!F G H ! 0JILK ?NM{?(@(?(?(A(?O P * % 7 "&(0V&2W YXFZ: % + !" " P Q :E) !"! #R% S&( *:+N#J &;) T$?(AONA &2 = T "0 ") )#U&2 <
Institute of Computer Science
Academy of Sciences of the Czech Republic
Reasoning about Bang3 multi-agent systems in KR-Hyper Gerd Beuster, Roman Neruda, Bj¨orn Pelzer Technical report No. 955 January 2006 Abstract: Bang3 is a Multi-Agent-System platform focusing on soft computing. KR-Hyper is an automatic theorem proofer for First Order Logic. In this paper, we describe how KR-HYPER can be connected to Bang3 in order to allow reasoning about Multi-Agent-Systems. Keywords: MAS, Bang, KR-HYPER, Logic, Deduction, Description Logics, First Order Logic, Agents
Institute of Computer Science
Academy of Sciences of the Czech Republic
N´ avrh tot´ aln´ı n´ ahrady kolenn´ıho kloubu s rotaˇ cn´ı polyetyl´ enovou vloˇ zkou Jiˇr´ı Stehl´ık, Jiˇr´ı Nedoma Technical report No. 957 May 2006 Abstrakt: In the paper the analyses of effect of axial changes on the weight-bearing total knee replacenets (TKRs) in frontal and sagital planes are shortly discussed. On the basis of obtained numerical results two rotary types of TKRs are presented and discussed. Keywords: Total knee replacement (TKR), axial changes, rotary TKR.
Institute of Computer Science
Academy of Sciences of the Czech Republic
Biomechanical analysis of the effect of axial angle changes on the weight-bearing total knee replacements J. Stehl´ık1 , P. Vavˇr´ık2 , J. Danˇek3 , J. Nedoma4 , I. Hlav´aˇcek5 , F. Denk6 Technical report No. 958 May 2006 Abstrakt: The aim of this paper is to compare of the biomechanical influences of different grades of valgus deformity after the total knee replacement (TKR) based on the contact model problem with friction, the finite element method and the nonoverlapping domain decomposition method. Keywords: Biomechanics, knee, total replacement, valgus deformity
1 Orthopaedic Department, The Hospital Cesk´ ˇ ˇ e Budˇ ejovice, B. Nˇ emcov´ a Str. 585/54, 370 01 Cesk´ e Budˇ ejovice, Czech Republic, e-mail: [email protected] 2 1st Ortopaedical Department, 1st Medical Faculty of the Charles University Prague, V u ´ valu 84, 150 00 Prague 5 - Motol, Czech Republic, e-mail: [email protected] 3 Centre of Applied Mathematics, University of West Bohemia, Univerzitn´ ı 8, 306 14 Pilsen, Czech Republic and Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod vod´ arenskou vˇ eˇ z´ı 2, 182 07 Prague 8, Czech Republic e-mail: [email protected] 4 Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod vod´ arenskou vˇ eˇ z´ı 2, 182 07 Prague 8, Czech Republic, e-mail: [email protected] 5 Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod vod´ arenskou vˇ eˇ z´ı 2, 182 07 Prague 8, ˇ a 25, 115 67 Prague 1, Czech Republic and Mathematical Institute, Academy of Sciences of the Czech Republic, Zitn´ Czech Republic, e-mail: [email protected] 6 WALTER a.s., Jinonick´ a 329, 158 01 Prague 5 - Jinonice, Czech Republic, e-mail: [email protected]
Institute of Computer Science
Academy of Sciences of the Czech Republic
Analysis of axial angle changes on the weight-bearing total knee replacements J. Stehl´ık1 , P. Vavˇr´ık2 , J. Danˇek3 , J. Nedoma4 , I. Hlav´aˇcek5 , F. Denk6 Technical report No. 959 May 2006 Abstrakt: Background. The analysis of the effect of axial angle changes on the weight-bearing total knee replacements (TKR) was investigated and discussed. Methods. A two dimensional finite element models of the femorotibial joint in the frontal and the sagital planes were developed from CT images. For computation the nonoverlapping finite element technique develped in our institute was used. Results. The effect of axial angle changes on the weight-bearing total knee replacements is analysed in frontal and sagital planes. It is shown that optimal distribution of forces operated on the TKR in anteroposterior direction and well-balanced transition of forces in anteroposterior direction will correspond to the 7 deg. case. The results show a good agreement between theoretical and orthopadic observations. Keywords: Biomechanics, Knee, Total replacement, Axial changes
1 Orthopaedic Department, The Hospital Cesk´ ˇ ˇ e Budˇ ejovice, B. Nˇ emcov´ a Str. 585/54, 370 01 Cesk´ e Budˇ ejovice, Czech Republic, e-mail: [email protected] 2 1st Ortopaedical Department, 1st Medical Faculty of the Charles University Prague, V u ´ valu 84, 150 00 Prague 5 - Motol, Czech Republic, e-mail: [email protected] 3 Centre of Applied Mathematics, University of West Bohemia, Univerzitn´ ı 8, 306 14 Pilsen, Czech Republic and Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod vod´ arenskou vˇ eˇ z´ı 2, 182 07 Prague 8, Czech Republic e-mail: [email protected] 4 Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod vod´ arenskou vˇ eˇ z´ı 2, 182 07 Prague 8, Czech Republic, e-mail: [email protected] 5 Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod vod´ arenskou vˇ eˇ z´ı 2, 182 07 Prague 8, ˇ a 25, 115 67 Prague 1, Czech Republic and Mathematical Institute, Academy of Sciences of the Czech Republic, Zitn´ Czech Republic, e-mail: [email protected] 6 WALTER a.s., Jinonick´ a 329, 158 01 Prague 5 - Jinonice, Czech Republic, e-mail: [email protected]
Institute of Computer Science
Academy of Sciences of the Czech Republic
Boolean factor analysis by Hopfield-like autoassociative memory 1 A. A. Frolov2 and D. H´usek3 and I. P. Muraviev4 and P. A. Polyakov5 Technical report No. 961 February 2006 Abstract: The feature space transformation is a widely used method for data compression. Due to this transformation the original patterns are mapped into the space of features or factors of reduced dimensionality. In this paper we demonstrate that Hebbian learning in Hopfield-like neural network is a natural procedure for Boolean factor analysis. Due to this learning, neurons that tend to fire together (represent one common factor) are more correlated and thus create an attractor of the network dynamics. If the attraction basins around factors are large enough, the factors could be revealed by random search. This paper is dedicated to estimation of the size of attraction basins around factors. Two global spurious attractors are shown to prevent convergence of the network activity to the factors invalidating any procedure of their search. These global attractors can be completely deleted from network dynamics by introducing a single inhibitory neuron with bi-directional Hebbian synapses. Due to additional inhibition, the size of attraction basins around factors becomes the same as around the stored patterns in usual Hopfield network. The procedure of factors search is described in the accompanying paper. Keywords: Boolean factor analysis, Hopfield neural network, unsupervised learning
1 The work was partly supported by the Institutional Research Plan AV0Z10300504 ”Computer Science for the Information Society: Models, Algorithms, Appplications” and by grant Intelligent methods for increasing of reliability of electrical networks 1ET100300414 granted by GA AS CR 2 Institute of Higher Nervous Activity and Neurophysiology of the Russian Academy of Sciences, Butlerova 5a, 117 485 Moscow, Russia; e-mail: [email protected] 3 Institute of Computer Science Academy of Science of the Czech Republic, Pod Vod´ arenskou vˇ eˇ z´ı 2, 182 07 Prague 8, Czech Republic; tel. (+420)26605 3230, Fax: (+420) 28658 5789, e-mail: [email protected] 4 Institute of Higher Nervous Activity and Neurophysiology of the Russian Academy of Sciences, Butlerova 5a, 117 485 Moscow, Russia;e-mail: [email protected] 5 Institute of Optical Neural Technologies of the Russian Academy of Sciences, Vavilova 44, 119 333 Moscow, Russia; e-mail: [email protected]
Institute of Computer Science
Academy of Sciences of the Czech Republic
Boolean factor analysis by Hopfield-like autoassociative memory: factors search1 A. A. Frolov2 , D. Husek3 , P. Y. Polyakov4 , I. P. Muraviev5 Technical report No. 962 February 2006 Abstract: In our previous paper [6] we have shown that Hebbian learning in Hopfield-like neural network is a natural procedure for Boolean factor analysis. Hebbian learning forms a connection matrix of the network as a co-variation matrix of input signal space. Neurons that represent one common factor are more correlated and thus create attractor of the network dynamics. In this paper we describe a procedure of factors retrieval. According to this procedure, network dynamics evolve forward starting from a random initial state and stabilize in the attractor which corresponds to one of the factors (a true attractor) or one of the spurious attractors. Separation of true and spurious attractors is based on calculation of their Lyapunov function and activation threshold. We studied efficiency of the retrieval procedure by computer simulation. Keywords: Boolean factor analysis, Hopfield neural network, unsupervised learning, recall procedure, data mining.
1 This work was supported by grant from Grant Agency of Czech Republic, Prague No.201/05/0079 and by grant 1ET100300414 of the research program ”Information Society” granted by GA AS CR. 2 Institute of Higher Nervous Activity and Neurophysiology of the Russian Academy of Sciences; e-mail: [email protected] 3 Institute of Computer Science Academy of Science of the Czech Republice; E-mail: [email protected] 4 Institute of Optical Neural Technologies of the Russian Academy of Sciences; e-mail: [email protected] 5 Institute of Higher Nervous Activity and Neurophysiology of the Russian Academy of Sciences; E-mail: [email protected]
Institute of Computer Science
Academy of Sciences of the Czech Republic
Johnson score and characteristics of distributions 1 Zdenˇek Fabi´an Technical report No. 963 February 2006 Abstract: New measures of central tendency and dispersion of continuous probability distributions are introduced. They exist for common distributions and their estimates have necessary statistical properties. Their meaning is explained by means of instructive examples. Keywords: basic characteristics, variance, Johnson transform
1 The
work was supported by Grant Agency AS CR under grant IAA1075403.
Institute of Computer Science
Academy of Sciences of the Czech Republic
The minC Combination of Belief Functions: derivation and formulas.1 Milan Daniel2 Technical report No. 964 June 2006 Abstract: Principal ideas of the minC combination are recalled. A mathematical structure of generalized frames of discernment is analysed and formalized. A generalized schema for a computation of the minC combination is presented. Conflicting belief masses redistribution among non-conflicting focal elements is overviewed. Final general formulas for computation of the minC combination are presented. Some examples of computation of the minC combination follow. A brief comparison of the minC combination with other combination rules is presented. Related works and approaches and some open problems for a future research are referred in the end. Keywords: Belief function, Combination of belief functions, Dempster-Shafer theory, Conflict, Potential conflict, Contradiction, minC combination.
1 The support of the grant 1ET100300419 GA AV CR ˇ is kindly announced. The work was partly supported by the Institutional Research Plan AV0Z10300504 ”Computer Science for the Information Society: Models, Algorithms, Applications”. 2 [email protected]
Institute of Computer Science
Academy of Sciences of the Czech Republic
Prim´ arnˇ e du´ aln´ı metoda aktivn´ıch mnoˇ zin pro jednostrann´ y kontakt pruˇ zn´ ych tˇ eles s dan´ ym tˇren´ım I.Hlav´aˇcek Technical report No. 965 March 2006 Abstrakt: Uvaˇzujeme jednostrann´y kontakt dvou pruˇzn´ych rovinn´ych nebo prostorov´ych tˇeles. Sm´ıˇsen´a variaˇcn´ı formulace vede na probl´em sedlov´eho bodu, kter´y diskretizujeme metodou koneˇcn´ych prvk˚ u. K nalezen´ı sedlov´eho bodu aplikujeme novou metodu tzv. prim´arnˇe du´aln´ı strategie aktivn´ıch mnoˇzin (PDAS), kter´a se d´a ztotoˇznit se zobecnˇenou Newtonovou iteraˇcn´ı metodou. V 1. kapitole je analyzov´ano ˇreˇsen´ı koercivn´ıch i semi-koercivn´ıch u ´loh bez tˇren´ı. 2. resp. 3. kapitola je vˇenov´ana kontaktu s ”dan´ym” tˇren´ım podle Trescova modelu ve 2D-, resp. 3D-formulaci. K nalezen´ı pˇr´ısluˇsn´eho sedlov´eho bodu je navrˇzen iteraˇcn´ı algoritmus, kter´y kombinuje projekce z metody Uzawovy s metodou PDAS v kaˇzd´em iteraˇcn´ım kroku. Keywords: Jednostrann´y kontakt, dan´e tˇren´ı, metoda koneˇcn´ych prvk˚ u, sedlov´y bod, zobecnˇen´a Newtonova metoda
Institute of Computer Science
Academy of Sciences of the Czech Republic
HUGO: A Cognitive Architecture with an Incorporated World Model1 Jiˇr´ı Wiedermann Technical report No. 966 April 2006 Abstract: We present a design of cognitive system architecture with an internal world model. The internal world model is realized with the help of artificial mirror neurons. We consider generalized artificial mirror neurons acting both as a mechanism for assembling and learning multimodal sensorimotor information and as associative memory for invoking multimodal information given only some of its components. We show that within an artificial cognitive system a network of generalized mirror neurons can simultaneously serve as an internal world model recognized by the agent and as that of the agent’s position within this world. We also specify a self-organizing control mechanism, which is based on the basic operations over concepts that were essentially identified by the British 18th century philosopher David Hume. This control mechanism makes use of the internal world model constructed in agent’s interaction with real world and straightforwardly supports imitation learning. Building heavily on the properties of the generalized mirror net and on automatic abstract concept creation, we offer an algorithmic explanation of computational language acquisition, thinking and consciousness in our model. Rather than describing an implementation of the respective mechanisms, the aim of the paper is to establish a proof of the principle of algorithmic nature of higher cognitive functions. Keywords: cognitive systems; embodied cognition; internal world model; mirror neurons; thinking; consciousness
1 This work was done within the Institutional Research Plan AV0Z10300504 and was partially supported by grant No. 1ET100300419
Institute of Computer Science
Academy of Sciences of the Czech Republic
Chtěli byste být mozkem v baňce? Jiří Wiedermann1 Technical report No. 967 duben 2006 Abstrakt: Moderní teorie kognitivních systémů pohlíží na tyto systémy jako na autonomní vtělené výpočetní systémy, které se situují v okolí prostřednictvím svých senzomotorických jednotek. Přesto zejména v kruzích počítačových teoretiků je opakovaně slyšet názory, že na kognici lze pořád možné pohlížet i ”klasicky”, jako na problém specifického zpracování dat a že tudíž vtělení není nezbytné pro zachycení podstaty kognice. Ukážeme, že takto zjednodušený pohled opomíjí podstatnou vlastnost kognitivních systémů - a sice jejich aktivní vliv na výběr či dokonce vznik vstupních dat. Bez této zpětné vazby si systém nemůže vytvořit svůj vnitřní model světa poznaný prostřednictvím svých akcí. Pro vysvětlení povahy zmíněného problému použijeme výpočetní model kognitivních systémů zavedený autorem v předchozích pracích. Tento model umožní na principielní úrovni přemýšlet o fungování algoritmických mechanizmů imitace, komunikace, vzniku řeči, myšlení a vědomí a tím přispět i k jejich pochopení v živých systémech. Keywords: kognitivní systémy; vtělenost; situovanost; vnitřní model světa
1 Tato
práce vznikla v rámci výzkumného záměru AV0Z10300504 s částečnou podporou grantu 1ET100300419
Institute of Computer Science
Academy of Sciences of the Czech Republic
Integral combinations of Heavisides1 Paul C. Kainen2 , Vˇera K˚ urkov´a3 , Andrew Vogt4 Technical report No. 968 May 2006 Abstract: A sufficiently smooth function of d variables that decays fast enough at infinity can be represented pointwise by an integral combination of Heaviside plane waves (i.e., characteristic functions of closed half-spaces). The weight function in such a representation depends on the derivatives of the represented function. The representation is proved here by elementary techniques with separate arguments for even and odd d, and unifies and extends various results in the literature. Keywords: Feedforward neural network, perceptron, Heaviside function, plane wave, integral formula, Radon transform, Green’s function for iterated Laplacians, order of vanishing, function of controlled decay.
1 V. K. was partially supported by GA CR ˇ grant number 201/05/0557 and the Institutional Research Plan AV0Z10300504. Collaboration of the three authors was also supported by NAS COBASE grants and the Georgetown University International Affairs Office. 2 Department of Mathematics, Georgetown University, Washington, D.C. 20057-1233 3 Institute of Computer Science, Acad. of Sci. of the Czech Republic, P.O. Box 5, 182 07 Prague 8, Czech Republic 4 Department of Mathematics, Georgetown University, Washington, D.C. 20057-1233
Institute of Computer Science Academy of Sciences of the Czech Republic
Johnson system of parametric families1 Zdenˇek Fabi´an Technical report No. 969 July 2006 Abstract: We present a system of parametric unimodal continuous distributions, containing all possible types of score functions of prototypes. We call it a Johnson system since Johnson transformation is used for its construction. The system contains many used probability distributions, some of them in reparametrized forms, with unified meaning of parameters. Three non-Johnson systems are mentioned as well. 2000 Mahematics Subject Classification codes: 62A01, 62F01
Keywords: systems of distributions, transformation, core function
1 The
work was supported by the Grant Agency AS CR under grant IS 1ET400300513.
Institute of Computer Science
Academy of Sciences of the Czech Republic
A Model of an Amorphous Computer and its Communication Protocol1 Luk´aˇs Petr˚ u2 and Jiˇr´ı Wiedermann3 Technical report No. 970 August 2006 Abstract: We design a formal model of an amorphous computer suitable for theoretical investigation of its computational properties. The model consists of a finite set of nodes created by RAMs with restricted memory, which are dispersed uniformly in a given area. Within a limited radius the nodes can communicate with their neighbors via a single-channel radio. The assumptions on low-level communication abilities are among the weakest possible: the nodes work asynchronously, there is no broadcasting collision detection mechanism and no network addresses. For the underlying network we design a randomized communication protocol and analyze its efficiency. The subsequent experiments and combinatorial analysis of random networks show that the expectations under which our protocol was designed are met by the vast majority of the instances of our amorphous computer model. Keywords: amorphous computing; networks; communication protocols; random graphs; complexity;
1 This research was carried out within the institutional research plan AV0Z10300504 and partially supported by the ˇ grant No. 1ET100300419 and GD201/05/H014. GA CR 2 Faculty of Mathematics and Physics, Charles University, Malostransk´ e n´ amˇ est´ı 25, 118 00 Prague 1, Czech Republic, email:[email protected] 3 Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod Vod´ arenskou vˇ eˇ z´ı 2, 182 07 Prague 8, Czech Republic
Institute of Computer Science
Academy of Sciences of the Czech Republic
Johnson point and Johnson variance∗ Zdenˇek Fabi´an Technical report No. 971 July 2006 Abstract: New measures of central tendency and dispersion of continuous probability distributions were introduced in [1]. In this paper we show that they offer a simple and suitable description of heavy-tailed distributions, i.e., the distributions which may not have the mean and/or variance. MSC: 62A01, 62F01 Keywords: basic characteristics, Johnson transform, parametric estimates
∗ The author is indebted to I. Vajda for valuable critical remarks and suggestions. The work was supported by Grant Agency AS CR under grant number IAA1075403.
Institute of Computer Science
Academy of Sciences of the Czech Republic
A strong nonrandom pattern in Matlab default random number generator Petr Savicky1 Technical report No. 972 September 2006 Abstract: The default random number generator in Matlab versions between 5 and at least 7.3 (R2006b) has a strong dependence between the numbers zi+1 , zi+16 , zi+28 in the generated sequence. In particular, there is no index i such that the inequalities zi+1 < 1/4, 1/4 ≤ zi+16 < 1/2, and 1/2 ≤ zi+28 are satisfied simultaneously. This fact is proved as a consequence of the recurrence relation defining the generator. A random sequence satisfies the inequalities with probability 1/32. Another example demonstrating the dependence is a simple function f with values −1 and 1, such that the correlation between f (zi+1 , zi+16 ) and sign(zi+28 − 1/2) is at least 0.416, while it should be zero. A simple distribution on three variables that closely approximates the joint distribution of zi+1 , zi+16 , zi+28 is described. The region of zero density in the approximating distribution has volume 4/21 in the three dimensional unit cube. For every integer 1 ≤ k ≤ 10, there is a parallelepiped with edges 1/2k+1 , 1/2k and 1/2k+1 , where the density of the distribution is 2k . Numerical simulation confirms that the distribution of the original generator matches the approximation within small random error corresponding to the sample size. Keywords: pseudorandom number generator, Matlab, dependence
1 Institute
of Computer Science, Academy of Sciences of CR, Czech Republic, [email protected]
Institute of Computer Science
Academy of Sciences of the Czech Republic
New class of limited-memory variationally-derived variable metric methods J. Vlˇcek, L. Lukˇsan1 Technical report No. V 973 December 2006
Abstract: A new family of limited-memory variationally-derived variable metric or quasi-Newton methods for unconstrained minimization is given. The methods have quadratic termination property and use updates, invariant under linear transformations. Some encouraging numerical experience is reported. Keywords: Unconstrained minimization, variable metric methods, limited-memory methods, quadratic termination property, invariance property, numerical results
1
This work was supported by the Grant Agency of the Czech Academy of Sciences, project No. IAA1030405 and the Institutional research plan No. AV0Z10300504, L. Lukˇsan is also from Technical University of Liberec, H´alkova 6, 461 17 Liberec
Institute of Computer Science Academy of Sciences of the Czech Republic
Web Search Engines and Linear Algebra1 ˇ anek Roman Sp´ 2
Technical report No. 974 September 2006 Abstract: The technical report presents a brief overview on web search engines with deeper insight into their linear algebra background. The linear algebra plays very important rule in modern web search algorithms (e.g. Google). The report presents two algorithms, particularly HITS and PageRank. The algorithms are discussed on their convergence problems and also some improvements to their personalization abilities. The computation complexity is also mentioned and briefly sketched. Keywords: Web searching engines, PapeRank, HITS, Power Method
1 The work was supported by the project 1ET100300419 of the Program Information Society (of the Thematic Program II of the National Research Program of the Czech Republic) “Intelligent Models, Algorithms, Methods and Tools for the Semantic Web Realization”, partly by the Institutional Research Plan AV0Z10300504 “Computer Science for the Information Society: Models, Algorithms, Applications” and by Ministry of Education, Youth and Sports of the Czech Republic, project No. 1M4674788502 Advanced Remedial Technology and Processes. 2 Institute of Computer Science, Acad. of Sci. of the Czech Republic, P.O. Box 5, 182 07 Prague 8, Czech Republic
Institute of Computer Science
Academy of Sciences of the Czech Republic
Computing by Broadcasting: Alternation in Disguise (Extended Version)12 Jiˇr´ı Wiedermann3 and Dana Pardubsk´a4 Technical report No. 975 September 2006 Abstract: Wireless parallel Turing machine (WPTM) is a new computational model introduced recently by the authors. Its design has been inspired by wireless mobile networking. The WPTM is an entirely deterministic model of parallel computations where the processes communicate wirelessly via dynamically tuned broadcasting channels. We show a tight connection between the computations of WPTMs and those of the classical alternating Turing machines. Namely, we prove that time-space simultaneously bounded computations on WPTMs correspond exactly to similarly bounded computations of alternating Turing machines. This result leads not only to an alternate characterization of alternation, but it also offers an alternate view of bounded uniform circuit families, such as NCi and NC. Keywords: wireless parallel Turing machine; alternating Turing machine; time and space complexity; circuit complexity
1 The research was carried out within the institutional research plan AV0Z10300504 and partially supported by grant No. 1ET100300517 2 The research was partially supported by grant VEGA 1/3106/06 3 Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod Vod´ arenskou vˇ eˇ z´ı 2, 182 07 Prague 8, Czech Republic 4 Department of Computer Science, Comenius University, Mlynsk´ a dolina, 842 48 Bratislava, Slovakia, [email protected]
Institute of Computer Science
Academy of Sciences of the Czech Republic
Rates of approximation of smooth functions by Gaussian radial-basis networks Paul C. Kainen1 , Vˇera K˚ urkov´a2 , Marcello Sanguineti3 Technical report No. 976 October 2006 Abstract: Complexity of Gaussian radial-basis-function networks, with varying widths, is bounded above in terms of the rate of decrease of approximation error with increasing number of hidden units. Bounds are explicitly given in terms of norms measuring smoothness (Bessel and Sobolev norms). Estimates are proven using suitable integral representations in the form of networks with continua of hidden units computing scaled Gaussians and translated Bessel potentials. Keywords: Gaussian radial-basis functions, rates of approximation, Bessel’s potencials.
1 Department
of Mathematics, Georgetown University, Washington, D. C. 20057-1233, USA, [email protected] of Computer Science, Academy of Sciences of the Czech Republic, Pod Vod´ arenskou vˇ eˇ z´ı 2, Prague 8, Czech Republic, [email protected] 3 Department of Communications, Computer, and System Sciences (DIST), University of Genoa, Via Opera Pia 13, 16145 Genova, Italy, [email protected] 2 Institute
Institute of Computer Science
Academy of Sciences of the Czech Republic
UFO 2006 Interactive System for Universal Functional Optimization L.Lukˇsan, M.T˚ uma, J.Hartman, J.Vlˇcek, N.Rameˇsov´a, ˇ ska, C.Matonoha 1 M.Siˇ Technical report No. 977 December 2006
Abstract: This report contains a description of the interactive system for universal functional optimization UFO, version 2006. Keywords: Numerical optimization, nonlinear programming, nonlinear approximation, algorithms, software systems.
1 This work was supported by the Grant Agency of the Czech Academy of Sciences, project code IAA1030405, L.Lukˇ san, and M.T˚ uma are also from Technical University of Liberec, H´ alkova 6, 461 17 Liberec.
Institute of Computer Science
Academy of Sciences of the Czech Republic
New measures of central tendency and variability of continuous distributions Zdenˇek Fabi´an Technical report No. 978 October 2006 Abstract: A scalar inference function introduced in Fabi´an (2001) is generalized for a larger class of continuous distributions. Its first two moments are used for introduction of measures of the central tendency and the variability of the distribution. The number of examples shows that the new measures are plausible for continuous distribution, even for such for which the mean and/or the variance do not exist. They can be estimated from the data through the maximum likelihood estimates of the parameters; the estimates are expressed in particular cases by algebraic formulas without need to estimate the parameters. Mathematics Subject Classification Primary 62A01; Secondary 62F01. Keywords: Description of distributions; Basic statistics; Score function; Core function; Point estimates
Institute of Computer Science
Academy of Sciences of the Czech Republic
A lower bound technique for restricted branching programs (version F)1 ˇ ak2 Stanislav Z´ Technical report No. 979 November 2006 Abstract: We attempt to create a new lower bound technique based on a tight observation concerning separation of positive and negative input strings. This technique gives a superpolynomial lower bound for restricted branching programs computing a special Boolean function. Keywords: branching programs, lower bounds
1 Research partially supported by the “Information Society” project 1ET100300517 and the Institutional Research Plan AV0Z10300504. 2 Institute of Computer Science, Academy of Sciences of the Czech Republic, P. O. Box 5, 18207 Prague 8, Czech Republic, [email protected]
!#"%$'&)(*,+.-/0 "213(4'"%(657-/98;:<(>=@?%(2"A:CB ('DFE)GIHJ1K"
L
#MNJOQP)R S
M]\^R
TIUWVÀX
P_
P_Z#M
[
P_ÁÂ6R9PI ^`a]b c
bef g i `Ã i j @k d
l]monqpsrutwvqryx{z}|3~ vq| w qw 2w } e < w¯ww Äoe¤ §°¦º² Å[Æ ÇÈÉ]ºÊ}¤ ¤JJ¥¥w ¦ ËÌÍJ f«kη¤ Jfe uf£ Ïf«½f ÐI¦§yJ¦º§f«½f Ñu Ò 'ÓÔÕ ¼e£w3f«% Ϩeªf¥¤ »¢¡}Ê Ñf fe£ Ö¦ºfW y¥w Õ¦§Æ u¨ ×K fËK¼ °¥¥weÕ¦ÔË·Í f«i wÊf2 ¦ºØe ^¦§u¥J¦º§e«½ Âwy Òw<Ó ¼¥¥£ Ïf«o Ϩ¥ªfew¤J» Ù e¤J f£% ¤º¦ Ѻ» ¿f[×K Ñ e f×Ï¥ ue u¨ffeu¨Ú¤Jw2 ¹ ¼' e §e« u¨¬f ËK¼ ªfeÒ%ËÌÍJ f« ×Ïk £¥'º u¨ ¦§ueÛ Øff ¦wÓ [ËÌ¥ u ªº f£A¤ §¨f i×K2Øe¿f¦ ¨<eu¨<¿fwÑ£¥eu¨) ѧ×K ¦º§¨WÜFsÝ ÙiÞ Û{ߢ¹àÄháfw®¿IÑu¦Awwq źʥâ;Ñ ¤² )¦§y¥¥Ûf¥Øe w¦ Ó¬ ÊeA f¦º£)¦§u¥J¦º§f«ã ye¬6¥ k¥» ¦äÒ_ Ñw±yÑwe£f«
Institute of Computer Science
Academy of Sciences of the Czech Republic
Matematick´ y model zatˇ eˇ zov´ an´ı kloubn´ıho syst´ emu ˇ casovˇ e promˇ enn´ ymi silami Jiˇr´ı Nedoma Technical report No. 981 November 2006 Abstract: This paper represents the Technical Report of the Project of the Ministry of Industry and Trade of the Czech Republic No. FT-TA/087 and deals with constructions of quasi-static and dynamic models of human joints and their total replacements. Moreover, this paper deals with the numerical analyses of the quasi-static and the dynamic non-linear contact problems with Coulombian friction in linear elasticity in the quasi-static case and/or in visco-elasticity with short memory. The human skeletal systems are modelled by elastic or visco-elastic bodies of arbitrary shapes being in mutual contacts. The Coulombian law of friction on contact boundaries is assumed. In the quasi-static model the finite element technique and the semi-discrete scheme are assumed and in the dynamic case the semi-implicit scheme in time and the FE approximation in space are used. The error estimates, the convergences of the numerical approximations and the optimal error estimates are developed and discussed. Numerical simulation of Coulombian frictions are based on the Tresca models of friction. The problems of contact problems of Tresca type are formulated as mixed variational problems with Lagrange multipliers in 2D and 3D and the algorithms of finding the saddle point are based on the primal-dual active set strategies and/or on the Uzawa algorithm and conjugate gradient method with constrains in every step of Uzawa algorithm. Keywords: Biomechanics, human joints, total joint replacements, linear elasticity, visco-elasticity with short memory, Coulomb and Tresca models of friction, FEM, semi-discrete scheme, semi-implicit scheme
Institute of Computer Science
Academy of Sciences of the Czech Republic
Problematika pˇr´ıpravy 3D s´ıtˇ e pro metodu koneˇ cn´ ych prvk˚ u s vyuˇ zit´ım medic´ınsk´ ych obrazov´ ych dat a n´ asledn´ e moˇ zn´ e zp˚ usoby vizualizace v´ ysledk˚ u Josef Danˇek Technical report No. 982 December 2006 Abstrakt: ˇ ˇc. FT-TA/087 Komplexn´ı v´ Pˇredloˇzen´a studie je v´yzkumnou zpr´avou Projektu MPO CR yzkum bi” omechanick´ ych podm´ınek aplikace umˇ el´ ych skelet´ aln´ıch n´ ahrad, interakce n´ ahrad s organismem, vyhodnocen´ı pˇ r´ıˇ cin selh´ an´ı a n´ avrh podm´ınek pro zv´ yˇ sen´ı jejich stability“ za rok 2006 a u ´koly: B. Mechanick´ e a biomechanick´ e hodnocen´ı B.3.3. Numerick´e ˇreˇsen´ı 2D a 3D matematick´ych model˚ u metodou koneˇcn´ych prvk˚ u, vˇcetnˇe v´yvoje vhodn´ych algoritm˚ u, aplikace metod vyuˇz´ıvaj´ıc´ıch i v´ıceprocesorov´ych poˇc´ıtaˇc˚ u (tzv. domain decomposition methods). a C. Stanoven´ı podm´ınek pro zv´ yˇ sen´ı stability umˇ el´ ych n´ ahrad v lidsk´ em organismu C.3.3 Aplikace algoritm˚ u umoˇzn ˇuj´ıc´ıch numerickou anal´yzu umˇel´ych n´ahrad kloub˚ u (i) ve vazbˇe na CT sn´ımkov´an´ı, (ii) ve vazbˇe na navigovanou operaˇcn´ı techniku. Ve studii je diskutov´an probl´em z´ısk´av´an´ı 3D koneˇcnˇeprvkov´e s´ıtˇe pro modely lidsk´ych kloub˚ u a jejich n´ahrad. Pˇri generov´an´ı s´ıtˇe se vych´az´ı obrazov´ych dat z´ıskan´ych pomoc´ı poˇc´ıtaˇcov´e tomografie (CT) nebo magnetick´e rezonance (MRI). Ke zpracov´an´ı sn´ımk˚ u je nutn´e vyuˇzit´ı softwaru zamˇeˇren´eho na vizualizaci a 3D rekonstrukci objekt˚ u. Podobnˇe pro postprocessing je vhodn´e pouˇz´ıt software, kter´y umoˇzn ˇuje vizualizaci vypoˇcten´ych dat na koneˇcnˇeprvkov´e s´ıti. Keywords: Biomechanika, geometrie, metoda koneˇcn´ych prvk˚ u, poˇc´ıtaˇcov´a tomografie (CT), magnetick´a rezonance (MRI)
Institute of Computer Science
Academy of Sciences of the Czech Republic
V´ ysledky numerick´ eho modelov´ an´ı zat´ıˇ zen´ eho kolenn´ıho kloubu a jeho n´ ahrady s uvaˇ zov´ an´ım kloubn´ıho pouzdra J. Danˇek, J. Stehl´ık, J. Nedoma, I. Hlav´aˇcek Technical report No. 983 December 2006 Abstrakt: ˇ ˇc. FT-TA/087 Komplexn´ı v´ Pˇredloˇzen´a studie je v´yzkumnou zpr´avou Projektu MPO CR yzkum bi” omechanick´ ych podm´ınek aplikace umˇ el´ ych skelet´ aln´ıch n´ ahrad, interakce n´ ahrad s organismem, vyhodnocen´ı pˇ r´ıˇ cin selh´ an´ı a n´ avrh podm´ınek pro zv´ yˇ sen´ı jejich stability“ za rok 2006 a u ´koly: B. Mechanick´ e a biomechanick´ e hodnocen´ı B.3.3. Numerick´e ˇreˇsen´ı 2D a 3D matematick´ych model˚ u metodou koneˇcn´ych prvk˚ u, vˇcetnˇe v´yvoje vhodn´ych algoritm˚ u, aplikace metod vyuˇz´ıvaj´ıc´ıch i v´ıceprocesorov´ych poˇc´ıtaˇc˚ u (tzv. domain decomposition methods). a C. Stanoven´ı podm´ınek pro zv´ yˇ sen´ı stability umˇ el´ ych n´ ahrad v lidsk´ em organismu C.3.3 Aplikace algoritm˚ u umoˇzn ˇuj´ıc´ıch numerickou anal´yzu umˇel´ych n´ahrad kloub˚ u (i) ve vazbˇe na CT sn´ımkov´an´ı, (ii) ve vazbˇe na navigovanou operaˇcn´ı techniku. V´yzkumn´a zpr´ava obsahuje numerick´e v´ysledky pro modely kolenn´ıho kloubu bez tot´aln´ı n´ahrady (Model I) a d´ale pak v´ysledky pro modely kolenn´ıho kloubu s aplikovanou tot´aln´ı n´ahradou pro r˚ uzn´e stupnˇe valgozity (Modely II aˇz VI). Modely jsou uvaˇzov´any ve front´aln´ım ˇrezu a jejich souˇc´ast´ı je i kloubn´ı pouzdro. Keywords: Biomechanika, kolenn´ı kloub, tot´aln´ı n´ahrada kolenn´ıho kloubu, metoda koneˇcn´ych prvk˚ u
Institute of Computer Science
Academy of Sciences of the Czech Republic
Generalizations and Extensions of Lattice-Valued Possibilistic Measures, Part II1 Ivan Kramosil Technical report No. 985 December 2006 Abstract: In this technical report, the systematic investigation of lattice-valued possibilistic measures, opened in the first part of this report (cf. Technical Report No. 952, ICS AS CR, December 2005) is pursued and focused towards possibilistic variants of the notions of outer (upper) and lower (inner) possibilistic measures induced by a given partial possibilistic measure. The notion of Lebesgue measurability for possibilistic measures is defined and it is generalized to the notion of almost-measurability in the sense that the values of inner and outer measure ascribed to a set are not identical, as demanded in the case of Lebesgue measurability, but these two values do not differ ”too much” from each other in the sense definable within the lattice structure. In the rest of this report, the probabilistic model of decision making under uncertainty is modified to the case of lattice-valued possibilistic measures, so arriving at the notion of possibilistic decision function. The Bayesian and the minimax principles when quantifying the qualities of particular possibilistic decision functions are also analyzed and applied to some cases, e.g., to the case of possibilistic decision functions for state identification. Keywords: Lattice-valued possibilistic measures, inner (lower) and outer (upper) possibilistic measures, approximation and completion of partial lattice-valued possibilistic measures, decision making under uncertainty, possibilistic decision function, possibilistic loss function.
1 This research was partially supported by the grant No. IAA100300503 of GA AS CR and by the Institutional Research Plan AV0Z10300504 “Computer Science for the Information Society: Models, Algorithms, Application”
Institute of Computer Science Academy of Sciences of the Czech Republic
Evolving neural networks which control a simple robotic agent Roman Neruda, Stanislav Sluˇsn´y1 Technical report No. 986 December 2006 Abstract: The design of intelligent embodied agents represents one of the key research topics of today’s artificial intelligence. These agents should be able to adopt to changes of the environment and to modify their behaviour according to acquired knowledge. The goal of this work is the study of emergence of intelligent behaviour within a simple intelligent agent. Cognitive agent functions will be realized by mechanisms based on neural networks and evolutionary algorithms, where the evolutionary algorithm will be responsible for the adaptation of a neural network in a simulated environment. Keywords: Evolutionary algorithms, neural networks, robotic agent.
1
Acknowledgment This work was supported by the Ministry of Education of the Czech Republic under the project Center of Applied Cybernetics No. 1M684077004 (1M0567).
Institute of Computer Science
Academy of Sciences of the Czech Republic
Interior point methods for minimization of composite nonsmooth functions L.Lukˇsan, C.Matonoha, J.Vlˇcek
1
Technical report No. 987 December 2006
Abstrakt: In this report, we propose a class of primal interior point methods for minimization of composite nonsmooth functions. After a short introduction where composite nonsmooth functions are defined, we describe two algorithms based on iterative and direct determination of the minimax vector respectively. Finally, we investigate most important special cases a give results of numerical experiments, which demonstrate high efficiency of primal interior point methods for composite nonsmooth functions. Keywords: Numerical optimization, nonlinear programming, nonlinear approximation, algorithms, software systems.
1
This work was supported by the Grant Agency of the Czech Academy of Sciences, project code IAA1030405, L.Lukˇsan is also from Technical University of Liberec, H´alkova 6, 461 17 Liberec.
Institute of Computer Science
Academy of Sciences of the Czech Republic
Programy pro ˇreˇsen´ı rovnic chemick´ e kinetiky L.Lukˇsan, M.Rozloˇzn´ık, M.T˚ uma
1
Technical report No. V988 Prosinec 2006
Abstrakt: V pr´aci jsou analyzov´any rovnice popisuj´ıc´ı chemickou kinetiku a vyvinuty efektivn´ı metody pro jejich ˇreˇsen´ı. Jsou studov´any a implementov´any metody pro ˇreˇsen´ı tuh´ych syst´em˚ u neline´arn´ıch diferenci´aln´ıch rovnic s poˇc´ateˇcn´ımi podm´ınkami. Jsou t´eˇz pops´any pˇr´ısluˇsn´e programy napsan´e v jazyce Fortran a uvedeny jejich v´ypisy. Pˇriloˇzeny jsou uk´azky v´ypoˇctu a v´ysledky vzorov´eho probl´emu. Keywords: Chemick´a kinetika, neline´arn´ı diferenci´aln´ı rovnice, tuh´e syst´emy, implicitn´ı metody typu Runge-Kutta, softwarov´a realizace.
1
ˇ grant TANDEM: FT-TA/066, Tato pr´ ace byla podpoˇrena Ministerstvem pr˚ umyslu a obchodu CR, ˇ a v´ yzkumn´ ym z´amˇerem AV0Z10300504 Akademie vˇed CR.
Academy of Sciences of the Czech Republic
Fuzzy Class Theory: A Primer v1.0 Libor Bˇehounek and Petr Cintula1 Technical report No. 939 December 2006 Abstract: Fuzzy Class Theory was proposed as a formal background of an axiomatic approach to fuzzy mathematics built inside a sufficiently strong formal fuzzy logic. The goal of this text is to provide a thorough introduction to this theory for non-specialists in formal fuzzy logic. First, we give an informal exposition of the apparatus of the theory and explain how its results can be interpreted from the point of view of traditional fuzzy mathematics. Secondly, we address notable features of this theory, starting with the importance of graded theories, continuing through natural embedding and then fuzzifying of classical mathematical theories, ending with basic methodological guidelines regarding the latter. Finally, we show how to prove the results in Fuzzy Class Theory, by employing not only proof methods for particular first-order logic but also new strong methods which heavily utilize the advantages of formal build-up of the Fuzzy Class Theory. This is version 1.0 of the Primer. A newer version may be downloadable from www.cs.cas.cz/hp. Keywords: Fuzzy Class Theory, graded properties, proof methods
1 Institute of Computer Science, Academy of Sciences of the Czech Republic, P. O. Box 5, 182 07 Prague 8, Czech Republic, {behounek,cintula}@cs.cas.cz. The work of Libor Bˇ ehounek was supported by the grant No. B100300502 of the Grant Agency of the Academy of Sciences of the Czech Republic. The work of Petr Cintula was partly supported by the grant No. B100300502 of the Grant Agency of the Academy of Sciences of the Czech Republic and partly by by the Institutional Research Plan AV0Z10300504.
Institute of Computer Science Academy of Sciences of the Czech Republic
Correlation Dimension-Based Classifier Marcel Ji ina and Marcel Ji ina, jr.
Technical Report No. V-945
January 2006
Abstract An innovative approach that utilizes the correlation dimension (CD) both for probability density estimate of data and consequently for classification is suggested. The idea of correlation dimension classifier directly follows the principle of classifier, which uses the distribution mapping exponent (DME). The basic difference between these two approaches is that DME is a local feature while CD is global feature. A new "hyperbolic" approximation of the correlation integral for the correlation dimension estimation is suggested. It is shown that CD-based classifier outperforms DME classifier and many other classifiers published on Machine Learning Repository pages.
Keywords: Multivariate data; Correlation dimension; Nearest neighbors; Distribution mapping exponent; Power approximation, Classification, ML Repository. Pod Vodárenskou v ží 2, 182 07 Prague 8, phone: +420 266 051 111, fax: +420 286 585 789 e-mail: [email protected]
2
Institute of Computer Science
Academy of Sciences of the Czech Republic
European Summer School in Information Retrieval ESSIR 2005 Zdeˇnka Linkov´a1 Technical report No. 949 February 2006 Abstract: Information Retrieval (IR) as a process of searching relevant information is a significant discipline of a data processing field. European Summer School in Information Retrieval ESSIR provides students, academic and industrial researchers and developers a grounding in the core objects of IR (models, architectures, algorithms), as well as covering some current topics, e.g. information retrieval from the Web. We have participated its 5th year that was held at Dublin City University in Dublin, Ireland. Keywords: Summer school, Information Retrieval.
1 Institute
of Computer Science, Academy of Sciences of the Czech Republic,182 07 Prague 8, Czech Republic
! " #%$'& (*),+.-0/,1324$56)878$'):9;/,1=8)A@CBD)E$:>GF) HJILK*MN56$
O
PQRS! TVU%=R W=XTYZR[ \T]J
bfdZceg h ij J lk U;da=dYZrG.s
m n8o.ÎYZ hpq` a
jkZp
vlwyx{z[|}yE¤C Ò z |*
^_ :º a
u
} |x{}}
} =
d` ¢¡¤£¥¦§£©¨,ª§¬«®¯ °` ±L²£i³´´®¤µ¬£¶S· ¸º¹ »½ ¾*³´´¿ ~²Ä¸¨j£ j¨ Ï ©'¨j ¸Ò¦ ¢¦£ µÃyĹ ¦§¡ ¾¢º§¤±8 ¢¡ ¨T×±'S§¤º¸¨j£ Æ j¨Tײ¢¡ ~ ¨ ¨T׺ÍE¸ S¨dÓ §£Î£¥`¸¨j£Ô j¨`¹L£¥º ¹Ö6§ SE²£¶¢ ×ÄÍ8¦£¥§Í£ ¢±:¸ §Ó ¹¨j*¯¤« ?S¾ 磶¹¸`Ï
°£ ¢ ¹§¤±8 È º¨T §{µ¬ ¨ ¨T×ÄÍ"¸ ¨ µÎ²£¶¢ ×ÄÍ ¦£¥§Í£ ¢±:¸'§Ó'²§¤Æ ¹`¹ ¹¨j
!"! #$% '&() *,+#$ .-/10324&(567 "&(0 83& " 1#39: &;) <>=Ò?(?(@(?(?(AºCB 0 *, D/10 % "&(0E!F G H ! 0JILK ?NM{?(@(?(?(A(?O P * % 7 "&(0V&2W YXFZ: % + !" " P Q :E) !"! #R% S&( *:+N#J &;) T$?(AONA &2 = T "0 ") )#U&2 <
Institute of Computer Science
Academy of Sciences of the Czech Republic
Reasoning about Bang3 multi-agent systems in KR-Hyper Gerd Beuster, Roman Neruda, Bj¨orn Pelzer Technical report No. 955 January 2006 Abstract: Bang3 is a Multi-Agent-System platform focusing on soft computing. KR-Hyper is an automatic theorem proofer for First Order Logic. In this paper, we describe how KR-HYPER can be connected to Bang3 in order to allow reasoning about Multi-Agent-Systems. Keywords: MAS, Bang, KR-HYPER, Logic, Deduction, Description Logics, First Order Logic, Agents
Institute of Computer Science
Academy of Sciences of the Czech Republic
N´ avrh tot´ aln´ı n´ ahrady kolenn´ıho kloubu s rotaˇ cn´ı polyetyl´ enovou vloˇ zkou Jiˇr´ı Stehl´ık, Jiˇr´ı Nedoma Technical report No. 957 May 2006 Abstrakt: In the paper the analyses of effect of axial changes on the weight-bearing total knee replacenets (TKRs) in frontal and sagital planes are shortly discussed. On the basis of obtained numerical results two rotary types of TKRs are presented and discussed. Keywords: Total knee replacement (TKR), axial changes, rotary TKR.
Institute of Computer Science
Academy of Sciences of the Czech Republic
Biomechanical analysis of the effect of axial angle changes on the weight-bearing total knee replacements J. Stehl´ık1 , P. Vavˇr´ık2 , J. Danˇek3 , J. Nedoma4 , I. Hlav´aˇcek5 , F. Denk6 Technical report No. 958 May 2006 Abstrakt: The aim of this paper is to compare of the biomechanical influences of different grades of valgus deformity after the total knee replacement (TKR) based on the contact model problem with friction, the finite element method and the nonoverlapping domain decomposition method. Keywords: Biomechanics, knee, total replacement, valgus deformity
1 Orthopaedic Department, The Hospital Cesk´ ˇ ˇ e Budˇ ejovice, B. Nˇ emcov´ a Str. 585/54, 370 01 Cesk´ e Budˇ ejovice, Czech Republic, e-mail: [email protected] 2 1st Ortopaedical Department, 1st Medical Faculty of the Charles University Prague, V u ´ valu 84, 150 00 Prague 5 - Motol, Czech Republic, e-mail: [email protected] 3 Centre of Applied Mathematics, University of West Bohemia, Univerzitn´ ı 8, 306 14 Pilsen, Czech Republic and Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod vod´ arenskou vˇ eˇ z´ı 2, 182 07 Prague 8, Czech Republic e-mail: [email protected] 4 Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod vod´ arenskou vˇ eˇ z´ı 2, 182 07 Prague 8, Czech Republic, e-mail: [email protected] 5 Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod vod´ arenskou vˇ eˇ z´ı 2, 182 07 Prague 8, ˇ a 25, 115 67 Prague 1, Czech Republic and Mathematical Institute, Academy of Sciences of the Czech Republic, Zitn´ Czech Republic, e-mail: [email protected] 6 WALTER a.s., Jinonick´ a 329, 158 01 Prague 5 - Jinonice, Czech Republic, e-mail: [email protected]
Institute of Computer Science
Academy of Sciences of the Czech Republic
Analysis of axial angle changes on the weight-bearing total knee replacements J. Stehl´ık1 , P. Vavˇr´ık2 , J. Danˇek3 , J. Nedoma4 , I. Hlav´aˇcek5 , F. Denk6 Technical report No. 959 May 2006 Abstrakt: Background. The analysis of the effect of axial angle changes on the weight-bearing total knee replacements (TKR) was investigated and discussed. Methods. A two dimensional finite element models of the femorotibial joint in the frontal and the sagital planes were developed from CT images. For computation the nonoverlapping finite element technique develped in our institute was used. Results. The effect of axial angle changes on the weight-bearing total knee replacements is analysed in frontal and sagital planes. It is shown that optimal distribution of forces operated on the TKR in anteroposterior direction and well-balanced transition of forces in anteroposterior direction will correspond to the 7 deg. case. The results show a good agreement between theoretical and orthopadic observations. Keywords: Biomechanics, Knee, Total replacement, Axial changes
1 Orthopaedic Department, The Hospital Cesk´ ˇ ˇ e Budˇ ejovice, B. Nˇ emcov´ a Str. 585/54, 370 01 Cesk´ e Budˇ ejovice, Czech Republic, e-mail: [email protected] 2 1st Ortopaedical Department, 1st Medical Faculty of the Charles University Prague, V u ´ valu 84, 150 00 Prague 5 - Motol, Czech Republic, e-mail: [email protected] 3 Centre of Applied Mathematics, University of West Bohemia, Univerzitn´ ı 8, 306 14 Pilsen, Czech Republic and Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod vod´ arenskou vˇ eˇ z´ı 2, 182 07 Prague 8, Czech Republic e-mail: [email protected] 4 Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod vod´ arenskou vˇ eˇ z´ı 2, 182 07 Prague 8, Czech Republic, e-mail: [email protected] 5 Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod vod´ arenskou vˇ eˇ z´ı 2, 182 07 Prague 8, ˇ a 25, 115 67 Prague 1, Czech Republic and Mathematical Institute, Academy of Sciences of the Czech Republic, Zitn´ Czech Republic, e-mail: [email protected] 6 WALTER a.s., Jinonick´ a 329, 158 01 Prague 5 - Jinonice, Czech Republic, e-mail: [email protected]
Institute of Computer Science
Academy of Sciences of the Czech Republic
Boolean factor analysis by Hopfield-like autoassociative memory 1 A. A. Frolov2 and D. H´usek3 and I. P. Muraviev4 and P. A. Polyakov5 Technical report No. 961 February 2006 Abstract: The feature space transformation is a widely used method for data compression. Due to this transformation the original patterns are mapped into the space of features or factors of reduced dimensionality. In this paper we demonstrate that Hebbian learning in Hopfield-like neural network is a natural procedure for Boolean factor analysis. Due to this learning, neurons that tend to fire together (represent one common factor) are more correlated and thus create an attractor of the network dynamics. If the attraction basins around factors are large enough, the factors could be revealed by random search. This paper is dedicated to estimation of the size of attraction basins around factors. Two global spurious attractors are shown to prevent convergence of the network activity to the factors invalidating any procedure of their search. These global attractors can be completely deleted from network dynamics by introducing a single inhibitory neuron with bi-directional Hebbian synapses. Due to additional inhibition, the size of attraction basins around factors becomes the same as around the stored patterns in usual Hopfield network. The procedure of factors search is described in the accompanying paper. Keywords: Boolean factor analysis, Hopfield neural network, unsupervised learning
1 The work was partly supported by the Institutional Research Plan AV0Z10300504 ”Computer Science for the Information Society: Models, Algorithms, Appplications” and by grant Intelligent methods for increasing of reliability of electrical networks 1ET100300414 granted by GA AS CR 2 Institute of Higher Nervous Activity and Neurophysiology of the Russian Academy of Sciences, Butlerova 5a, 117 485 Moscow, Russia; e-mail: [email protected] 3 Institute of Computer Science Academy of Science of the Czech Republic, Pod Vod´ arenskou vˇ eˇ z´ı 2, 182 07 Prague 8, Czech Republic; tel. (+420)26605 3230, Fax: (+420) 28658 5789, e-mail: [email protected] 4 Institute of Higher Nervous Activity and Neurophysiology of the Russian Academy of Sciences, Butlerova 5a, 117 485 Moscow, Russia;e-mail: [email protected] 5 Institute of Optical Neural Technologies of the Russian Academy of Sciences, Vavilova 44, 119 333 Moscow, Russia; e-mail: [email protected]
Institute of Computer Science
Academy of Sciences of the Czech Republic
Boolean factor analysis by Hopfield-like autoassociative memory: factors search1 A. A. Frolov2 , D. Husek3 , P. Y. Polyakov4 , I. P. Muraviev5 Technical report No. 962 February 2006 Abstract: In our previous paper [6] we have shown that Hebbian learning in Hopfield-like neural network is a natural procedure for Boolean factor analysis. Hebbian learning forms a connection matrix of the network as a co-variation matrix of input signal space. Neurons that represent one common factor are more correlated and thus create attractor of the network dynamics. In this paper we describe a procedure of factors retrieval. According to this procedure, network dynamics evolve forward starting from a random initial state and stabilize in the attractor which corresponds to one of the factors (a true attractor) or one of the spurious attractors. Separation of true and spurious attractors is based on calculation of their Lyapunov function and activation threshold. We studied efficiency of the retrieval procedure by computer simulation. Keywords: Boolean factor analysis, Hopfield neural network, unsupervised learning, recall procedure, data mining.
1 This work was supported by grant from Grant Agency of Czech Republic, Prague No.201/05/0079 and by grant 1ET100300414 of the research program ”Information Society” granted by GA AS CR. 2 Institute of Higher Nervous Activity and Neurophysiology of the Russian Academy of Sciences; e-mail: [email protected] 3 Institute of Computer Science Academy of Science of the Czech Republice; E-mail: [email protected] 4 Institute of Optical Neural Technologies of the Russian Academy of Sciences; e-mail: [email protected] 5 Institute of Higher Nervous Activity and Neurophysiology of the Russian Academy of Sciences; E-mail: [email protected]
Institute of Computer Science
Academy of Sciences of the Czech Republic
Johnson score and characteristics of distributions 1 Zdenˇek Fabi´an Technical report No. 963 February 2006 Abstract: New measures of central tendency and dispersion of continuous probability distributions are introduced. They exist for common distributions and their estimates have necessary statistical properties. Their meaning is explained by means of instructive examples. Keywords: basic characteristics, variance, Johnson transform
1 The
work was supported by Grant Agency AS CR under grant IAA1075403.
Institute of Computer Science
Academy of Sciences of the Czech Republic
The minC Combination of Belief Functions: derivation and formulas.1 Milan Daniel2 Technical report No. 964 June 2006 Abstract: Principal ideas of the minC combination are recalled. A mathematical structure of generalized frames of discernment is analysed and formalized. A generalized schema for a computation of the minC combination is presented. Conflicting belief masses redistribution among non-conflicting focal elements is overviewed. Final general formulas for computation of the minC combination are presented. Some examples of computation of the minC combination follow. A brief comparison of the minC combination with other combination rules is presented. Related works and approaches and some open problems for a future research are referred in the end. Keywords: Belief function, Combination of belief functions, Dempster-Shafer theory, Conflict, Potential conflict, Contradiction, minC combination.
1 The support of the grant 1ET100300419 GA AV CR ˇ is kindly announced. The work was partly supported by the Institutional Research Plan AV0Z10300504 ”Computer Science for the Information Society: Models, Algorithms, Applications”. 2 [email protected]
Institute of Computer Science
Academy of Sciences of the Czech Republic
Prim´ arnˇ e du´ aln´ı metoda aktivn´ıch mnoˇ zin pro jednostrann´ y kontakt pruˇ zn´ ych tˇ eles s dan´ ym tˇren´ım I.Hlav´aˇcek Technical report No. 965 March 2006 Abstrakt: Uvaˇzujeme jednostrann´y kontakt dvou pruˇzn´ych rovinn´ych nebo prostorov´ych tˇeles. Sm´ıˇsen´a variaˇcn´ı formulace vede na probl´em sedlov´eho bodu, kter´y diskretizujeme metodou koneˇcn´ych prvk˚ u. K nalezen´ı sedlov´eho bodu aplikujeme novou metodu tzv. prim´arnˇe du´aln´ı strategie aktivn´ıch mnoˇzin (PDAS), kter´a se d´a ztotoˇznit se zobecnˇenou Newtonovou iteraˇcn´ı metodou. V 1. kapitole je analyzov´ano ˇreˇsen´ı koercivn´ıch i semi-koercivn´ıch u ´loh bez tˇren´ı. 2. resp. 3. kapitola je vˇenov´ana kontaktu s ”dan´ym” tˇren´ım podle Trescova modelu ve 2D-, resp. 3D-formulaci. K nalezen´ı pˇr´ısluˇsn´eho sedlov´eho bodu je navrˇzen iteraˇcn´ı algoritmus, kter´y kombinuje projekce z metody Uzawovy s metodou PDAS v kaˇzd´em iteraˇcn´ım kroku. Keywords: Jednostrann´y kontakt, dan´e tˇren´ı, metoda koneˇcn´ych prvk˚ u, sedlov´y bod, zobecnˇen´a Newtonova metoda
Institute of Computer Science
Academy of Sciences of the Czech Republic
HUGO: A Cognitive Architecture with an Incorporated World Model1 Jiˇr´ı Wiedermann Technical report No. 966 April 2006 Abstract: We present a design of cognitive system architecture with an internal world model. The internal world model is realized with the help of artificial mirror neurons. We consider generalized artificial mirror neurons acting both as a mechanism for assembling and learning multimodal sensorimotor information and as associative memory for invoking multimodal information given only some of its components. We show that within an artificial cognitive system a network of generalized mirror neurons can simultaneously serve as an internal world model recognized by the agent and as that of the agent’s position within this world. We also specify a self-organizing control mechanism, which is based on the basic operations over concepts that were essentially identified by the British 18th century philosopher David Hume. This control mechanism makes use of the internal world model constructed in agent’s interaction with real world and straightforwardly supports imitation learning. Building heavily on the properties of the generalized mirror net and on automatic abstract concept creation, we offer an algorithmic explanation of computational language acquisition, thinking and consciousness in our model. Rather than describing an implementation of the respective mechanisms, the aim of the paper is to establish a proof of the principle of algorithmic nature of higher cognitive functions. Keywords: cognitive systems; embodied cognition; internal world model; mirror neurons; thinking; consciousness
1 This work was done within the Institutional Research Plan AV0Z10300504 and was partially supported by grant No. 1ET100300419
Institute of Computer Science
Academy of Sciences of the Czech Republic
Chtěli byste být mozkem v baňce? Jiří Wiedermann1 Technical report No. 967 duben 2006 Abstrakt: Moderní teorie kognitivních systémů pohlíží na tyto systémy jako na autonomní vtělené výpočetní systémy, které se situují v okolí prostřednictvím svých senzomotorických jednotek. Přesto zejména v kruzích počítačových teoretiků je opakovaně slyšet názory, že na kognici lze pořád možné pohlížet i ”klasicky”, jako na problém specifického zpracování dat a že tudíž vtělení není nezbytné pro zachycení podstaty kognice. Ukážeme, že takto zjednodušený pohled opomíjí podstatnou vlastnost kognitivních systémů - a sice jejich aktivní vliv na výběr či dokonce vznik vstupních dat. Bez této zpětné vazby si systém nemůže vytvořit svůj vnitřní model světa poznaný prostřednictvím svých akcí. Pro vysvětlení povahy zmíněného problému použijeme výpočetní model kognitivních systémů zavedený autorem v předchozích pracích. Tento model umožní na principielní úrovni přemýšlet o fungování algoritmických mechanizmů imitace, komunikace, vzniku řeči, myšlení a vědomí a tím přispět i k jejich pochopení v živých systémech. Keywords: kognitivní systémy; vtělenost; situovanost; vnitřní model světa
1 Tato
práce vznikla v rámci výzkumného záměru AV0Z10300504 s částečnou podporou grantu 1ET100300419
Institute of Computer Science
Academy of Sciences of the Czech Republic
Integral combinations of Heavisides1 Paul C. Kainen2 , Vˇera K˚ urkov´a3 , Andrew Vogt4 Technical report No. 968 May 2006 Abstract: A sufficiently smooth function of d variables that decays fast enough at infinity can be represented pointwise by an integral combination of Heaviside plane waves (i.e., characteristic functions of closed half-spaces). The weight function in such a representation depends on the derivatives of the represented function. The representation is proved here by elementary techniques with separate arguments for even and odd d, and unifies and extends various results in the literature. Keywords: Feedforward neural network, perceptron, Heaviside function, plane wave, integral formula, Radon transform, Green’s function for iterated Laplacians, order of vanishing, function of controlled decay.
1 V. K. was partially supported by GA CR ˇ grant number 201/05/0557 and the Institutional Research Plan AV0Z10300504. Collaboration of the three authors was also supported by NAS COBASE grants and the Georgetown University International Affairs Office. 2 Department of Mathematics, Georgetown University, Washington, D.C. 20057-1233 3 Institute of Computer Science, Acad. of Sci. of the Czech Republic, P.O. Box 5, 182 07 Prague 8, Czech Republic 4 Department of Mathematics, Georgetown University, Washington, D.C. 20057-1233
Institute of Computer Science Academy of Sciences of the Czech Republic
Johnson system of parametric families1 Zdenˇek Fabi´an Technical report No. 969 July 2006 Abstract: We present a system of parametric unimodal continuous distributions, containing all possible types of score functions of prototypes. We call it a Johnson system since Johnson transformation is used for its construction. The system contains many used probability distributions, some of them in reparametrized forms, with unified meaning of parameters. Three non-Johnson systems are mentioned as well. 2000 Mahematics Subject Classification codes: 62A01, 62F01
Keywords: systems of distributions, transformation, core function
1 The
work was supported by the Grant Agency AS CR under grant IS 1ET400300513.
Institute of Computer Science
Academy of Sciences of the Czech Republic
A Model of an Amorphous Computer and its Communication Protocol1 Luk´aˇs Petr˚ u2 and Jiˇr´ı Wiedermann3 Technical report No. 970 August 2006 Abstract: We design a formal model of an amorphous computer suitable for theoretical investigation of its computational properties. The model consists of a finite set of nodes created by RAMs with restricted memory, which are dispersed uniformly in a given area. Within a limited radius the nodes can communicate with their neighbors via a single-channel radio. The assumptions on low-level communication abilities are among the weakest possible: the nodes work asynchronously, there is no broadcasting collision detection mechanism and no network addresses. For the underlying network we design a randomized communication protocol and analyze its efficiency. The subsequent experiments and combinatorial analysis of random networks show that the expectations under which our protocol was designed are met by the vast majority of the instances of our amorphous computer model. Keywords: amorphous computing; networks; communication protocols; random graphs; complexity;
1 This research was carried out within the institutional research plan AV0Z10300504 and partially supported by the ˇ grant No. 1ET100300419 and GD201/05/H014. GA CR 2 Faculty of Mathematics and Physics, Charles University, Malostransk´ e n´ amˇ est´ı 25, 118 00 Prague 1, Czech Republic, email:[email protected] 3 Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod Vod´ arenskou vˇ eˇ z´ı 2, 182 07 Prague 8, Czech Republic
Institute of Computer Science
Academy of Sciences of the Czech Republic
Johnson point and Johnson variance∗ Zdenˇek Fabi´an Technical report No. 971 July 2006 Abstract: New measures of central tendency and dispersion of continuous probability distributions were introduced in [1]. In this paper we show that they offer a simple and suitable description of heavy-tailed distributions, i.e., the distributions which may not have the mean and/or variance. MSC: 62A01, 62F01 Keywords: basic characteristics, Johnson transform, parametric estimates
∗ The author is indebted to I. Vajda for valuable critical remarks and suggestions. The work was supported by Grant Agency AS CR under grant number IAA1075403.
Institute of Computer Science
Academy of Sciences of the Czech Republic
A strong nonrandom pattern in Matlab default random number generator Petr Savicky1 Technical report No. 972 September 2006 Abstract: The default random number generator in Matlab versions between 5 and at least 7.3 (R2006b) has a strong dependence between the numbers zi+1 , zi+16 , zi+28 in the generated sequence. In particular, there is no index i such that the inequalities zi+1 < 1/4, 1/4 ≤ zi+16 < 1/2, and 1/2 ≤ zi+28 are satisfied simultaneously. This fact is proved as a consequence of the recurrence relation defining the generator. A random sequence satisfies the inequalities with probability 1/32. Another example demonstrating the dependence is a simple function f with values −1 and 1, such that the correlation between f (zi+1 , zi+16 ) and sign(zi+28 − 1/2) is at least 0.416, while it should be zero. A simple distribution on three variables that closely approximates the joint distribution of zi+1 , zi+16 , zi+28 is described. The region of zero density in the approximating distribution has volume 4/21 in the three dimensional unit cube. For every integer 1 ≤ k ≤ 10, there is a parallelepiped with edges 1/2k+1 , 1/2k and 1/2k+1 , where the density of the distribution is 2k . Numerical simulation confirms that the distribution of the original generator matches the approximation within small random error corresponding to the sample size. Keywords: pseudorandom number generator, Matlab, dependence
1 Institute
of Computer Science, Academy of Sciences of CR, Czech Republic, [email protected]
Institute of Computer Science
Academy of Sciences of the Czech Republic
New class of limited-memory variationally-derived variable metric methods J. Vlˇcek, L. Lukˇsan1 Technical report No. V 973 December 2006
Abstract: A new family of limited-memory variationally-derived variable metric or quasi-Newton methods for unconstrained minimization is given. The methods have quadratic termination property and use updates, invariant under linear transformations. Some encouraging numerical experience is reported. Keywords: Unconstrained minimization, variable metric methods, limited-memory methods, quadratic termination property, invariance property, numerical results
1
This work was supported by the Grant Agency of the Czech Academy of Sciences, project No. IAA1030405 and the Institutional research plan No. AV0Z10300504, L. Lukˇsan is also from Technical University of Liberec, H´alkova 6, 461 17 Liberec
Institute of Computer Science Academy of Sciences of the Czech Republic
Web Search Engines and Linear Algebra1 ˇ anek Roman Sp´ 2
Technical report No. 974 September 2006 Abstract: The technical report presents a brief overview on web search engines with deeper insight into their linear algebra background. The linear algebra plays very important rule in modern web search algorithms (e.g. Google). The report presents two algorithms, particularly HITS and PageRank. The algorithms are discussed on their convergence problems and also some improvements to their personalization abilities. The computation complexity is also mentioned and briefly sketched. Keywords: Web searching engines, PapeRank, HITS, Power Method
1 The work was supported by the project 1ET100300419 of the Program Information Society (of the Thematic Program II of the National Research Program of the Czech Republic) “Intelligent Models, Algorithms, Methods and Tools for the Semantic Web Realization”, partly by the Institutional Research Plan AV0Z10300504 “Computer Science for the Information Society: Models, Algorithms, Applications” and by Ministry of Education, Youth and Sports of the Czech Republic, project No. 1M4674788502 Advanced Remedial Technology and Processes. 2 Institute of Computer Science, Acad. of Sci. of the Czech Republic, P.O. Box 5, 182 07 Prague 8, Czech Republic
Institute of Computer Science
Academy of Sciences of the Czech Republic
Computing by Broadcasting: Alternation in Disguise (Extended Version)12 Jiˇr´ı Wiedermann3 and Dana Pardubsk´a4 Technical report No. 975 September 2006 Abstract: Wireless parallel Turing machine (WPTM) is a new computational model introduced recently by the authors. Its design has been inspired by wireless mobile networking. The WPTM is an entirely deterministic model of parallel computations where the processes communicate wirelessly via dynamically tuned broadcasting channels. We show a tight connection between the computations of WPTMs and those of the classical alternating Turing machines. Namely, we prove that time-space simultaneously bounded computations on WPTMs correspond exactly to similarly bounded computations of alternating Turing machines. This result leads not only to an alternate characterization of alternation, but it also offers an alternate view of bounded uniform circuit families, such as NCi and NC. Keywords: wireless parallel Turing machine; alternating Turing machine; time and space complexity; circuit complexity
1 The research was carried out within the institutional research plan AV0Z10300504 and partially supported by grant No. 1ET100300517 2 The research was partially supported by grant VEGA 1/3106/06 3 Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod Vod´ arenskou vˇ eˇ z´ı 2, 182 07 Prague 8, Czech Republic 4 Department of Computer Science, Comenius University, Mlynsk´ a dolina, 842 48 Bratislava, Slovakia, [email protected]
Institute of Computer Science
Academy of Sciences of the Czech Republic
Rates of approximation of smooth functions by Gaussian radial-basis networks Paul C. Kainen1 , Vˇera K˚ urkov´a2 , Marcello Sanguineti3 Technical report No. 976 October 2006 Abstract: Complexity of Gaussian radial-basis-function networks, with varying widths, is bounded above in terms of the rate of decrease of approximation error with increasing number of hidden units. Bounds are explicitly given in terms of norms measuring smoothness (Bessel and Sobolev norms). Estimates are proven using suitable integral representations in the form of networks with continua of hidden units computing scaled Gaussians and translated Bessel potentials. Keywords: Gaussian radial-basis functions, rates of approximation, Bessel’s potencials.
1 Department
of Mathematics, Georgetown University, Washington, D. C. 20057-1233, USA, [email protected] of Computer Science, Academy of Sciences of the Czech Republic, Pod Vod´ arenskou vˇ eˇ z´ı 2, Prague 8, Czech Republic, [email protected] 3 Department of Communications, Computer, and System Sciences (DIST), University of Genoa, Via Opera Pia 13, 16145 Genova, Italy, [email protected] 2 Institute
Institute of Computer Science
Academy of Sciences of the Czech Republic
UFO 2006 Interactive System for Universal Functional Optimization L.Lukˇsan, M.T˚ uma, J.Hartman, J.Vlˇcek, N.Rameˇsov´a, ˇ ska, C.Matonoha 1 M.Siˇ Technical report No. 977 December 2006
Abstract: This report contains a description of the interactive system for universal functional optimization UFO, version 2006. Keywords: Numerical optimization, nonlinear programming, nonlinear approximation, algorithms, software systems.
1 This work was supported by the Grant Agency of the Czech Academy of Sciences, project code IAA1030405, L.Lukˇ san, and M.T˚ uma are also from Technical University of Liberec, H´ alkova 6, 461 17 Liberec.
Institute of Computer Science
Academy of Sciences of the Czech Republic
New measures of central tendency and variability of continuous distributions Zdenˇek Fabi´an Technical report No. 978 October 2006 Abstract: A scalar inference function introduced in Fabi´an (2001) is generalized for a larger class of continuous distributions. Its first two moments are used for introduction of measures of the central tendency and the variability of the distribution. The number of examples shows that the new measures are plausible for continuous distribution, even for such for which the mean and/or the variance do not exist. They can be estimated from the data through the maximum likelihood estimates of the parameters; the estimates are expressed in particular cases by algebraic formulas without need to estimate the parameters. Mathematics Subject Classification Primary 62A01; Secondary 62F01. Keywords: Description of distributions; Basic statistics; Score function; Core function; Point estimates
Institute of Computer Science
Academy of Sciences of the Czech Republic
A lower bound technique for restricted branching programs (version F)1 ˇ ak2 Stanislav Z´ Technical report No. 979 November 2006 Abstract: We attempt to create a new lower bound technique based on a tight observation concerning separation of positive and negative input strings. This technique gives a superpolynomial lower bound for restricted branching programs computing a special Boolean function. Keywords: branching programs, lower bounds
1 Research partially supported by the “Information Society” project 1ET100300517 and the Institutional Research Plan AV0Z10300504. 2 Institute of Computer Science, Academy of Sciences of the Czech Republic, P. O. Box 5, 18207 Prague 8, Czech Republic, [email protected]
!#"%$'&)(*,+.-/0 "213(4'"%(657-/98;:<(>=@?%(2"A:CB ('DFE)GIHJ1K"
L
#MNJOQP)R S
M]\^R
TIUWVÀX
P_
P_Z#M
[
P_ÁÂ6R9PI ^`a]b c
bef g i `Ã i j @k d
l]monqpsrutwvqryx{z}|3~ vq| w qw 2w } e < w¯ww Äoe¤ §°¦º² Å[Æ ÇÈÉ]ºÊ}¤ ¤JJ¥¥w ¦ ËÌÍJ f«kη¤ Jfe uf£ Ïf«½f ÐI¦§yJ¦º§f«½f Ñu Ò 'ÓÔÕ ¼e£w3f«% Ϩeªf¥¤ »¢¡}Ê Ñf fe£ Ö¦ºfW y¥w Õ¦§Æ u¨ ×K fËK¼ °¥¥weÕ¦ÔË·Í f«i wÊf2 ¦ºØe ^¦§u¥J¦º§e«½ Âwy Òw<Ó ¼¥¥£ Ïf«o Ϩ¥ªfew¤J» Ù e¤J f£% ¤º¦ Ѻ» ¿f[×K Ñ e f×Ï¥ ue u¨ffeu¨Ú¤Jw2 ¹ ¼' e §e« u¨¬f ËK¼ ªfeÒ%ËÌÍJ f« ×Ïk £¥'º u¨ ¦§ueÛ Øff ¦wÓ [ËÌ¥ u ªº f£A¤ §¨f i×K2Øe¿f¦ ¨<eu¨<¿fwÑ£¥eu¨) ѧ×K ¦º§¨WÜFsÝ ÙiÞ Û{ߢ¹àÄháfw®¿IÑu¦Awwq źʥâ;Ñ ¤² )¦§y¥¥Ûf¥Øe w¦ Ó¬ ÊeA f¦º£)¦§u¥J¦º§f«ã ye¬6¥ k¥» ¦äÒ_ Ñw±yÑwe£f«
Institute of Computer Science
Academy of Sciences of the Czech Republic
Matematick´ y model zatˇ eˇ zov´ an´ı kloubn´ıho syst´ emu ˇ casovˇ e promˇ enn´ ymi silami Jiˇr´ı Nedoma Technical report No. 981 November 2006 Abstract: This paper represents the Technical Report of the Project of the Ministry of Industry and Trade of the Czech Republic No. FT-TA/087 and deals with constructions of quasi-static and dynamic models of human joints and their total replacements. Moreover, this paper deals with the numerical analyses of the quasi-static and the dynamic non-linear contact problems with Coulombian friction in linear elasticity in the quasi-static case and/or in visco-elasticity with short memory. The human skeletal systems are modelled by elastic or visco-elastic bodies of arbitrary shapes being in mutual contacts. The Coulombian law of friction on contact boundaries is assumed. In the quasi-static model the finite element technique and the semi-discrete scheme are assumed and in the dynamic case the semi-implicit scheme in time and the FE approximation in space are used. The error estimates, the convergences of the numerical approximations and the optimal error estimates are developed and discussed. Numerical simulation of Coulombian frictions are based on the Tresca models of friction. The problems of contact problems of Tresca type are formulated as mixed variational problems with Lagrange multipliers in 2D and 3D and the algorithms of finding the saddle point are based on the primal-dual active set strategies and/or on the Uzawa algorithm and conjugate gradient method with constrains in every step of Uzawa algorithm. Keywords: Biomechanics, human joints, total joint replacements, linear elasticity, visco-elasticity with short memory, Coulomb and Tresca models of friction, FEM, semi-discrete scheme, semi-implicit scheme
Institute of Computer Science
Academy of Sciences of the Czech Republic
Problematika pˇr´ıpravy 3D s´ıtˇ e pro metodu koneˇ cn´ ych prvk˚ u s vyuˇ zit´ım medic´ınsk´ ych obrazov´ ych dat a n´ asledn´ e moˇ zn´ e zp˚ usoby vizualizace v´ ysledk˚ u Josef Danˇek Technical report No. 982 December 2006 Abstrakt: ˇ ˇc. FT-TA/087 Komplexn´ı v´ Pˇredloˇzen´a studie je v´yzkumnou zpr´avou Projektu MPO CR yzkum bi” omechanick´ ych podm´ınek aplikace umˇ el´ ych skelet´ aln´ıch n´ ahrad, interakce n´ ahrad s organismem, vyhodnocen´ı pˇ r´ıˇ cin selh´ an´ı a n´ avrh podm´ınek pro zv´ yˇ sen´ı jejich stability“ za rok 2006 a u ´koly: B. Mechanick´ e a biomechanick´ e hodnocen´ı B.3.3. Numerick´e ˇreˇsen´ı 2D a 3D matematick´ych model˚ u metodou koneˇcn´ych prvk˚ u, vˇcetnˇe v´yvoje vhodn´ych algoritm˚ u, aplikace metod vyuˇz´ıvaj´ıc´ıch i v´ıceprocesorov´ych poˇc´ıtaˇc˚ u (tzv. domain decomposition methods). a C. Stanoven´ı podm´ınek pro zv´ yˇ sen´ı stability umˇ el´ ych n´ ahrad v lidsk´ em organismu C.3.3 Aplikace algoritm˚ u umoˇzn ˇuj´ıc´ıch numerickou anal´yzu umˇel´ych n´ahrad kloub˚ u (i) ve vazbˇe na CT sn´ımkov´an´ı, (ii) ve vazbˇe na navigovanou operaˇcn´ı techniku. Ve studii je diskutov´an probl´em z´ısk´av´an´ı 3D koneˇcnˇeprvkov´e s´ıtˇe pro modely lidsk´ych kloub˚ u a jejich n´ahrad. Pˇri generov´an´ı s´ıtˇe se vych´az´ı obrazov´ych dat z´ıskan´ych pomoc´ı poˇc´ıtaˇcov´e tomografie (CT) nebo magnetick´e rezonance (MRI). Ke zpracov´an´ı sn´ımk˚ u je nutn´e vyuˇzit´ı softwaru zamˇeˇren´eho na vizualizaci a 3D rekonstrukci objekt˚ u. Podobnˇe pro postprocessing je vhodn´e pouˇz´ıt software, kter´y umoˇzn ˇuje vizualizaci vypoˇcten´ych dat na koneˇcnˇeprvkov´e s´ıti. Keywords: Biomechanika, geometrie, metoda koneˇcn´ych prvk˚ u, poˇc´ıtaˇcov´a tomografie (CT), magnetick´a rezonance (MRI)
Institute of Computer Science
Academy of Sciences of the Czech Republic
V´ ysledky numerick´ eho modelov´ an´ı zat´ıˇ zen´ eho kolenn´ıho kloubu a jeho n´ ahrady s uvaˇ zov´ an´ım kloubn´ıho pouzdra J. Danˇek, J. Stehl´ık, J. Nedoma, I. Hlav´aˇcek Technical report No. 983 December 2006 Abstrakt: ˇ ˇc. FT-TA/087 Komplexn´ı v´ Pˇredloˇzen´a studie je v´yzkumnou zpr´avou Projektu MPO CR yzkum bi” omechanick´ ych podm´ınek aplikace umˇ el´ ych skelet´ aln´ıch n´ ahrad, interakce n´ ahrad s organismem, vyhodnocen´ı pˇ r´ıˇ cin selh´ an´ı a n´ avrh podm´ınek pro zv´ yˇ sen´ı jejich stability“ za rok 2006 a u ´koly: B. Mechanick´ e a biomechanick´ e hodnocen´ı B.3.3. Numerick´e ˇreˇsen´ı 2D a 3D matematick´ych model˚ u metodou koneˇcn´ych prvk˚ u, vˇcetnˇe v´yvoje vhodn´ych algoritm˚ u, aplikace metod vyuˇz´ıvaj´ıc´ıch i v´ıceprocesorov´ych poˇc´ıtaˇc˚ u (tzv. domain decomposition methods). a C. Stanoven´ı podm´ınek pro zv´ yˇ sen´ı stability umˇ el´ ych n´ ahrad v lidsk´ em organismu C.3.3 Aplikace algoritm˚ u umoˇzn ˇuj´ıc´ıch numerickou anal´yzu umˇel´ych n´ahrad kloub˚ u (i) ve vazbˇe na CT sn´ımkov´an´ı, (ii) ve vazbˇe na navigovanou operaˇcn´ı techniku. V´yzkumn´a zpr´ava obsahuje numerick´e v´ysledky pro modely kolenn´ıho kloubu bez tot´aln´ı n´ahrady (Model I) a d´ale pak v´ysledky pro modely kolenn´ıho kloubu s aplikovanou tot´aln´ı n´ahradou pro r˚ uzn´e stupnˇe valgozity (Modely II aˇz VI). Modely jsou uvaˇzov´any ve front´aln´ım ˇrezu a jejich souˇc´ast´ı je i kloubn´ı pouzdro. Keywords: Biomechanika, kolenn´ı kloub, tot´aln´ı n´ahrada kolenn´ıho kloubu, metoda koneˇcn´ych prvk˚ u
Institute of Computer Science
Academy of Sciences of the Czech Republic
Generalizations and Extensions of Lattice-Valued Possibilistic Measures, Part II1 Ivan Kramosil Technical report No. 985 December 2006 Abstract: In this technical report, the systematic investigation of lattice-valued possibilistic measures, opened in the first part of this report (cf. Technical Report No. 952, ICS AS CR, December 2005) is pursued and focused towards possibilistic variants of the notions of outer (upper) and lower (inner) possibilistic measures induced by a given partial possibilistic measure. The notion of Lebesgue measurability for possibilistic measures is defined and it is generalized to the notion of almost-measurability in the sense that the values of inner and outer measure ascribed to a set are not identical, as demanded in the case of Lebesgue measurability, but these two values do not differ ”too much” from each other in the sense definable within the lattice structure. In the rest of this report, the probabilistic model of decision making under uncertainty is modified to the case of lattice-valued possibilistic measures, so arriving at the notion of possibilistic decision function. The Bayesian and the minimax principles when quantifying the qualities of particular possibilistic decision functions are also analyzed and applied to some cases, e.g., to the case of possibilistic decision functions for state identification. Keywords: Lattice-valued possibilistic measures, inner (lower) and outer (upper) possibilistic measures, approximation and completion of partial lattice-valued possibilistic measures, decision making under uncertainty, possibilistic decision function, possibilistic loss function.
1 This research was partially supported by the grant No. IAA100300503 of GA AS CR and by the Institutional Research Plan AV0Z10300504 “Computer Science for the Information Society: Models, Algorithms, Application”
Institute of Computer Science Academy of Sciences of the Czech Republic
Evolving neural networks which control a simple robotic agent Roman Neruda, Stanislav Sluˇsn´y1 Technical report No. 986 December 2006 Abstract: The design of intelligent embodied agents represents one of the key research topics of today’s artificial intelligence. These agents should be able to adopt to changes of the environment and to modify their behaviour according to acquired knowledge. The goal of this work is the study of emergence of intelligent behaviour within a simple intelligent agent. Cognitive agent functions will be realized by mechanisms based on neural networks and evolutionary algorithms, where the evolutionary algorithm will be responsible for the adaptation of a neural network in a simulated environment. Keywords: Evolutionary algorithms, neural networks, robotic agent.
1
Acknowledgment This work was supported by the Ministry of Education of the Czech Republic under the project Center of Applied Cybernetics No. 1M684077004 (1M0567).
Institute of Computer Science
Academy of Sciences of the Czech Republic
Interior point methods for minimization of composite nonsmooth functions L.Lukˇsan, C.Matonoha, J.Vlˇcek
1
Technical report No. 987 December 2006
Abstrakt: In this report, we propose a class of primal interior point methods for minimization of composite nonsmooth functions. After a short introduction where composite nonsmooth functions are defined, we describe two algorithms based on iterative and direct determination of the minimax vector respectively. Finally, we investigate most important special cases a give results of numerical experiments, which demonstrate high efficiency of primal interior point methods for composite nonsmooth functions. Keywords: Numerical optimization, nonlinear programming, nonlinear approximation, algorithms, software systems.
1
This work was supported by the Grant Agency of the Czech Academy of Sciences, project code IAA1030405, L.Lukˇsan is also from Technical University of Liberec, H´alkova 6, 461 17 Liberec.
Institute of Computer Science
Academy of Sciences of the Czech Republic
Programy pro ˇreˇsen´ı rovnic chemick´ e kinetiky L.Lukˇsan, M.Rozloˇzn´ık, M.T˚ uma
1
Technical report No. V988 Prosinec 2006
Abstrakt: V pr´aci jsou analyzov´any rovnice popisuj´ıc´ı chemickou kinetiku a vyvinuty efektivn´ı metody pro jejich ˇreˇsen´ı. Jsou studov´any a implementov´any metody pro ˇreˇsen´ı tuh´ych syst´em˚ u neline´arn´ıch diferenci´aln´ıch rovnic s poˇc´ateˇcn´ımi podm´ınkami. Jsou t´eˇz pops´any pˇr´ısluˇsn´e programy napsan´e v jazyce Fortran a uvedeny jejich v´ypisy. Pˇriloˇzeny jsou uk´azky v´ypoˇctu a v´ysledky vzorov´eho probl´emu. Keywords: Chemick´a kinetika, neline´arn´ı diferenci´aln´ı rovnice, tuh´e syst´emy, implicitn´ı metody typu Runge-Kutta, softwarov´a realizace.
1
ˇ grant TANDEM: FT-TA/066, Tato pr´ ace byla podpoˇrena Ministerstvem pr˚ umyslu a obchodu CR, ˇ a v´ yzkumn´ ym z´amˇerem AV0Z10300504 Akademie vˇed CR.
Related Documents
Institute Of Computer Science
June 2020 12
Foundation Of Computer Science
April 2020 20
Basic Of Computer Science
May 2020 15
Computer Forensics - Computer Science
April 2020 28
Computer Science
May 2020 18