Zoubir Layouni

Nowe wyniki dla problemu

Minimalizacja kolejnych bloków

• Broschiertes Buch

Produktbeschreibung

W tej ksi¿¿ce przyjrzymy si¿ specjalnej w¿äciwo¿ci macierzy binarnych, znanej jako "w¿äciwo¿¿ kolejnych 1". Kolejny blok to sekwencja kolejno po¿o¿onych jedynek. Problem polega na znalezieniu takiej permutacji kolumn, aby liczba kolejnych bloków w indukowanej macierzy by¿a minimalna. Wskazujemy, ¿e jest on NP-zupe¿ny dla ogólnych przypadków, a nast¿pnie przedstawiamy zastosowania, które go dotycz¿, warianty i aktualny stan wiedzy. Nasz pierwszy wk¿ad polega na udowodnieniu, ¿e CBM jest NP-zupe¿ne nawet wtedy, gdy macierz binarna ma tylko dwie jedynki na wiersz, poprzez wielomianowe przeksztäcenie problemu ¿äcucha Hamiltona o maksymalnej wadze do CBM ograniczonego do omawianych przypadków.Drugi wk¿ad polegä na rozwi¿zaniu pytania: czy CBM jest aproksymowalny z gwarancj¿? Odpowied¿ zostäa znaleziona w postaci wielomianowej heurystyki, która konstruuje permutacje skutkuj¿ce liczb¿ kolejnych bloków nie wi¿ksz¿ ni¿ 50% od optimum.

Produktdetails

• Verlag: Wydawnictwo Nasza Wiedza
• Seitenzahl: 56
• Erscheinungstermin: 23. Juni 2025
• Polnisch
• Abmessung: 220mm x 150mm x 4mm
• Gewicht: 102g
• ISBN-13: 9786208992255
• ISBN-10: 6208992257
• Artikelnr.: 74630872

Autorenporträt

O Dr. Zoubir Layouni obteve um doutoramento em ciências informáticas em 2010 pela Université Badji Mokhtar em Annaba, Argélia. Atualmente, é Professor Universitário e Vice-Diretor da Faculdade. Os seus interesses de investigação incluem a otimização, os algoritmos de aproximação e os problemas NP-difíceis.