Search

Given an edge-weighted undirected graph with weights specifying dissimilarities between pairs of objects, represented by the vertices of the graph, the clique partitioning problem (CPP) is to partition the vertex set of the graph into mutually disjoint subsets such that the sum of the edge weights over all cliques induced by the subsets is as small as possible. We develop an iterated tabu search (ITS) algorithm for solving this problem. The proposed algorithm incorporates tabu search, local search, and solution perturbation procedures. We report computational results on CPP instances of size up to 2000 vertices. Performance comparisons of ITS against state-of-the-art methods from the literature demonstrate the competitiveness of our approach.

Šiuolaikiniame pasaulyje vis daugiau žmonių naudoja išmaniuosius telefonus, kurie perima vis daugiau su kompiuterio atliekamo darbo (el. pašto tikrinimas, apsipirkimas internetu ir t.t.). Šiuose įrenginiuose vis daugiau funkcijų galima atlikti balsu (atidaryti programėles ir kt.), tačiau kol kas tik anglų ir keletu kitų kalbų. Todėl šiame darbe bus nagrinėjamas lietuvių kalbos atpažinimo uždavinys iOS platformai (viena iš pagrindinių išmaniųjų telefonų ir planšetinių kompiuterių platformų), kuri yra naudojama mobiliuose Apple įrenginiuose. Šiame darbe nagrinėjamas CMU Sphinx ir Julius bibliotekų panaudojimas iOS įrenginiuose atpažįstant lietuvių kalbą. Tyrimui buvo sukurtas LSR karkasas paslepiantis CMU Sphinx ir Julius bibliotekų realizacijos ypatumus po Objective-C kalbos sąsaja. Tyrimui buvo naudojamas skaičių nuo 0 iki 9 garsynas ir analizuota, koks atpažinimo tikslumas ir greitaveika yra su tokiu nedideliu 10 žodžių žodynu atpažįstant pavienius skaičius., Nowadays more and more people use smartphones which replaces more word done with personal computer (e-mail checking, e-shopping, etc.). In these devices more and more functions could be done with voice (open apps and other), but still only in english and some other languages. Therefore, in out work we will investigate Lithuanian speech recognition task in iOS (one of the major smartphones and tablets platforms), which runs in Apple's mobile devices. In this work we investigate CMU Sphinx and Julius libraries use in iOS devices for Lithuanian speech recognition. For this task LSR framework was created which encapsulated CMU Sphinx and Julius realisation nuances under Objective-C interfaces. Experiments were performed with numbers from 0 to 9 corpus and recognition accuracy and speed were investigated.

Šiame darbe yra analizuojama ir tiriama kaip veikia balso atpažinimo sistema HTK, kokie žingsniai turi būti atlikti norint sėkmingai atpažinti lietuviškai išartus žodžius. Taip pat apžvelgiamos kokių kalbos technologijų samprata reikalinga norint sukurti balso atpažinimo programą. Balso atpažinime labai svarbu yra kalbos signalų atpažinimo modeliai ir paslėptosios Markovo grandinės, todėl analizėje yra apžvelgiama jų veikimo principai ir algoritmai. This thesis will focus on how the speech recognition program HTK operates and what steps have to be taken in order to recognize spoken Lithuanian words. Also the emphasis of this thesis goes to conceptions of speech recognition technologies which are needed to create a speech recognition program.

