Byly publikovány informace o novém bezpečnostním problému pojmenovaném GPU.zip (paper, GitHub). S vlastním logem. Jedná se o možný útok postranním kanálem na grafickou kartu (GPU). Proces může "krást pixely" jinému procesu.
Projekt GNU dnes slaví 40. výročí. Přesně před čtyřiceti lety, 27. září 1983, Richard Stallman oznámil, že se chystá napsat s Unixem kompatibilní operační systém GNU (Gnu's Not Unix). Hlavní oslava a setkání hackerů probíhá ve Švýcarsku ve městě Biel/Bienne. Na programu je také přednáška Richarda Stallmana.
Byl vydán Mozilla Firefox 118.0. Přehled novinek v poznámkách k vydání, poznámkách k vydání pro firmy a na stránce věnované vývojářům. Vypíchnout je nutno automatický lokální strojový překlad webových stránek. Řešeny jsou rovněž bezpečnostní chyby. Nový Firefox 118 je již k dispozici také na Flathubu a Snapcraftu.
Byla vydána nová major verze 15.0.0 softwaru OCRmyPDF pro přidávání textové vrstvy k naskenovaným PDF dokumentům (PDF/A). Přehled novinek v poznámkách k vydání. OCRmyPDF využívá pro optické rozpoznávání znaků (OCR) engine Tesseract.
Karel Matějka zveřejnil druhé demo své chystané hry Bzzzt. Kromě verze pro Windows a macOS je dostupná i verze pro Linux. Plná verze hry má vyjít zanedlouho.
Noví Bulánci byli oficiálně vydáni. V roce 2021 bylo na Startovači na podporu vývoje této hry vybráno 7,3 miliónů Kč. Hra je zatím určena jenom pro Windows, díky Protonu ale běží také na Linuxu.
ChatGPT může vidět, slyšet a mluvit.
Upscaler je open source nástroj pro zvýšení rozlišení a vylepšení obrázků pomocí AI. Vývoj probíhá na GitLabu. Instalovat lze také z Flathubu. Stejně jako Upscayl je Upscaler postaven nad Real-ESRGAN.
GNUnet (Wikipedie) byl vydán v nové major verzi 0.20.0. Jedná se o framework pro decentralizované peer-to-peer síťování, na kterém je postavena řada aplikací.
V Dublinu o víkendu proběhla dvanáctá iterace multimediální konference Video Dev Days, kterou pravidelně pořádá nezisková organizace VideoLAN. Záznamy přednášek z prvního a druhého dne jsou dostupné na YouTube.
Zdravím a prosím o pomoc s algoritmickým řešením následující úlohy:
Je dáno:
Pravidla:
Cílem je získat pro daný mix v pytlíku nejvíce bodů.
Díky za postrčení.
P.S. Hladový algoritmus? Generický algoritmus? Něco jiného? Jak na to? Nějaké knihovny atd.? Řešit to potřebuju v PHP.
Řešení dotazu:
*_kamenů >= 0 integer kombinace1 = 19 bodů kombinace2 = 11 bodů ... červených_kamenů = 2*kombinace1 + kombinace2 + ... ... červených_kamenů <= kolik_máš_červených_kamenů ... ct = sum kombinace*; max ct; solve
jelikož u té menší již znáte maximální skóre, je snadné spočítat maximální skóre i pro tu většíPokud znám nejlepší řešení pro 1 trojici a 2 trojice, nevidím jak snadno najít nejlepší řešení pro tří trojice. Jde najít kombimace, kdy v nejlepším řešení pro tři trojice nebude žádná trojice, která je v nejlepších řešeních pro 1 resp. 2 trojice.
maxSkore
budou cachovat):
// poctyKamenu je pole. poctyKamenu[i] oznacuje, kolik kusu i-teho kamene mame. function maxSkore(poctyKamenu) m = 0 for i = 1 .. 9 do for j = 1 .. 9 do for k = 1 .. 9 do if poctyKamenu umoznuji vybrat trojici (i, j, k) then od poctyKamenu odecti kameny pouzite v (i, j, k) m = max(maxSkore(poctyKamenu) + skore trojice (i, j, k), m) k poctyKamenu pricti kameny pouzite v (i, j, k) end if end for end for end for end function
m
, to jsem zapomněl.
for i = 1 .. 9 do for j = i .. 9 do for k = j .. 9 doDále lze v rekurzivních voláních
maxSkore
uvažovat pouze lexikálně stejně velké nebo vyšší trojice.
integer
podmínku, tak to asi nenajde optimum, ale řešení by mohlo být „docela dobré“ a spočítá se rychle).
x(1) = 3 x(2) = 9 ... x(n) = k(n)Dále mám nějaké kameny, to vyjádřím:
y(1) = 100 // tím zavedu počet kamenů, možná by mělo být y(m) <= k(m) ale to je detail y(2) = 23 ... y(9) = 11Otázka teď ale zní, jak vyjádřím závislost x(n) na kamenech - tedy y(m)? Podle mého nikdy nedostanu do jedné (ne)rovnice x(n) a y(m), protože hodnota kamenu není konstanta... Uniká mi něco?
Musím tedy volit jako proměnné trojice kamenůAno. Trojice kamenů očísluji 1-729 a
x(i)
bude vyjadřovat, kolikrát vyberu trojici s číslem i
.
Je-li c(i)
konstanta s cenou trojice číslo i
, pak chceme maximalizovat c(1)*x(1) + … + c(729)*x(729)
s tím, že počty použitých kamenů nesmí přesáhnout počty kamenů na vstupu.
Tj. označíme-li n(1), …, n(9) počty kamenů na vstupu, pak pro každé n(j) musí platit:
(suma x(i) takových, že trojice číslo i obsahuje právě jeden kámen j) + 2 * (suma x(i) takových, že trojice číslo i obsahuje právě dva kameny j) + 3 * (suma x(i) takových, že trojice číslo i obsahuje právě tři kameny j) <= n(j)
Trochu sem to pročetl a nevidím způsob, jak to na úlohu LP nasadit.Napsal jsem to výše. (btw. pokud to jde tím dynamickým programováním jak napsal Radek výše, tak to je mnohem lepší)
Pak to bude vypadat tak, že budu mít několik set funkcíAno, to není problém, třeba můj úkol pro předmět ze kterého pochází ten manuál měl 10k funkcí a výpočet trval pár sekund.
Otázka teď ale zní, jak vyjádřím závislost x(n) na kamenech - tedy y(m)?Vyrobíš si proměnné z(1) .. z(n), které značí, kolikrát jsi kterou kombinaci použil. Potom vyrobíš proměnné a(1) .. a(9), které v závislosti na vektoru z ukazují, kolik kamenů jsi využil.
a(1) = 1*z(1) + 2*z(2) + 1*z(4)pokud v kombinaci 1 je 1 kámen barvy 1, v kombinaci 2 jsou 2 kameny barvy 2, v kombinaci 3 žádný atd. Pak už jenom zadáš podmínky že nesmíš použít víc kamenů než máš
a(1) <= y(1)Pak zadáš účelovou funkci - součet ohodnocení * kolikrát ta kombinace padla
ct = z(1)*x(1) + z(2)*x(2) + .. + z(n)*x(n)A řešíš pro
max ctAle jak jsem psal, pokud to jde iterativně dynamicky, dá to lepší výsledek a nejspíš to doběhne i rychleji.
btw. pokud to jde tím dynamickým programováním jak napsal Radek výše, tak to je mnohem lepšíObávám se, že pro větší počet kamenů to je nepraktické. Například pro 100 kamenů celkem existuje 108! / 100! / 8! možných devític.
Do cache se dostane každá kombinace, tedy i všechny kombinace 10 trojicCache je 9-rozměrné pole o hranách kolik_kamenů_od_té_barvy_máme, ne? Takže pro 20 kusů od každého kamene je to „jenom“ 20^9 * sizeof(uint64) = 4 TB.
# x(i) ... promenna kolikrat jsem pouzil kombinaci i (vůbec nebo libovolně krát)
var x1 >= 0;
var x2 >= 0;
var x3 >= 0;
var x4 >= 0;
var x5 >= 0;
var x6 >= 0;
var x7 >= 0;
var x8 >= 0;
var x11 >= 0;
...
var x729 >= 0;
# c(i) ... hodnota kombinace i (dané konstanty)
var c1 = 6;
var c2 = 5;
var c3 = 6;
var c4 = 5;
var c5 = 5;
var c6 = 7;
var c7 = 8;
var c8 = 9;
var c9 = 5;
var c11 = 4;
...
var c729 = 3;
# vstupy a(i) - kolik mám kamenů daných typů (nerovnost, protože nemusím použít všechny)
var a1 <= 6;
var a2 <= 0;
var a3 <= 0;
var a4 <= 0;
var a5 <= 0;
var a6 <= 0;
var a7 <= 0;
var a8 <= 0;
var a9 <= 0;
# a(n) ... pocet pouzitych kamenu n... tohle je dáno zadáním - např. kombinace 1 je ze 3 kamenu typu 1, proto je v a1 člen 3*x1
v1: a1 = 0 + 3*x1 + 2*x2 + 2*x3 + 2*x4 + ...
v2: a2 = 0 + 1*x2 + 2*x11 + 1*x12 + 1*x13 + ...
v3: a3 = 0 + 1*x3 + 1*x12 + 2*x21 + 1*x22 + ...
v4: a4 = 0 + 1*x4 + 1*x13 + 1*x22 + 2*x31 + ...
v5: a5 = 0 + 1*x5 + 1*x23 + 1*x32 + 2*x41 + ...
v6: a6 = 0 + 1*x6 + 1*x15 + 1*x24 + 1*x33 + ...
v7: a7 = 0 + 1*x7 + 1*x25 + 1*x34 + 1*x43 + ...
v8: a8 = 0 + 1*x8 + 1*x17 + 1*x26 + 1*x35 + ...
v9: a9 = 0 + 1*x9 + 1*x27 + 1*x36 + 1*x45 + ...
# ucelova fce ct = c(1)*x(1) + c(2)*x(2) + .. + c(n)*x(n) - vždy násobím hodnotu kombinace krát počet jejích užití... celkový součet maximalizuji
maximize ct: 0 + c1*x1 + c2*x2 + c3*x3 + c4*x4 + c5*x5 + c6*x6 + ...
solve;
end;
Ty kombinace jsem zkrátil - teda vybral vždy jen jen tu nejlepší permutaci pro danou trojici kamenů - zbylo 165 kombinací.
Netušíte, v čem je zakopaný pes a co je špatně?
multiplication of linear forms not allowedNemůže být problém v tom, že násobíte proměnné jinýmy proměnnými? Místo c1, c2 atd. bych zkusil použít přímo konkrétní čísla.
/tmp> cat lin.mod var x1 >= 0; var x2 >= 0; var x3 >= 0; var x4 >= 0; param c1 := 6; param c2 := 5; param c3 := 6; param c4 := 5; var a1 <= 6; var a2 <= 0; var a3 <= 0; var a4 <= 0; v1: a1 = 0 + 3*x1 + 2*x2 + 2*x3 + 2*x4; v2: a2 = 0 + 1*x2; v3: a3 = 0 + 1*x2; v4: a4 = 0 + 1*x3; maximize ct: 0 + c1*x1 + c2*x2 + c3*x3 + c4*x4; solve; end; /tmp> glpsol -m lin.mod GLPSOL: GLPK LP/MIP Solver, v4.55 Parameter(s) specified in the command line: -m lin.mod Reading model section from lin.mod... 24 lines were read Generating v1... Generating v2... Generating v3... Generating v4... Generating ct... Model has been successfully generated GLPK Simplex Optimizer, v4.55 5 rows, 8 columns, 15 non-zeros Preprocessing... 1 row, 2 columns, 2 non-zeros Scaling... A: min|aij| = 1.000e+00 max|aij| = 2.000e+00 ratio = 2.000e+00 Problem data seem to be well scaled Constructing initial basis... Size of triangular part is 1 * 0: obj = 1.200000000e+01 infeas = 0.000e+00 (0) * 1: obj = 1.500000000e+01 infeas = 0.000e+00 (0) OPTIMAL LP SOLUTION FOUND Time used: 0.0 secs Memory used: 0.1 Mb (102316 bytes) Model has been successfully processedNo a tohle ti najde řešení, které když zaokrouhlíš, tak asi bude nějak „přiměřeně dobré“ (v tom předmětu ze kterého to pochází se pak třeba dokazuje jestli takto získané řešení není více než 2x horší než skutečné optimum atd.). Když za "x" proměnné napíšeš "integer" (var x1 >= 0, integer;), tak to najde optimum, ale asi to bude počítat dýl (obecně až exponenciálně dlouho).
obecně až exponenciálně dlouhoObecně i Simplex počítá exponenciálně dlouho (lineární programy lze však řešit v polynomiálním čase – například elipsoidovou metodou).
Tiskni
Sdílej: