Debian pro mobilní zařízení Mobian (Wikipedie) byl vydán ve verzi 13 Trixie. Nová stabilní verze je k dispozici pro PINE64 PinePhone, PinePhone Pro a PineTab, Purism Librem 5, Google Pixel 3a a 3a XL, OnePlus 6 a 6T a Xiaomi Pocophone F1.
Operátor O2 představil tarif Datamanie 1200 GB . Nový tarif přináší 1200 GB dat s neomezenou 5G rychlostí, a také možnost neomezeného volání do všech sítí za 15 Kč na den. Při roční variantě předplatného zákazníci získají po provedení jednorázové platby celou porci dat najednou a mohou je bezstarostně čerpat kdykoli během roku. Do 13. listopadu jej O2 nabízí za zvýhodněných 2 988 Kč. Při průměrné spotřebě tak 100 GB dat vychází na 249 Kč měsíčně.
Byly publikovány informace o útoku na zařízení s Androidem pojmenovaném Pixnapping Attack (CVE-2025-48561). Aplikace může číst citlivá data zobrazovaná jinou aplikací. V demonstračním videu aplikace čte 2FA kódy z Google Authenticatoru.
Free Software Foundation (FSF) spustila projekt Librephone, jehož cílem je vytvoření svobodného operačního systému pro mobilní telefony. Bez binárních blobů.
Byla vydána verze 7 s kódovým název Gigi linuxové distribuce LMDE (Linux Mint Debian Edition). Podrobnosti v poznámkách k vydání. Linux Mint vychází z Ubuntu. LMDE je postaveno na Debianu.
Byl vydán Mozilla Firefox 144.0. Přehled novinek v poznámkách k vydání a poznámkách k vydání pro vývojáře. Vypíchnout lze lepší správu profilů. Řešeny jsou rovněž bezpečnostní chyby. Nový Firefox 144 bude brzy k dispozici také na Flathubu a Snapcraftu.
Discord potvrdil únik osobních údajů přibližně 70 000 uživatelů. Incident se týká uživatelů po celém světě, především těch, kteří v rámci ověřování svého věku nahráli do aplikace doklad totožnosti. Únik informací se netýkal systémů samotné platformy, ale došlo k němu přes kompromitovaný účet pracovníka zákaznické podpory u externího poskytovatele služeb.
Americká společnost OpenAI, která provozuje chatbota ChatGPT, kvůli výrobě vlastních procesorů pro umělou inteligenci (AI) spojí síly s firmou Broadcom. Firmy o tom informovaly (en) ve svém včerejším sdělení. OpenAI se snaží zajistit si výpočetní výkon potřebný k uspokojení rostoucí poptávky po svých službách. Akcie Broadcomu po zprávě výrazně zpevnily.
O víkendu 18. a 19. října lze na brněnském výstavišti navštívit s jednou vstupenkou dvě akce: Maker Faire Brno, "festival tvořivosti, vynálezů a bastlířské radosti", a GameDev Connect, "akci určenou pro všechny současné a hlavně budoucí herní vývojáře, kteří touží proniknout do jednoho z nejúžasnějších průmyslů na světě".
Do 20. října do 19:00 běží na Steamu přehlídka nadcházejících her Festival Steam Next | říjen 2025 (YouTube) doplněná demoverzemi, přenosy a dalšími aktivitami. Demoverze lze hrát zdarma.
Na regulární výrazy existuje několik pohledů. Pro ty, kteří je používat neumí, se jedná o magickou sekvenci znaků, které se nikdy nesnaží porozumět. Pro ty, kteří je používají, se jedná o mocný nástroj pro práci s textem, který lze použít při hledání, pro úpravy, nebo pro ověření vstupního řetězce. No a pro ty, kteří něco vědí o teoretické informatice, se jedná o větu jazyka typu 3. Navíc ta poslední skupina lidí tuší něco o konečném automatu a jeho vztahu k regulárním jazykům, výrazům.
Pochopitelně se nám tu vynořuje otázka. Pokud jsou regulární výrazy výsledkem gramatiky typu 3, to znamená nejméně mocné formy, proč se jimi vůbec zabývat? Proč nenasadit rovnou prostředky klasického programovacího jazyka, který je nepochybně mocnější a zvládne více věcí? Důvodů je několik. Předně síla jazyků typu 3 na většinu úloh stačí (a navíc současné výrazy u moderních nástrojů už patří do vyšších typů). Druhým důvodem je stručnost a (ne)přehlednost zápisu, oproti programové implementaci (jak se přesvědčíte dále). Kniha Art Of Unix Programming se v osmé kapitole zabývá minijazyky pro řešení specializovaných úloh, mezi něž se řadí i regulární výrazy. Obvykle je jednodušší napsat regulární výraz, než vytvořit jeho programovou implementaci.
Snad každého někdy napadlo — Jak to ten
Vezměme jednoduchý výraz grep
(sed
, perl
, ...) vlastně dělá? Jaká je posloupnost kroků od zadaného výrazu až po kód, který jej provádí?x*y+
, který značí vezmi libovolný počet znaků x, následovaný alespoň jedním znakem y.
Člověk, který o regulárních výrazech neslyšel, by pravděpodobně začal daný problém řešit asi takto:
function hledej1(inp) { byloX = false; // promenne udavajici byloY = false; // stav resene ulohy zac = 0; kon = 0; for (i = 0; i != inp.length; i++) { ch = inp.charAt(i); if (!byloX && !byloY && ch != "x" && ch != "y") { continue; } if (!byloX && !byloY && ch == "x") { byloX = true; zac = i; } if (!byloX && !byloY && ch == "y") { byloY = true; zac = i; } if ( byloX && !byloY && ch == "y") { byloY = true; } if ( byloX && byloY && ch != "y") { break;} kon++; } msg1 = "hledej1(\""+inp+"\") --> x*y+ "; msg3 = "\n"; if (!byloY) { msg2 = "nenalezen"; } else { msg2 = "nalezen (" + zac + ", " + kon + ")";} return msg1+msg2+msg3; }
Dlouho jsem přemýšlel, jaký jazyk zvolit pro příklady — C, C++, Javu, Python? Nakonec jsem se rozhodl pro Javascript a to z toho důvodu, že všechny příklady jsou jednoduché a navíc mohou být spuštěny přímo v prohlížeči. Bohužel mi dalo trochu práce ladění, protože se zdá, že některé konstrukce v jistých prohlížečích nepracují, jako třeba foreach
(Opera, MSIE) a indexování řetězců (MSIE). Nicméně skripty jsou úspěšně otestovány v prohlížečích Mozilla Firefox 1.5, Internet Explorer 6.0 a Konqueror 3.5 a Opera 9.0. Výsledek (dynamicky generovaný Javascriptem) máte zde:
Je nutné poznamenat, že tento způsob implementace je velice (velice jemně řečeno) nevhodný. Kód je zmatený, složitý, špatně se chápe a tím poskytuje prostor pro chyby (ostatně moje implementace pracuje špatně). Navíc, byť i jednoduchá změna, znamená, že je nutné celý program změnit.
Tím, co kód znepřehledňuje nejvíc, jsou stavové proměnné. Respektive jejich složité vztahy, které musíme v programu uhlídat pomocí složitých podmínek. Pokud se nám v kódu (v lepším případě v návrhu) podobné věci množí, bývá konečný automat nejvhodnějším řešením. Formálně je (nedeterministický, bude vysvětleno dále) konečný automat pětice M = (Q, Σ, δ, q0 ∈ Q, F ⊂ Q)
Nejdůležitějším pojmem u konečného automatu je stav. Koneckonců se někdy nazývají stavovými automaty (Finite State Automata v angličtině). Automat lze graficky znázornit:
Jak vidíte, automat se sestává se 3 stavů S, X a Y, přičemž S je startovacím stavem a Y koncovým. Ne náhodou je tento automat ekvivalentní regulárnímu výrazy x*y+
. Ve startovacím stavu S automat čeká na některý ze znaků x, nebo y. V případě příchodu znaku x se přepne do stavu X a ten neopustí, dokud nenačte znak y. Potom se přepne do stavu koncového stavu Y. Znak ¬y značí cokoliv mimo y, takže se ze stavu X můžeme dostat do počátku. Praktická implementace by mohla vypadat takto (přidal jsem 4. stav F, abych nemusel používat goto
, nebo cyklus while
):
function hledej2(inp) { states = { S : 0, X : 1, Y : 2, F : 3 } st = states.S; zac = kon = 0; for (i = 0; i != inp.length; i++) { ch = inp.charAt(i); switch (st) { case states.S: if (ch == "x") { st = states.X; zac = i;} if (ch == "y") { st = states.Y; zac = i;} break; case states.X: if (ch == "y") { st = states.Y; } else if (ch != "x") { st = states.S; } break; case states.Y: if (ch != "y") { kon = i - 1; st = states.F;} break; default: break; }; kon++; if (st == states.F) { st = states.Y; break;} } msg1 = "hledej2(\""+inp+"\") --> x*y+ "; msg3 = "\n"; if (st != states.Y) { msg2 = "nenalezen";} else { msg2 = "nalezen (" + zac + ", " + kon + ")";} return msg1+msg2+msg3; }
Tato, byť na počet řádků delší, ale jednoznačně přehlednější implementace konečného automatu, je přesně to, co mnoho programátorů s úspěchem používá. Je nutné říct, že takto natvrdo
naprogramovaný stroj trpí špatnou rozšiřitelností, ale místo konstrukce switch
case
lze z výhodou použít hashovací pole.
Ovšem i toto řešení trpí malou obecností. Pokud chceme změnit regulární výraz, nezbude nám, než kód přeprogramovat (anebo použít dynamické jazyky a hashovací pole místo konstrukce case
). Ovšem je tu ještě jedna možnost - jiný pohled na konečné automaty a to tabulka přechodů. Prakticky stejně jsou implementovány všechny pomocné knihovny pro konečné automaty.
Stav | S | X | Y |
x | X | X | S |
y | Y | Y | Y |
... |
Ještě než budeme pokračovat, zbývá nám vysvětlit jeden pojem. Deterministický (DKA), versus nedeterministický automat (NKA). U DKA je přechod jednoznačně dán příští stav aktuálním stavem a podmínkou. NKA může mít na jednu podmínku následujících stavů více. Oba automaty jsou ekvivalentní, ale nedeterministické jsou rychlejší, protože nemusí prohledávat všechny možnosti a vyberou si vždy správnou větev. Nevýhodou je, že naše počítače, jak je známe dnes, jsou deterministické, což znamená, že nedeterministické stroje se stejně musejí převést na deterministické. Fragment NKA je zobrazen na následujícím obrázku.
Mluvím o tom z toho důvodu, že běžně používaný algoritmus převádí regulární výrazy právě na NKA. Pokud se narazí na větev, která vede na více možností, program začne prozkoumávat jednotlivé cílové stavy (backtracking). Klasický postup skončí v případě nálezu prvního vyhovujícího výrazu. Posixová varianta v případě použité konstrukce "nebo" najde všechny vyhovující a vrátí nejdelší řetězec, ale tuto variantu běžné nástroje neimplementují, protože je nejpomalejší. Druhou možností je paralelní provádění všech cest, díky čemuž stačí jeden průchod a není třeba se vracet. Nevýhodou je skutečnost, že si nemůžete zapamatovat podvýrazy.
Toto byl pouze lehký úvod do problematiky konečných automatů. Zcela jsem vynechal problematiku stavových akcí, pojmy jako Mealy a Moorův automat. Nemluvili jsme o greedy regulárních výrazech a podobně. Navíc jsem tvorbu stroje pro provádění regulárních výrazů lehce odbyl. Jednak dnešní nástroje obecně regulární výrazy podporují. A v případě, že ne, je nejlepším způsobem jednoduše použít knihovnu PCRE (Perl Compatible Regular Expressions), která je syntakticky i sémanticky kompatibilní s regulárními výrazy Perlu. Což je defakto norma, protože skutečná norma POSIX se používá méně a její regulární výrazy nejsou tolik silné. Tuto knihovnu používají open source projekty Exim (pro nějž byla původně napsána), Apache, PHP, Postfix, nebo KDE.
Pokud chcete automaty vidět
na vlastní oči, podívejte se na Animace Teoretické informatiky, jedná se o flashové animace konečných (DKA i NKA) automatů, převodů NKA na DKA a mnoho dalších zajímavých věcí.
V dalším díle se zvolna přesuneme k problematice překladačů, na řadě je totiž syntaxe.
Nástroje: Tisk bez diskuse
Tiskni
Sdílej:
V případě příchodu znaku x se přepne do stavu X a ten neopustí, dokud nenačte znak yV tom případě máš drobnou chybku v obrázku u svislé šipky ze stavu X do Y.
deb http://ftp.cz.debian.org/debian jessie main contrib non-free
deb http://ftp.cz.debian.org/debian jessie main contrib non-free
hledej1("y") --> x*y+ nalezen (0, 1)
To je velmi optimistický výsledek... Moc pekny clanek, jak funguje grep me vzdycky zajimalo.
Jenom tenhle kus kodu mi prijde nejaky podezrely. javascript neznam, ale misto toho prvniho break bych videl radsi case ;)
break states.Y: if (ch != "y") { kon = i - 1; st = states.F;} break;
ostatně moje implementace pracuje špatněPomohla by pridat pred posledni podminku jeste jednu ?
if ( byloX && !byloY && ch != "y") { byloX = false; zac = 0; kon = 0;}
Dotaz 5: Opravil by muj navrh na pridani podminky tu implementaci ?
Diky moc za pripadne odpovedi a srry za takovou zbesilou tapetu, ale pro lidi co nemaji potrebnou vysokou skolu je dobre, kdyz se i v trivialitach ujisti. Je to lepsi nez stavet na necem co je blbe To x nad sipkou ze stavu X do Y je samozrejme spatne -- patri tam y (to je to alespon jedno y, ktere tam musi byt kvuli +). NFA je to proto, ze z jednoho stavu vede vice sipek s x. To je ten nedeterminismus. Konecny automat cte ze vstupni pasky jednotliva pismenka a kdyz dorazi do stavu X a zrovna ma cist dalsi pismenko x, tak nevi, kudy ma jit. Pokud by byl ten obrazek spravne (viz vyse), bude ten automat DFA (deterministicky), protoze v zadnem ze stavu neni moznost jit vice jak jednou cestou skrze jeden znak.Njn, pokud je nad sipkou "y" a pokud not(y) znamena cokoliv jineho krome x a y, pak nepovede z jednoho kolecka vice sipek ze stejnym pismenkem => je to spis DKA podle toho co rikas. Pokud ale not(y) zahrnuje i moznost "x" (bezohledu na to, ze tato moznost uz je tam konkretne zminena tou kruhovou sipkou), pak opravdu bude kolecko X s vice stejnymi moznostmi "uniku" a pak je to jednoznacne NKA jak pises. A pokud by byl obrazek spravne tak by opet bylo vice stejnych vetvi s jednoho kolecka a pak by to spis byl NFA ne ? Ted mi teda zbyva otazka, jak je to s tim not(y) v tomto pripade ? PS: jinak ostatni bylo velice pochopitelne napsano, diky :-}