Dinaminiai kelio paieškos algoritmai apjungia euristinės ir plečiamos (angl. incremental) paieškos metodus, sprendžiant eiles panašių paieškos uždavinių tiek žinant visą informaciją apie aplinką, tiek neturint jokios informacijos. Yra trys plečiamą paiešką naudojančių algoritmų klasės. Šiame darbe pateikiama trumpa dinaminių kelio paieškos algoritmų, naudojančių plečiamos paieškos metodus analizė. Pagrindinis darbo tikslas – visų trijų plečiamos paieškos klasių algoritmų, kuriuos naudojant gaunamas optimalus kelio paieškos sprendinys aplinkose, kur perėjimų tarp viršūnių svoriai gali didėti ir mažėti, palyginimas. Algoritmai lyginami trijose skirtingose situacijose: stacionarioje, judėjimo link tikslo (angl. goal – directed) bei judančio taikinio (angl. moving – target). Tyrimo rezultatai parodė, jog A* ir FSA* nepasiekiamų viršūnių kiekiui esant ~16000 yra ~23,6% našesni už GAA* ir trečios plečiamos klasės algoritmus, o pasiekiamumą keičiančių viršūnių kiekiui esant ~8000 – 42,3%. Nepasiekiamų viršūnių kiekiui kintant nuo 1000 iki 16000 trečios plečiamos klasės algoritmai yra vidutiniškai ~58,7% našesni už GAA* ir ~54% našesni už A* ir FSA*. Pasiekiamumą keičiančių viršūnių kiekiui kintant nuo 500 iki 8000 trečios plečiamos klasės algoritmai yra vidutiniškai ~69,3% našesni už GAA* ir ~47,8% našesni už A* ir FSA*. Dynamic path finding algorithms combine heuristic and incremental search methods to solve a series of similar search tasks in both known and unknown environments. There are three classes of incremental search algorithms. In this document we provide a brief summary of dynamic path finding algorithms, that uses incremental search methods, but its main focus is on comparing main algorithms of all three incremental classes, that are guaranteed to give optimal solution in environment where action costs can increase and decrease over time, and showing their strong and weak sides. The algorithms are compared in three different situations: stationary, goal – directed and moving – target. At the end of the document conclusions are given based on performed work. In this paper, research showed that A* and FSA* are ~23,6% more efficient than GAA* and third incremental class algorithms when the amount of untraversable cells is ~16000 and ~42,3% more efficient when the amount of traversability changing cells is ~8000. When the amount of untraversable cells is between 1000 and 16000, the third incremental class algorithms are ~58,7% more efficient than GAA* and ~54% – than A* and FSA*. When the amount of traversability changing cells is between 500 and 8000, the third incremental class algorithms are ~69,3% more efficient than GAA* and ~47,8% – than A* and FSA*.

Susidūrimų paieška - tai dviejų ar daugiau objektų susikirtimo radimas. Praktikoje susidūrimų paieška taikoma šiose srityse: kompiuteriniuose žaidimuose, netiesinėje baigtinių elementų analizėje, dalelių hidrodinamikoje, daugiafunkcinės dinamikos analizėje, įvairiose fizikos simuliacijose ir kt. Egzistuoja daugybė susidūrimų paieškos algoritmų, iš kurių populiariausi yra erdvinio skaidymo, hierarchinio struktūrizavimo ir atrinkimo bei rūšiavimo metodai. Šiame darbe yra tiriamas šių algoritmų veikimas ant CPU (Central processing unit) ir ant GPU (Graphics processing unit), analizuojami susidūrimų paieškos nustatymo būdai bei nagrinėjamos pasirinktų algoritmų veikimo spartinimo galimybės panaudojant CUDA (Compute Unified Device Architecture) technologiją. Ši technologija yra Nvidia sukurta nauja duomenų apdorojimo architektūra išnaudojanti grafinio procesoriaus resursus bendro pobūdžio skaičiavimams. Darbe iškeltų tikslų pasiekimui yra realizuotos kelios bazinės algoritmų versijos, jų pritaikymo lygiagretiems skaičiavimams galimybės ir taip pat atliekami bazinių algoritmų laiko, reikalingo skaičiavimams atlikti, grafinio procesoriaus atminties sąnaudos bei įvairių veikimo laiką įtakojančių faktorių tyrimai. Darbo pabaigoje aptariami lygiagretaus programavimo privalumai pritaikant nagrinėjamai temai. Šiame darbe atlikti tyrimai parodė, jog perduodant skaičiavimus į GPU pasiekiamas 200 kartų didesnis nagrinėjamų algoritmų našumas negu atliekant skaičiavimus naudojant CPU. Collision detection is a well-studied and active research field where the main problem is to determine if one or more objects collide with each other in 3D virtual space. Collision detection is an issue affecting many different fields of study, including computer animation, physical-based simulation, robotics, video games and haptic applications. There is a big variety of collision detection algorithms of witch spatial subdivision, octree and sort and sweep are three of them. In this document we provide a short summary of collision detection algorithms, but the main focus will be on analyzing and increasing their performance working on CPU (orig. Central processing unit) and GPU (orig. Graphics processing unit) separately by making use of CUDA (orig.Compute Unified Device Architecture) technology. This technology is a part of Nvidia, witch helps the use of graphics processor for general-purpose computation. Main goal of this research is achieved by performing analysis of implemented spatial subdivision, octree and sort and sweep algorithms. This analysis consists of both general performance, parallelization performance and various performance affecting factors analyses. At the end of the document, the advantages of parallel programming adapted to the present subject are discussed.

Šiuo tyrimu siekiama išanalizuoti populiariausių vartotojo sąsajos tyrimų metodus ir įvertinti juos įvairiais aspektais bei nustatyti jų taikymo atvejus. Taip pat suprojektuoti eksperimentinę erdvę ir atlikti tyrimą su vienu iš vartotojo sąsajos tyrimo metodu. Išanalizuoti rezultatus ir juos palyginti su panašiu vartotojo sąsajos tyrimo metodu. Galiausiai ieškosime būdų pagerinti šio metodo tikslumui. Analizės metu buvo įvertinta 15 vartotojo sąsajos metodų. Remiantis žiniomis įgautomis atliekant literatūros analizę apie vartotojo sąsajos tyrimų atlikimo eigą ir vertinimo parametrus buvo atliktas eksperimentas, kurio tikslas ištirti pelės sekimo tikslumą lyginant su akių sekimo metodo tikslumu. Išaiškinus priežastis lemiančias pelės sekimo metodo tikslumą, jas pašalinome ir pakartojome eksperimentą. Atlikus eksperimentus paaiškėjo, kad pagrindinis veiksnys lemiantis pelės sekimo metodo tikslumą yra dalyvių pasyvumas, o dalyvius informavus apie pelės judinimo būtinybę kartu su akių judesiais, užfiksuotas šio metodo tikslumo padidėjimas iki 47% - 77%. In this research we are going to analyze most popular user interface research methods and evaluate them in different aspects and determinate their use of cases. In addition, create experimental space for one of the user interface methods research. Analyze results and compare with similar method. Lastly, we will look for solutions to increase its accuracy. 15 user interface research methods were evaluated in analyze stage. From gathered knowledge about user interface research methods and evaluation parameters, experiment was performed. His purpose was to evaluate mouse tracking accuracy as user interface method and compare it with eye tracking method. After causes for its accuracy were found, they were removed and repeated the experiment. After conducting the experiment we found out that the main factor in mouse tracking accuracy is user's inability to move mouse actively. After asking experiment participants to sync their eyes movement with mouse movements we witnessed 47% - 77% accuracy comparing with eye tracking method.

Šiuo metu viena iš labiausiai bei sparčiausiai besivystančių technologijos krypčių yra mobiliesiems telefonams, planšetiniams kompiuteriams bei multimedijos įrenginiams skirta programinė įranga. Vartotojų susidomėjimas šia sritimi bei mobiliųjų įrenginių techninės įrangos tobulėjimas skatina vis daugiau IT kompanijų plėtoti savo veiklą šioje srityje. Viena iš didžiausių klaidų, kurias yra sunkiausia ištaisyti, yra pirminėje projekto stadijoje neteisingai pasirinktos technologijos. Šiame darbe apžvelgiamos ir palyginamos trijų populiariausių, į mobiliuosius įrenginius diegiamų operacinių sistemų: Android, iOS bei Windows Phone programų kūrimo sąsajos ir nustatomi jų privalumai bei trūkumai. Vertinimai yra atliekami atsižvelgiant į operacinės sistemos architektūrą, programų kūrimo įrankius, suderinamumą su technine įranga, programų derinimo galimybėmis, saugumo užtikrinimu, grafinės vartotojo sąsajos kūrimu, daugiakalbystės palaikymu, animacijos, garsų bei video medžiagos pateikimu, HTML turinio atvaizdavimu, integracija su žemėlapiais, vartotojo buvimo vietos nustatymu, sensorių bei tinklų pasiekiamumu, foninių procesų kūrimu, duomenų išsaugojimo bei apsikeitimo su kitomis programomis galimybėmis. Tyrimo metu nustatyta, kad Android turi geriausias sąsajas kurti foninius procesus bei integruotis su kitomis programomis. iOS turi geriausius įrankius bei grafinės vartotojo sąsajos kūrimo priemones, o Windows Phone turi patogiausia karkasą darbui su multimedija, žemėlapiais bei... [toliau žr. visą tekstą] At a present time, one of the most developing area of technology is software for mobile phones, tablets and multimedia devices. Growing numbers of users and improved hardware makes more and more companies to expand their activity in this market. One of the biggest mistakes, that is very hard to solve, is badly chosen technologies in a beginning stage of the projects. The main objective of this project is to compare three of the most popular operating systems Android, iOS and Windows Phone software development kits and to determinate their advantages and disadvantages. Analysis is made based on operating system architecture, tools, compatibility with hardware, debugging, security, graphical user interface, multilanguage support, animation, sounds, video, HTML preview, interaction with maps and user location, sensors, networks, background processes, data persistence and integration with another software. In this research was identified that Android has best interfaces to create background processes and share data between programs. iOS has best tools and components for graphical user interface and Windows Phone has best framework to work with multimedia, maps and user location services.

Pagrindinis šio darbo tikslas - išanalizuoti lietuvių kalbos semantinio anotavimo procesą ir sukurti metodologiją, leisiančią įgyvendinti semantinio anotavimo proceso automatizavimą. Kompiuteris, kitaip nei žmogus, nesupranta ar tekstas yra rišlus ir prasmingas, ar neturi jokio rišlumo ir prasmės. Tai ypač atsiliepia verčiant tekstus, lyginant tos pačios kalbos tekstus vieną su kitu ir t.t. Semantinis anotavimo procesas leidžia išspręsti šią problemą sukurdamas metodiką, kuri leidžia aprašyti žodžių sąsajas sakiniuose, tačiau norint tekstą semantiškai suanotuoti rankiniu būdu, reikia turėti specifinių žinių ir tai reikalauja didelių laiko sąnaudų. Norint išvengti šių problemų semantinį procesą būtina automatizuoti. Šiame darbe buvo išanalizuotas lietuvių kalbai tinkantis semantinio anotavimo procesas, sukurta metodologija, leidžianti įgyvendinti semantinio anotavimo proceso automatizavimą. Metodologijos pagrindu JAVA programavimo kalba įgyvendintas automatizuoto semantinio anotavimo proceso realizavimas, atliktas eksperimentas ir pateiktos išvados., Major aim of this work – analyze Lithuanian language semantic annotation process and develop methodology which let implement automate semantic annotation process. The computer, unlike the person, does not understand did the text is coherent and meaningful, or have no coherence and meaning. This is particularly vulnerable to the translation of the text, compared with the same language texts with one another, etc. Semantic annotation process allows to solve the problem of creating a methodology that enables to describe links between words in sentences, but in order to semantically annotate the text manually, you need to have specific knowledge and it requires time-consuming. To avoid these problems it is necessary to automate the process of semantic. In this work was analyzed the Lithuanian language suitability for semantic annotation process, developed methodology to implement semantic annotation of process automation. Methodology based Java programming language implementation of automated semantic annotation process realization of the experiment was conducted and the following conclusions.

There are three implemented algorithms in this work: lessons permutation, lessons permutation with simulated annealing adjustment, lessons permutation using Bayesian approach theory to optimize SA parameters algorithms. Algorithms and graphical user interface are programmed with JSP which is based on Java object programming language. To evaluate schedule goodness algorithms are computing every penalty points which are given for some inconvenieces. User is able to define how much penalty points will be given if some inconveniece is satisfied. Also he is able to assign stochastic algorithm parameters. There was accomplished theory, where was observed using of simulated annealing and Bayesian approch methods in other stochastic algorithms and their different combination. There is a description of profiled school schedule optimization algorithm, which is based on SA searching methodology: searching for the optima through lower quality solutions, using temperature function which convergence, difference in quality. Algorythm which is using BA was created in case to improve SA searching methodology. User by changing systems temperature or annealing speed througth parameters can make big influence to SA behaviour. Passing parameters then using algorithm with BA meaner influence is made to behaviour because this method prognosticates, acording to him, better parameters with which SA should work effectively and changing them. Researches with three stochastic algorithms were made after program was created. Analysed using randomization factor then optimizing schedule then different schedule variant are computed with same parameters. Exploring what big influence is made to stochatic algorithm then choosing correct parameters. Researched global minimum searching then function has a lot of local minimums. Analysed condition then stochastic algorithm found global minimum, studing influnece of making initial schedule to later optimization process. Whole experiments were performed with schedules from real Lithuanian school. For the calculation of initial schedule were used simple and stochastic, with coincidence factor mixing up lessons, algorithms.

To understand evolution, and to discover how different species are related, gene order analysis is a useful tool. Problems in this area can usually be formulated in a combinatorial language. We regard genomes as signed, or unsigned permutations, and thus evolutionary operations like inversions (reversing the order of a segment of genes) are easy to describe combinatorially. A commonly studied problem is to determine the evolutionary distance between two species. This is estimated by several combinatorial distances between gene order permutations, for instance the inversion distance. The main objective of this work was to survey the existing algorithms for genome comparison and to present new approach for solving this problem. The work led to these results: - We have surveyed existing approaches of genome comparison, namely comparison by inversion distance in signed and unsigned cases. It appeared that sorting signed genomes by inversions is done in quadratic time, but sorting unsigned genomes by inversions is NP-hard. - We have proposed the method of how to apply heuristic algorithms for sorting unsigned genomes by inversions. - We have applied tabu search and genetic algorithm to solve the sorting unsigned genomes by inversions problem. - We have experimentally proven, that the worst case solutions to sorting unsigned genomes by inversions found by heuristics (tabu search and genetic algorithm) are better then ones expected from best known approximating algorithm used for... [to full text]

A real-time system is one in which the correctness of the computations not only depends upon the logical correctness of the computation but also upon the time at which the result is produced. If the timing constraints of the system are not met, system failure is said to have occurred. Real-time system consist specialized hardware an software components. Nowadays, systems are so big and complex that teams of architects, analysts, programmers, testers and users must work together to create reliable real-time system. To manage this, a number of system development life cycle models have been created. System development life cycle refers to a methodology for developing systems. It provides a consistent framework of tasks and deliverables needed to develop systems. System development consist stages, that are common for all models: project planning, requirements definition, system design, implementation, testing, deployment and maintenance. However, there still are problems, that lead project to the failure. Problems appear while iterating from design stage to the implementation or prototype creation. Thesis describes methodology, that provide a way to overcome these problems. The main idea is to transform functional structure of the real-time system, that is designed using easy to understand graphical environment, to the executable code that will be able to run on target hardware components. Thesis describe the methods of doing such transformation. Methodology allows to create... [to full text]

Neural networks are one of the most efficient classifier methods. One of such classifying neural networks we are trying to teach in this work by using genetic algorithms. In this work we test two types of genetic algorithms. One may be called parameterized genetic algorithm. It is built on the basic ideas of genetic algorithms. The other one is called parameter less genetic algorithm. It was presented by F. G. Lobo and D. E. Goldberg. Both genetic algorithms are tested and compared to the other well known optimization methods such as Bayes and Monte Carlo search. Experiments show the relevance of use genetic algorithms in teaching classifying neural network. Also stated that parameter less genetic algorithm works more efficient than parametric genetic algorithm in general cases. Created programs will be used in future studies.