Symulowane wyżarzanie w asemblerze x86 (AMD64 + SSE)

Program, który powstał w sumie jako zakład z jednym z kolegów na kierunku. Celem było napisanie algorytmu symulowanego wyżarzania w asemblerze, bez łączenia z biblioteką C. Naturalnie, podjąłem ten zakład. Pierwszym problemem było opracowanie w jakiś sposób obliczania funkcji , co w sumie sprawiło, że projekt utknął w miejscu na bardzo długi czas. Po bardzo dużej ilości googlowania i przeglądania zestawu instrukcji udało się jednak tego dokonać.

Nie było też do dyspozycji generatora liczb pseudolosowych, przez co byłem zmuszony do zastosowania bardzo prostego (i pewnie mało efektywnego pod względem prawdziwej losowości) algorytmu, którego kiedyś znalazłem na Wikipedii (teraz nie umiem go znaleźć).

Jedyną funkcją udostępnianą jest funkcja annealing() o następującym prototypie :
void annealing(float Tstart,float Tmin,float alpha,uint32_t *sol,int solsize,int(*crit)(uint32_t*,int));

Tstart, Tmin i alpha to parametry samego procesu wyżarzania (opisane w jednym z artykułów), *sol to wskaźnik na tablicę zawierającą solsize elementów 32-bitowych, które są początkowym rozwiązaniem algorytmu. Do oceny rozwiązania wykorzystywana jest funkcja przekazywana za pomocą wskaźnika *crit, przyjmująca wskaźnik na tablicę i jej rozmiar, oraz zwracająca liczbę całkowitą będącą oceną przekazanego do niej rozwiązania. Przed wywołaniem funkcji należy również wypełnić pola dwuelementowej tablicy seed, która jest używana jako ziarno dla generatora liczb pseudolosowych.

Kod funkcji został napisany zgodnie z ABI dla Linuksa AMD64 z rozszerzeniami SSE (jako że każdy procesor obsługujący operacje 64-bitowe ma też SSE). Po modyfikacjach na pewno będzie bezproblemowo działać na zwykłych i386.

Jako przykładowe zastosowanie tej funkcji napisałem krótki program w C, który znajduje rozwiązanie problemu TSP dla instancji gr17. Wątpię, żeby moja implementacja była w jakikolwiek sposób szybsza bądź lepsza od analogicznej w C – pewnie jest nawet gorsza. Program powstał po to, żeby pokazać, że można.

Źródełka tutaj. Do kompilacji wymagany NASM. Public domain.

Anonimowe udostępnianie plików i folderów w Windows XP Pro

Dzisiaj prezentacja rozwiązania problemu, nad którym zastanawiałem się przez dość długi czas, mianowicie – jak sprawić, żeby (oczywiście nie wszystkie, ale chociażby wybrane) udostępniane w Windows XP Professional foldery były dostępne dla osób, które nie mają na tym komputerze konta. Rozwiązanie takie jest bardzo wygodne w małych sieciach lokalnych, jeśli chcemy udostępnić jakiś określony zasób każdemu, kto ma do tej sieci dostęp.

W Windows XP Home Edition zrobienie czegoś takiego jest banalnie proste, co wynika z okrojenia edycji Home z wszelkich opcji zabezpieczeń, powiedzmy, „enterprajsowych” – chociaż tutaj bardziej po prostu chodzi o stosowanie zwykłego schematu wywodzącego się prosto z Windows NT, bez żadnych jego uproszczeń.

Ale do rzeczy. Zaznaczam od razu, że wszelkie opisy tyczą się anglojęzycznej wersji systemu z zainstalowanym SP3. Komputer ten nie jest przyłączony do domeny i pracuje jako część grupy roboczej. Do naszego problemu mamy dwa rozwiązania :

• przydzielić każdemu użytkownikowi łączącemu się z zasobem dokładnie takie same prawa, bez względu na to, kim on jest,
• przydzielić inne uprawnienia użytkownikom anonimowym, a inne tym, którzy łączą się podając poprawną kombinację user/pass.

Pierwsze rozwiązanie jest idealną kalką „prostego udostępniania plików” znanego z Home Edition. Możemy je również wprowadzić na Professional, i to na dwa sposoby – pierwszym jest zaznaczenie odpowiedniej opcji w Opcjach folderów w Panelu sterowania.

Drugim sposobem natomiast (który nie spowoduje ograniczenia dostępnych opcji dotyczących zabezpieczeń zasobów współdzielonych oraz zabezpieczeń samych plików i folderów) jest zmodyfikowanie odpowiedniego ustawienia w Local Security Policy, gałąź Local Policies oraz Security Options nazwanego Network access: Sharing and security model for local accounts.

Ustawienie to ma dwie możliwe wartości, których chyba nie trzeba chyba dodatkowo wyjaśniać :

Jeśli chcemy, aby każdy łączący się z komputerem był rozpoznawany jako Guest (i otrzymywał tylko i wyłącznie jego uprawnienia), wybieramy drugą opcję.

Jedna z powyższych ścieżek wystarczy nam, aby zaimplementować „proste udostępnianie plików”. Jeśli szanowny czytelnik chce jednak mieć dokładniejszą kontrolę nad udostępnianymi zasobami, uprasza się o dalsze czytanie.

A więc : myśląc w ogóle o udostępnianiu anonimowym czegokolwiek, musimy mieć włączone konto gościa. Możemy tego dokonać przez aplet User Accounts w panelu sterowania, lub za pomocą ustawienia Accounts: Guest account status w Local Security Policy.

Musimy też odpowiednio zmodyfikować prawa, jakie posiada gość, a mianowicie jedno – prawo do dostępu do komputera z sieci, które domyślnie w XP Pro temu użytkownikowi jest odebrane. Znowu z pomocą przychodzi Local Security Policy :

Jeśli widzimy, że jest tam wspomniany „Guest”, to oczywiście usuwamy go. Teraz jest pora na modyfikację trzech kluczowych ustawień w Local Security Policy, mianowicie :

• Network access: Let Everyone permissions apply to anonymous users
• Network access: Named pipes that can be accessed anonymously
• Network access: Shares that can be accessed anonymously

Pierwsze z nich zmieniamy oczywiście na „Enabled”. W przeciwnym razie połączenia od użytkowników anonimowych nie będą mapowane do uprawnień nadanym grupie „Everyone”, przez co nie będą miały żadnych uprawnień i dla jakiegokolwiek zasobu dostaniemy po prostu „Access denied”.

Drugie ustawienie powinniśmy zmienić – a mianowicie dopisać tam srvsvc tylko, jeśli chcemy, żeby anonimowi użytkownicy mieli możliwość wylistowania wszystkich udostępnianych przez komputer zasobów. Jeśli tego nie zrobimy, użytkownik będzie musiał znać nazwę zasobu – niemożliwe będzie pobranie nazw wszystkich, do których można się ewentualnie dostać.

Trzecie ustawienie musimy zmieniać za każdym razem, gdy tworzymy lub usuwamy nowy anonimowo udostępniany zasób. Jeśli go tutaj nie dodamy, to nawet pomimo nadania uprawnień grupie „Everyone” anonimowi użytkownicy nie będą mieli do niego dostępu!

Local Security Policy możemy już zamknąć. Teraz wystarczy utworzyć zasób, pamiętając o uprawnieniach, jakie musimy nadać. Po wybraniu naszego katalogu wchodzimy więc do „Sharing” w jego właściwościach :

Nadajemy mu żądaną przez nas nazwę i ewentualnie jakiś elokwentny komentarz, a następnie modyfikujemy uprawnienia :

Wychodzimy z okienka zatwierdzając zmiany i wracamy do właściwości naszego folderu. Musimy jednak jeszcze nadać uprawnienia do dostępu do niego z poziomu samego systemu plików, a nie tylko jako udostępnianego zasobu. W tym celu przechodzimy na zakładkę obok we właściwościach.

Widzimy tutaj, że „Everyone” nie ma zupełnie praw dostępu do tego katalogu. Tak więc nawet jeśli anonimowemu użytkownikowi udałoby się uzyskać dostęp do zasobu (a teraz już by się udało), nie mógłby on w ogóle odczytać folderu reprezentowanego przez ten zasób. Dodajemy więc grupę „Everyone”, modyfikujemy uprawnienia, jakie chcemy nadać, i zatwierdzamy zmiany.

Należy w tym momencie zaznaczyć, że uprawnienia przydzielone do zasobu i do folderu to dwie różne rzeczy. Mając pełne uprawnienia do zasobu, lecz read-only dla folderu, nic w nim nie zapiszemy – i na odwrót. Dla przykładu, logując się do tego zasobu jako „Daniel” miałbym tylko uprawnienia do jego odczytu – ponieważ do zasobu tego ma tylko uprawnienia „Everyone”, i są to uprawnienia RO. Nikt nam jednak nie broni dodać Daniela do listy uprawnień zasobu i nadać mu ich więcej.

Nie zapominamy oczywiście do dodaniu naszego nowego zasobu do listy anonimowo dostępnych w Local Security Policy.

To wszystko. :) Zasób taki jest teraz dostępny anonimowo, czyli może się na niego zalogować ktokolwiek, podając zupełnie dowolną nazwę użytkownika, która nie występuje na tym komputerze, i zupełnie dowolne hasło. Jeśli nazwa już występuje – będziemy zobowiązani podać hasło dla tego użytkownika.

Co najciekawsze, Google jak i dokumentacja MS na temat anonimowego udostępniania w XP Pro z grupą roboczą niewiele potrafią powiedzieć. W dojściu do wielu z tych rzeczy o wiele bardziej pomógł mi Linux, a konkretniej mówiąc – smbclient. Wstydź się, Bill.

Symulowane wyżarzanie

Do czytelników : artykuł ten jest głównie adresowany do kolegów i koleżanek z kierunku, jednak powinien zainteresować każdego szukającego informacji o tym algorytmie metaheurystycznym.

Jako że wczoraj nie poszedłem na wykład dr. Cabana z systemów operacyjnych i męczą mnie z tego powodu wyrzuty sumienia, postanowiłem swój czas poświęcić na czyn społeczny i napisać krótki, acz konkretny artykuł na temat symulowanego wyżarzania. Przedstawione tutaj informacje będą trochę miksem notatek z wykładu dr. Kozika i moich własnych doświadczeń.

Algorytm symulowanego wyżarzania jest algorytmem wyszukującym przybliżone rozwiązanie konkretnej instancji jakiegoś problemu NP-trudnego. Jak wie każdy mniej więcej ogarnięty, przestrzeń możliwych rozwiązań problemów NP-trudnych jest z reguły na tyle duża, że odpada jej dokładne przebadanie, tj. sprawdzanie każdego możliwego rozwiązania po kolei. Dla problemu komiwojażera na przykład mamy rozwiązań, co już dla 20 miast daje liczbę na tyle dużą, że wykonanie takiego algorytmu zajmie niewiarygodnie dużo czasu. Wykorzystując algorytmy przybliżone jesteśmy w stanie znaleźć rozwiązanie, które może i nie będzie najlepszym (optymalnym), jednak będzie „wystarczająco dobrym”, a do tego zostanie ono znalezione w czasie w miarę rozsądnym.

Algorytmy metaheurystyczne zawsze działają inaczej, ponieważ w swoim działaniu opierają się na losowości – najbardziej ogólny algorytm metaheurystyczny będzie wyglądał tak :

while(i < limit_iteracji)
{
	wylosuj nowe rozwiązanie;
	jeśli jest lepsze od poprzednio wylosowanego, zapisz je;
	++i;
}

Taki „naiwny” algorytm jednak działa bardzo kiepsko, ponieważ za każdym razem przeskakuje w zupełnie inny punkt obszaru możliwych rozwiązań, a możliwe jest, że jeśli jesteśmy w jakimś punkcie, to rozwiązanie, które będzie od niego lepsze znajduje się zaraz obok niego – dlatego zdefiniujemy coś takiego jak otoczenie rozwiązania jako rozwiązanie mu sąsiadujące na przykład przez zamieniony jeden element. Czyli sąsiedztwem permutacji { 3, 7, 1, 2, 4, 5, 6 } może być permutacja { 3, 7, 1, 4, 2, 5, 6 }. Pierwszym pomysłem powinno być, by algorytm dostawał „jakieś” rozwiązanie początkowe (chociażby wylosowane) i działał tak długo, aż w sąsiedztwie nie znajdują się żadne lepsze rozwiązania. Jest z tym związany jeden mankament – aby to zobrazować, powiedzmy, że chcemy zminimalizować poniższą funkcję na obszarze ograniczonym wykresem.

Na pierwszy rzut oka widać, że funkcja ma globalne minimum w x=1 i lokalne minimum w okolicach x=-0.8. Jeśli rozwiązaniem początkowym naszego algorytmu będzie na przykład x = -0.25, to nie ma możliwości, by kiedykolwiek dotarł on do globalnego minimum, ponieważ nigdy nie będzie się ono znajdowało w sąsiedztwie badanego rozwiązania.

Modyfikacją takiego „naiwnego” algorytmu jest właśnie symulowane wyżarzanie, w którym zezwalamy na zmianę rozwiązania z pewnym prawdopodobieństwem, nawet wtedy, gdy jest ono gorsze – bo możliwe, że w sąsiedztwie gorszego będą lepsze niż te, które mamy w sąsiedztwie rozwiązania aktualnie rozpatrywanego. Dzięki temu symulowane wyżarzanie potrafi „unikać” problemów minimum lokalnego. Poza tym, cytując dr. Kozika „Własność losowości jest taka, że po pewnym czasie daje dobre wyniki”, co tutaj ma chyba jakiś sens.

Algorytm cechuje się następującymi parametrami :

• początkową temperaturą T,
• końcową temperaturą Tmin,
• funkcją prawdopodobieństwa P,
• funkcją obniżania temperatury G.

Funkcja prawdopodobieństwa określa, z jakim prawdopodobieństwem będziemy zmieniać rozwiązanie na gorsze. W „oryginalnej” odmianie symulowanego wyżarzania funkcja ta była zależna od oceny rozwiązania nowego, starego i aktualnej temperatury. Bierze się to z analogii tego algorytmu do procesu metalurgicznego – póki temperatura jest wysoka, akceptujemy zmiany na rozwiązania początkowo gorsze, ale potencjalnie lepsze. Zakładamy, że w miarę postępowania algorytmu i obniżania temperatury dojdziemy do rozwiązania „w miarę dobrego”, tak więc „ryzykowne” zmiany na rozwiązania początkowo gorsze nie będą już potrzebne. Z tego wynika też funkcja obniżania temperatury – wykonywana jest ona po każdej iteracji algorytmu i w oryginalnej odmianie była zależna od aktualnej temperatury i aktualnego numeru iteracji.

Po przeczytaniu tego wszystkiego poniższy pseudokod powinien być w miarę oczywisty.

i = 0
wybierz losowo rozwiązanie A
while(T > Tmin)
{
	stwórz rozwiązanie B przez zamianę dwóch losowych elementów w A
	if(Kryterium(B) < Kryterium(A)) A = B
	else if(random(0,1) < P()) A = B
	T = G()
	i = i+1
}

Jak widać, sama idea algorytmu jest bardzo prosta, jeszcze prostsze jest to, jak to zastosować w przypadku problemów przez nas rozpatrywanych – zarówno w przypadku komiwojażera, jak i szeregowania wystarczy po prostu zamienić ze sobą dwa elementy aktualnie rozpatrywanej permutacji i przeliczyć dla nich kryterium. I to wszystko.

Jedynym problemem jest dobranie funkcji P i G tak, aby algorytm dawał dobre rozwiązania. W przypadku P odpowiedź jest prosta :

Zakładając, że e to stała Eulera, f() to funkcja określająca kryterium rozwiązania, S’ to „nowe” rozwiązanie, S to „stare” rozwiązanie, a T to aktualna temperatura. Natomiast funkcja G :

lub

Gdzie gamma, alpha i k0 to „jakieś stałe” (twierdzenie, z którego pochodzi ten wzór mówi tylko tyle, że „istnieją”), k to aktualna iteracja algorytmu, a Tk to aktualna temperatura.

Dla zainteresowanych jako „further reading” polecam :

• Chances: The Simulated Annealing Solution
• Understanding Simulated Annealing

Mam nadzieję, że coś rozjaśniłem. Proszę rzucać pytania, jeśli się pojawią.

Chances: The Simulated Annealing Solution

Dwa przepisy na babkę

Dzisiaj w programie dwa przepisy na babki, które w moim domu robi się od dawna – pamiętam je jeszcze z bardzo wczesnego dzieciństwa. Dość proste w przyrządzeniu i bardzo, bardzo smaczne. :)

Babka makowo-piaskowa

• 20 dag (1 szklanka) mąki pszennej,
• 20 dag (niepełna szklanka) mąki ziemniaczanej,
• 25 dag margaryny,
• 25 dag (1 szklanka) cukru,
• 4 jajka,
• 1 szklanka maku,
• 1 1/2 łyżeczki proszku do pieczenia,
• 1/3 szklanki mleka,
• aromat migdałowy.

Mąkę pszenną przesiać z proszkiem do pieczenia. Margarynę ucierać, dodając stopniowo jajka, cukier, mąkę ziemniaczaną i mąkę pszenną z proszkiem. Do utartego ciasta wlać mleko, wsypać suchy mak i jeszcze raz dokładnie utrzeć ciasto. Wlać ciasto do wysmarowanej tłuszczem i wysypanej tartą bułką formy. Piec w umiarkowanie gorącym piekarniku (150 °C) około 50 minut. Gotową babę posypać cukrem pudrem lub polukrować.

Babka czekoladowa (łaciata)

• 1/2 kg mąki,
• 35 dag (1 1/2 szklanki) cukru,
• 25 dag masła lub margaryny,
• 4 jajka,
• 3/4 szklanki mleka,
• 3 łyżeczki kakao,
• 2 łyżeczki proszku do pieczenia,
• paczka cukru waniliowego.

Masło utrzeć do białości, dodać cukier, żółtka, cukier waniliowy, mąkę z proszkiem, mleko a na końcu pianę z białek. Rozdzielić ciasto na dwie połowy – jedną z nich zmieszać z kakao. Ciasto do natłuszczonej formy nakładać w kolejności : warstwa bez kakao, z kakao (cała) i na wierzchu bez kakao. Piec 60-90 minut w temperaturze ok. 150 °C.

Smacznego. :) Zapraszam do zadawania ewentualnych pytań w komentarzach.

Dynamiczna alokacja pamięci z poziomu assemblera [Linux]

Pisząc dzisiaj w assemblerze program zacząłem zastanawiać się, jak wygląda sprawa dynamicznej alokacji pamięci na stercie programowej z jego poziomu. Jak wiadomo, wszystkie dostępne assemblery umożliwiają tylko zaalokowanie stałej ilości pamięci w sekcji BSS lub sekcji danych, nie ma jednak sposobu na uzależnienie tej ilości od jakiejś liczby podawanej w runtime. Najbardziej oczywistym (i chyba też najbardziej efektywnym i najprostszym) rozwiązaniem jest zlinkowanie naszego programu z biblioteką C i wykorzystanie malloc.

Problem jednak pojawia się, gdy z jakichkolwiek powodów nie chcemy naszego programu linkować z libc – bo mamy taki kaprys, bo piszemy na platformę wbudowaną gdzie jej nie ma (chociaż to bardzo naciągany powód), bo uważamy że nasze metody alokacji pamięci będą o wiele ładniejsze i przyjemniejsze. Rozwiązaniem jest wykorzystanie wywołania systemowego (syscall) – pytanie tylko którego.

Pierwszymi wywołaniami narzucającymi się osobie szukającej są brk i sbrk, które zmieniają coś co podręcznik definiuje jako „program break”, czyli miejsce, gdzie kończy się sekcja niezainicjalizowanych danych programu. Przy wykorzystaniu tego pierwszego zmieniamy ten adres w sposób bezwzględny (czyli musimy podać nowy adres końca sekcji danych), natomiast argumentem tego drugiego jest liczba określająca, o ile bajtów ma on zostać zainkrementowany. Wywołań tych jednak nie będziemy używać, głównie z tego powodu, że wydają się one być stosunkowo trudne w obsłudze (gołe operacje na adresach, problemy z dealokacją miejsca – np. zaalokujemy dwa obszary jeden po drugim i chcemy pozbyć się tego pierwszego – będzie problem), a poza tym sam podręcznik odradza ich używania (co ciekawe, na rzecz wspomnianego już malloc). Ponadto wywołania te zostały usunięte z specyfikacji POSIX w roku 2001, co powinno samo w sobie mówić o tym ile są naprawdę warte.

Nasz cel osiągniemy używając wywołań mmap i munmap. Teoretycznie służą one do odtworzenia (zmapowania) w przestrzeni wirtualnej naszego procesu zawartości jakiegoś pliku – jednak mają one opcję tzw. anonymous mapping, czyli odwzorowania pamięci bez przypisania do pliku. Obszar pamięci w ten sposób zarezerwowany jest wtedy inicjalizowany zerami, co jest równoważne z wywołaniem funkcji C calloc. Dealokacją zajmuje się drugie wywołanie. Jedyny mankament jest taki, że do dealokacji musimy znać rozmiar zarezerwowanego obszaru pamięci, a nie sam jego adres (jak to jest w free).

Teraz trochę historii. mmap, jako jedna z najbardziej podstawowych funkcji kernela, została wprowadzona już w wersji 1.0. Niestety, tamte wersje jądra nie pozwalały na przesłanie przez rejestry więcej niż czterech parametrów wywołania (parametry od lewej do prawej w ebx, ecx, edx, esi), więc dla wywołań wymagających ich więcej potrzebne było ich „owinięcie” w pewną (zdefiniowaną przez jądro) strukturę i przesłanie jako parametr wskaźnika na tą strukturę. W przypadku mmap wyglądała ona tak (zapożyczone z linux-2.6.34.1/mm/mmap.c) :

struct mmap_arg_struct {
        unsigned long addr;
        unsigned long len;
        unsigned long prot;
        unsigned long flags;
        unsigned long fd;
        unsigned long offset;
};

Od jądra 1.3.0 wywołania systemowe mogły mieć 5 parametrów (dodano edi), a od 2.3.31 – sześć (dodano ebp). Aby to wykorzystać, napisane zostały nowe wywołania – funkcjonalnie równoważne starym, ale wykorzystujące możliwości nowych jąder. Tak więc mmap zamieniło się w mmap2, które jest dzisiaj używane. Na architekturze x64 nie ma nawet możliwości wywołania „starego” mmap, bo na niej absolutnie wszystkie argumenty (chociaż dalej może być ich maksymalnie 6) przekazywane są w rejestrach – kolejno rdi, rsi, rdx, r10, r8 i r9. W obydwu architekturach numer wywołania musi znajdować się w akumulatorze.

Przejdźmy jednak do konkretów, bo jakiś przydługawy ten wstęp. Prototypy naszych wywołań w rozumieniu C wyglądają następująco :

void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
int munmap(void *addr, size_t length);

Teraz zerknijmy do asm/unistd_32.h, gdzie znajdziemy numery wywołań systemowych. Wyglądają następująco :

#define __NR_mmap 90
#define __NR_munmap 91
#define __NR_mmap2 192

Pierwszy numer to „stary” mmap, czyli ten który wymaga od nas wskaźnika na strukturę mmap_arg_struct. mmap2 to ten „nowy”, który wszystkie swoje argumenty przyjmuje w rejestrach. Skoro o argumentach mowa, dobrze byłoby wiedzieć, jak mają one wyglądać w naszym przypadku. No więc tak (munmap pominę, bo ich znaczenie chyba jest oczywiste) :

• void *addr to początkowy adres odwzorowania, które chcemy utworzyć, traktowany jednak przez jądro tylko jako „wskazówka”. Jeśli jest równy NULL, to adres ten wybiera jądro (oczywiście jest on w obszarze pamięci wirtualnej procesu, który tą funkcję wywołał), i to właśnie nas interesuje.
• size_t length to oczywiście rozmiar odwzorowania w bajtach.
• int prot to flagi zabezpieczeń odwzorowania. Określają one, czy możemy z nim nic nie robić (PROT_NONE), czytać z niego (PROT_READ), zapisywać do niego (PROT_WRITE), czy też uruchamiać umieszczony w nim kod (PROT_EXEC). Flagi te są ze sobą ORowane celem pozyskania końcowej, w naszym przypadku interesują nas PROT_WRITE i PROT_READ, chyba że ktoś ma bardzo dziwne wymagania, to jeszcze może do tego dojść PROT_EXEC.
• int flags określają zaś, czy do naszego odwzorowania mają dostęp inne procesy – może ono być prywatne (MAP_PRIVATE) lub współdzielone (MAP_SHARED). Parametr ten musi być logicznym OR jednej (i tylko jednej, co chyba jest jasne) z tych stałych i innych, których pełna lista znajduje się w podręczniku (mmap(2)). Nas interesuje tutaj jedna konkretna stała : MAP_ANONYMOUS, która oznacza, że mapowanie nie odbywa się do pliku. Niektórzy mogą też próbować z stałą MAP_UNINITIALIZED (wspieraną od jądra 2.6.33 i dostępną tylko jeśli zostało ono odpowiednio skonfigurowane), która nie inicjalizuje odwzorowań „anonimowych” zerami.
• int fd to deskryptor pliku który ma zostać odwzorowany w pamięci. W przypadku MAP_ANONYMOUS parametr ten jest ignorowany. (chociaż, jeśli wierzyć podręcznikowe, to niektóre implementacje nawet w takim przypadku wymagają, by był on równy -1)
• off_t offset określa, na jakiej pozycji rozpocząć odwzorowanie pliku. Jak powyższy, jest ignorowany przy MAP_ANONYMOUS.

Nazwy pisane WIELKIMI LITERAMI to oczywiście nazwy stałych, które zostały z#define’dowane w odpowiednich plikach nagłówkowych (tutaj bits/mman.h).

W asm/unistd_64.h mamy natomiast :

#define __NR_mmap 9
#define __NR_munmap 11

Jak już wspominałem, nie ma podziału na „stary” mmap i „nowy” mmap2 – istnieje tylko jeden, który przyjmuje parametry przez rejestry.

Wykorzystując tą całą wiedzę napisałem taki oto moduł w assemblerze (NASM), który udostępnia funkcje służące do alokacji i dealokacji pamięci przy wykorzystaniu mmap (tego nowego, rejestrowego). Wszystko jest zgodne z ABI dla i386 i AMD64, więc nie będzie problemu z wykorzystaniem tego chociażby z poziomu C – prototypy w źródłach. Niestety WordPress nie ma podkreślania składni asemblerowej. :(

bits 32

section .text

mmap2             equ 192
munmap             equ 91 ; asm/unistd_32.h
PROT_READ         equ 0x1
PROT_WRITE         equ 0x2
MAP_ANONYMOUS     equ 0x20
MAP_PRIVATE     equ 0x02 ; bits/mman.h

; void *mmap_alloc(size_t ile [ebp+8])
global mmap_alloc
mmap_alloc:
 push    ebp
 mov        ebp,    esp ; ramka stosu
 push     ebx
 push     edi
 push     esi ; rejestry zarezerwowane dla f-cji wywolujacej

 xor     ebx,    ebx ; NULLujemy (ABI mowi, ze NULL == 0) void *addr
 mov     ecx,    [ebp+8] ; size_t length - podany do funkcji parametr
 mov     edx,    PROT_READ | PROT_WRITE ; int prot
 mov     esi,    MAP_ANONYMOUS | MAP_PRIVATE ; int flags
 mov     edi,    -1 ; int fd
 ; w ebp powinien sie jeszcze znalezc offset, ale mmap go ignoruje i dziala
 ; poprawnie bez niego, wiec w ogole go nie przekazujemy

 mov     eax,    mmap2 ; numer wywolania do eax
 int     0x80
 ; wynik wywolania systemowego jest w eax, zwracamy go jako wynik funkcji

 pop     esi
 pop     edi
 pop     ebx ; przywracamy rejestry
 mov     esp,    ebp
 pop     ebp
 ret ; i powracamy do f-cji wywolujacej

; int mmap_free(void* p [ebp+8],size_t ile [ebp+12])
global mmap_free
mmap_free:
 push     ebp
 mov     ebp,    esp
 push     ebx

 mov     eax,    munmap
 mov     ebx,    [ebp+8]
 mov     ecx,    [ebp+12]
 int     0x80

 pop     ebx
 mov     esp,    ebp
 pop     ebp
 ret

I to samo dla x64…

bits 64

section .text

mmap             equ 9
munmap             equ 11 ; asm/unistd_64.h

PROT_READ         equ 0x1
PROT_WRITE         equ 0x2
MAP_PRIVATE     equ 0x02
MAP_ANONYMOUS     equ 0x20 ; bits/mman.h

global mmap_alloc
; void *mmap_alloc(size_t size [rdi])
mmap_alloc:
 push     rbp
 mov     rbp,    rsp

 mov     rax,    mmap
 mov     rsi,    rdi ; size_t length
 xor     rdi,    rdi ; void *addr (NULLujemy zeby dac kernelowi dowolnosc)
 mov     rdx,    PROT_READ | PROT_WRITE ; int prot
 mov     r10,    MAP_PRIVATE | MAP_ANONYMOUS ; int flags
 mov     r8,        -1 ; int fd (ignorowany)
 xor     r9,        r9 ; off_t offset (ignorowany)
 sysenter

 mov     rsp,    rbp
 pop     rbp
 ret

global mmap_free
; int mmap_free(void *addr [rdi],size_t size [rsi])
mmap_free:
 push     rbp
 mov     rbp,    rsp

 mov     rax,    munmap
 ; wszystko jest juz w odpowiednich rejestrach
 syscall

 mov     rsp,    rbp
 pop     rbp
 ret

(niestety widzę że na wordpressie się to wszystko porozjeżdżało, jak coś to na pastebin : i386 ; x64)

Tak przygotowane funkcje umożliwiają nam stosunkowo bezbolesną dynamiczną alokację pamięci w Linuksie z poziomu assemblera. Wątpię jednak, żeby była to metoda w jakikolwiek sposób lepsza bądź efektywniejsza od najzwyklejszego malloc (albo raczej calloc w tym przypadku) – i moim zdaniem (tak jak i ludzi z ##asm na freenode) o wiele wygodniej, prościej i lepiej po prostu pogodzić się z tym linkowaniem z libc i wykorzystać funkcje, które daje.

Na koniec jeszcze słówko o error-checking : jak nietrudno zauważyć, żadna z napisanych przeze mnie funkcji nie sprawdza wartości zwracanej przez mmap/munmap i przekazuje ją bezpośrednio jako swój wynik działania. mmap zwraca adres na początek odwzorowania, jeśli się ono powiodło – jeśli natomiast nie, to zwraca wartość -1, czyli 0xff..ff. Rozsądnie jest jednak założyć, że każda wartość w przedziale od -1 do -4095 oznacza jakiś błąd – mówi o tym oficjalnie ABI AMD64, nie wspomina zaś ABI i386 – jednak podczas pisania tych funkcji wiele razy natknąłem się na jakąś dziwaczny adres który adresem nie mógł być i był na pewno liczbą ujemną różną od -1. munmap zaś zwraca 0, jeśli usunięcie odwzorowania powiodło się i -1, jeśli nie.

Ja naprawdę niewiele wymagam. Mieć swój komputer i swoją muzykę. No i może czasami coś zjeść, umyć się też byłoby fajnie. Więcej mi nie potrzeba.

the smiths shoutbox @ last.fm

pure tró.

wtf?

w życiu nie spodziewałbym się, że zajmę się cytowaniem treści 4chan-owych, ale jednak!

gość ma po prostu valid point.

Sprzętowe dekodowanie obrazu HD (720p, 1080p) na kartach Nvidia i ATI w Windowsie i Linuksie

Uznałem, że w Internecie nie ma takiego jednolitego poradnika/przewodnika, który wytłumaczyłby użytkownikowi – jak krowie na rowie – na czym polega sprzętowe dekodowanie obrazu o wysokiej rozdzielczości i jak je uzyskać na swoim komputerze. Tak więc całymi swoimi siłami spróbuję temat ten – wbrew pozorom, nie tak skomplikowany, wyjaśnić.

Obraz HD przechowywany jest na płytach Blu-Ray (no i HD DVD, ale ten format przegrał wojnę, więc go pomijamy) z rozdzielczością 1280×720 (to jest właśnie 720p) bądź 1920×1080 (czyli 1080p) oraz zakodowany kodekami VC1 bądź H264/AVC (w wczesnych etapach pojawiały się też zakodowane w MPEG-2, ale je też pomijamy). Jeśli chodzi o dźwięk, do wyboru jest więcej możliwości – wszystkie odtwarzacze Blu-Ray muszą być zdolne zdekodować dźwięk zakodowany na płycie kodekami Dolby Digital (znane też jako po prostu AC3), DTS, bądź PCM. Wszystkie te trzy kodeki były też dostępne na płytach DVD. Opcjonalnie odtwarzacze mogą też posiadać wsparcie dla kodeków takich jak Dolby Digital Plus, DTS-HD High Resolution Audio, bądź bezstratnych Dolby TrueHD czy DTS-HD Master Audio. Bardzo niewiele wydanych płyt Blu-Ray posiada jednak ścieżkę dźwiękową zapisaną w jednym z nowych formatów.

Problem pojawia się, gdy chcemy obraz HD odtworzyć na zwykłym komputerze. Przy zainstalowanych „zwykłych” kodekach (przyjmijmy, że ffdshow) z 720p nie powinniśmy mieć problemu (zakładając, że nasz komputer ma mniej niż, powiedzmy, 3 lata), jednak pojawi się on zapewne przy 1080p – procesor nie będzie „nadążał” z dekodowaniem obrazu w właściwym tempie, dlatego na ekranie (czy telewizorze) otrzymamy po prostu „skaczący” obraz, kompletnie rozsynchronizowany z dźwiękiem.

Jak temu zaradzić? Ano można – wykorzystując możliwości naszej karty graficznej. Bardzo możliwe, że jeśli jest ona stosunkowo świeża i pochodzi ze stajni Nvidii albo ATI, to możemy ją zaprzęgnąć do dekodowania obrazu HD – jednocześnie ściągając bardzo dużo obciążenia z naszego zwykłego procesora. Listy (chociaż zapewne niekompletne) kart zdolnych do sprzętowego dekodowania HD są na wikipedii – ATI i NVIDIA. Jeśli naszej karty nie ma na tej liście, a nie jest starsza niż – powiedzmy – dwa lata, to warto spróbować – a nuż zadziała.

Zwracam uwagę, że artykuł ten nie zajmuje się w jakikolwiek sposób złamaniem zabezpieczenia AACS występującego na płytach Blu-Ray – przyjmuję, że użytkownik ma do dyspozycji plik z obrazem HD zakodowanym kodekiem H264 lub VC1 (dźwięk pomijamy, bo w większości przypadków jest to AC3 albo DTS – a z nimi sobie bez problemu radzi mój ulubiony AC3Filter czy chociażby po prostu ffdshow). Źródło pochodzenia tego pliku nie musi być mi znane. ;)

Teraz opiszę, jak uzyskać sprzętowe dekodowanie HD – najpierw na Windowsie, później na Linuxie.

Sprzętowe dekodowanie HD na Windows

Na Windows sprawa wygląda dość prosto, i – w odróżnieniu od Linuxa – tak samo dla kart firmy Nvidia, jak i ATI. Cała sprawa polega na tym, że w odróżnieniu od standardowego API VfW (Video for Windows), z którego korzystają praktycznie wszystkie kodeki i który przekazuje wszystkie funkcje dekodujące na procesor, a kartę graficzną traktuje po prostu jako urządzenie do rysowania obrazu, musimy skorzystać z kodeka wykorzystującego API DXVA (DirectX Video Acceleration), który korzysta z funkcji DirectX w celu dostania się do funkcji przetwarzających karty graficznej.

Jest wiele programów, które mają wbudowane kodeki wykorzystujące DXVA :

• WinDVD
• PowerDVD
• PowerCinema
• Media Player Classic Homecinema
• Media Portal
• KMPlayer
• GOM Player

Moim wyborem jest jednak mój ulubiony Media Player Classic Homecinema. Jego strona znajduje się tutaj, a jeśli chodzi o ściąganie to do wyboru mamy :

• wersję 32-bitową [v1.2.908.0 x86]
• wersję 64-bitową [v1.2.908.0 x64] (przypominam, że nawet jeśli mamy 64-bitowy procesor i 32-bitowy system operacyjny, to pobieramy wersję 32-bitową. jakiekolwiek kodeki zewnętrzne (chociażby wspominany już nie wiem który raz ffdshow) muszą też być w wersji 64-bitowej, inaczej program nie będzie miał do nich dostępu)

Gdy program ten już ściągniemy i rozpakujemy (nie ma on instalatora, po prostu go rozpakowywujemy do Program Files albo w sumie gdziekolwiek), uruchamiamy go i pierwsze co robimy to zmieniamy język na polski (albo i nie – sam w sumie używam wersji angielskiej, ale screeny będą z wersji polskiej)

Teraz wchodzimy do ustawień…

Ukazuje nam się nowe okno, w którym mamy dostęp do wielu rzeczy zmieniających działanie programu – ustawienie większości z nich w sumie zależy od preferencji osobistych, tak więc zachęcam do poszperania w nich samemu. Przejdziemy teraz do kluczowej dla nas sprawy, czyli wyboru renderera. Z listy po lewej stronie wybieramy Strumień wyjścia i otrzymujemy :

To, który renderer wybierzemy, zależy od systemu – XP, Vista czy Windows 7.

• w przypadku Windows XP wybieramy albo Overlay Mixer, albo VMR7 renderless, albo VMR9 renderless – wyboru dokonujemy na podstawie „co działa najlepiej” i tego, czy potrzebujemy w naszym filmie napisów (o tym też później)
• w przypadku Windows Vista i Windows 7 wybieramy EVR jeśli nie potrzebujemy napisów lub EVR profil własny jeśli ich potrzebujemy – w przypadku tego drugiego w razie problemów z wydajnością (jednak tych być nie powinno) zalecam pogrzebanie ustawieniem Bufory EVR

Przenosimy się teraz do zakładki Filtry wewnętrzne…

i upewniamy się, że dwa nas najbardziej interesujące – H264/AVC (DXVA) oraz VC1 (DXVA) są zaznaczone. Niektóre z pozostałych możemy poodznaczać, jeśli chcemy, żeby zamiast filtrów wbudowanych w MPC-HC dekodowanie formatów obsługiwanych przez dane filtry przejmował filtr zewnętrzny (ja na przykład do AC3 i DTS wolę używać wspomnianego już AC3Filter, bo on pozwala na przekierowanie strumienia dźwiękowego bezpośrednio na interfejs S/PDIF). Następnie dwukrotnie klikamy na nazwę jednego z filtrów DXVA i otrzymujemy :

Jeśli w polu Karta graficzna pojawiła się nazwa naszej karty graficznej, oznacza to, że jest ona w stanie dekodować sprzętowo dany format. Ponadto, Ilość wątków dekodera powinna odpowiadać liczbie rdzeni w naszym procesorze – MPC-HC wykrywa jednak ją automatycznie, tak więc zmiana nie powinna być potrzebna. Pozostałe ustawienia służą do ewentualnej poprawy wydajności, jednak – szczerze mówiąc – sam ich nie ruszałem, tak więc nie wiem, co i w którą stronę można zmienić.

To już koniec ustawień – teraz klikamy OK i ładujemy nasz film w odtwarzaczu. Jeśli wszystko poszło pomyślnie, nie powinno być jakichkolwiek problemów z jego odtwarzaniem, a zużycie procesora nie powinno przekraczać 25%.

Napisy w DXVA MPC-HC

Jako że filtr DXVA musi być bezpośrednio podłączony do renderera, nie może być pomiędzy tymi dwoma rzeczami „pośredniczącego” filtra, np. filtra odpowiedzialnego za dodawanie napisów. Napisy można uzyskać jednak przez używanie renderera, który obsługuje dodawanie napisów sam w sobie – takimi są (dla XP) VMR9 renderless oraz (dla Visty i siódemki) EVR profil własny. Jeśli wybraliśmy jeden z tych rendererów oraz w katalogu z plikiem filmowym jest też plik z napisami, to zostanie on automatycznie załadowany i napisy będą wyświetlane. Jeśli się tak jednak nie stało, klikamy prawym przyciskiem myszy na obszar wyświetlania filmu i wybieramy Napisy, a następnie Włącz. Jeśli jednak napisy dalej się nie wyświetlają, upewnijmy się, że zostały załadowane, wybierając w głównym oknie programu menu Plik i pozycję Wczytaj napisy, a następnie wybierając odpowiedni plik z napisami.

Things to consider

Z moich własnych doświadczeń wynika, że do opisanych tutaj wybryków z DXVA o wiele lepiej nadaje się Windows Vista. Na Windows XP nie udało mi się uzyskać płynnego obrazu korzystając z renderera VMR9 renderless – stał się on „oglądalny” (tj. po prostu o szybkości 23.976fps) dopiero po wybraniu Overlay Mixer, który to nie umożliwia niestety wyświetlania napisów. Na Windows Vista jak i Windows 7 przy wybranym EVR profil własny żadnych problemów nie było. Możliwe jednak, że jest to kwestia konfiguracji mojego XP bądź sterowników do mojej karty graficznej.

Sprzętowe dekodowanie HD na Linuksie – karty Nvidia

Na Linuksie sprawa sprzętowego dekodowania jest zależna od producenta karty graficznej. W przypadku kart firmy Nvidia skorzystamy z opracowanego przez nią VDPAU, czyli Video Decoding and Presentation API for Unix, który odpowiada za obsługę funkcji PureVideo na nowszych kartach GeForce. Niestety, VDPAU wymaga nowszego sprzętu niż DXVA – najstarszymi kartami obsługującymi go są GeForce’y z serii 8, oprócz tych opartych na chipsecie G80, czyli 8800 Ultra, niektórych 8800 GTS  i 8800 GTX. Pełna (mniej więcej) lista kompatybilnych z VDPAU kart znajduje się tutaj.

Aby wykorzystywać możliwości naszej Nvidii do dekodowania HD na Linuksie, potrzebujemy :

• kompatybilnej z VDPAU karty,
• sterowników od Nvidii w wersji 180.37 lub nowszej,
• odtwarzacza obsługującego VDPAU i mającego współpracujące z VDPAU kodeki.

Zakładam, że użytkownik dwie pierwsze rzeczy już ma – uważam, że opis instalacji sterowników Nvidii jest tutaj zbędny, zwłaszcza, że większość dzisiejszych dystrybucji oferuje po prostu pakiety z tymi sterownikami, tak więc komplikacja tej procedury jest minimalna. Odtwarzaczami obsługującymi VDPAU są Xine i MPlayer. Używam tego drugiego, tak więc na nim będzie oparta dalsza część artykułu.

Rozpoczynamy od pobrania najnowszego źródła MPlayera z SVN :

$ svn co svn://svn.mplayerhq.hu/mplayer/trunk mplayer

Co spowoduje pobranie najnowszej wersji SVN do katalogu mplayer. Po wejściu do niego rozpoczynamy kompilację z paroma dodatkową flagą –enable-vdpau (reszta jest moimi własnymi wymaganiami, proszę je dostosować do własnych lub po prostu pominąć – configure w przypadku mplayera ma całkiem niezłą autodetekcję i powinien wykryć potrzebne dla danego sprzętu wtyczki audio/video) :

$ ./configure --enable-vdpau --disable-inet6 --disable-mencoder --disable-ossaudio --enable-tremor --extra-cflags="-march=core2 -O2 -pipe"
$ make
# make install

Jeśli configure wywala się w pewnym momencie (szczególnie jeśli narzuciliśmy budowanie czegoś flagą –enable), bądź nie jest budowana jakaś wtyczka – np. ALSA (to, jakie wtyczki będą zbudowane, możemy obejrzeć po zakończeniu skryptu configure), upewnijmy się, że mamy wszystkie biblioteki developerskie dla danego podsystemu.

Filmy HD odpalamy teraz z innymi parametrami – jako że VDPAU potrzebuje do działania kodeków napisanych specjalnie „pod” niego, nie możemy używać zwykłych, pochodzących z ffmpeg/libavcodec. W ten sposób :

• filmy zakodowane H264/AVC uruchamiamy z parametrami -vo vdpau -vc ffh264vdpau
• filmy zakodowane w VC-1 uruchamiamy z parametrami -vo vdpau -vc ffvc1vdpau

Nie ukrywajmy jednak, że odtwarzanie filmów w „gołym” mplayerze, wywołując go z konsoli, do zbyt wygodnych ani przyjemnych rzeczy nie należy. Jeśli używamy frontendu SMPlayer, to możemy mu powiedzieć, żeby jako domyślną wtyczkę wideo używał właśnie VDPAU – nie spowoduje to jakichkolwiek zawirowań w normalnych filmach „nie-HD”.

A jak tego dokonać? Prosto…najpierw wchodzimy do ustawień

I po ukazaniu się nowego okna w zakładce General wybieramy kartę Video i jako Output driver wybieramy właśnie vdpau, a następnie klikamy OK. Od teraz domyślnym sterownikiem wideo w SMPlayerze będzie właśnie on.

Musimy jednak zadbać, aby przy ładowaniu filmów HD ładowane były też kodeki VDPAU. W tym celu, podczas odtwarzania takowego, wchodzimy do View info and properties z menu Options (tego samego, co na poprzednim screenie), i tam wybieramy kartę Video codec.

Tam upewniamy się, że wybrany jest ffh264vdpau bądź ffvc1vdpau, zależnie od kodeka, w którym zakodowany jest film. Jeśli nie jest – dwukrotnie klikamy jego nazwę i wychodzimy z okna klikając OK.

Zwracam uwagę, że jeżeli posiadamy dystrybuję Arch Linux, to MPlayer’a z wkompilowaną obsługą VDPAU możemy zdobyć z AUR – kryje się on pod nazwą mplayer-vdpau i mplayer-vdpau-nogui. Jeśli używamy innej dystrybucji, to też warto poszukać już gotowych paczek z tym programem i VDPAU.

Sprzętowe dekodowanie HD na Linuksie – karty ATI

Ta sekcja artykułu jest niestety dopiero w przygotowaniu – pomimo usilnych starań nie udało mi się jeszcze zmusić kart ATI do współpracy z UVD2 i XvMC/XvBA. Sterowniki catalyst dla kart ATI na Linuksa też do najlepszych – mówiąc skromnie – nie należą. Samo ATI też o sprzętowym wsparciu dekodowania HD na Linuksie niewiele mówi.

Napiszę jednak jak je osiągnąć gdy tylko sam do tego dojdę. ;)

Pierdoły

A co u mnie? W sumie niewiele, pierwszy rok studiów mam jednak w stu procentach za sobą. Aktualnie cieszę się wakacjami i odpoczywam, ile mogę. Od połowy sierpnia zaczynam miesięczne praktyki w gorzowskim Volkswagenie jako…w sumie sam nie wiem kto. ;D Czyli wakacje w sumie mi się już za dwa tygodnie skończą. Nie ukrywajmy, jak się praktyki skończą to już będzie połowa września, zapisy i podobne farmazony, trzeba będzie do Wrocławia już wracać…ech. Szkoda, dobrze mi w domu – z drugiej strony, co za dużo, to niezdrowo. ;)

Matura 2009 – wyciek – matematyka rozszerzona

UPDATE 12.05.2009
Tak, te wycieki nie są prawdziwe. :) Gratulacje do tych bardziej trzeźwych, co się zorientowali, że takich pojęć na maturze nie ma – i nie ma żadnych szans, żeby się w ogóle pojawiły. Zadania te obejmują bardzo szeroki zakres materiału – szerszy niż nawet na jedno kolokwium. Takie zadania jednak pojawiają się na pierwszym roku studiów na Wydziale Elektroniki Politechniki Wrocławskiej – i zapewne wielu innych wyższych uczelniach technicznych. Tak więc przejrzyjcie je sobie i przeanalizujcie w miarę możliwości, jeśli macie aspiracje na polibudę. :)

A teraz sobie odpocznijcie i idźcie wcześnie spać zamiast szukać czegoś, czego na pewno nie znajdziecie. :)

Ten okrutny żart był zainspirowany żartem, który ktoś mi wyciął rok temu, jak sam pisałem maturę. :D

Aha, i jeszcze zamieszczam rozwiązania, które sam opracowałem dzisiaj po powrocie z uczelni – jeśli są jakieś błędy, przepraszam, jestem tylko człowiekiem – ale na pewno nikt nie będzie mówił, że „nie umiem tego zrobić, cieszę japę i zgrywam kozaka”. Rozwiązania są tutaj.

Szczerze życzę powodzenia. :)

Drodzy tegoroczni maturzyści!
Jako że mam parę „wtyków” w CKE, udało mi się dotrzeć do treści pytań z tegorocznego egzaminu maturalnego z matematyki na poziomie rozszerzonym. W tym roku jest ich mniej niż zwykle – mam jednak nadzieję, że poradzicie sobie z nimi bez problemów. Powodzenia!

Oto one :

1. Obliczyć zadaną całkę podwójną korzystając ze zmiennych biegunowych. Sporządzić rysunek obszaru całkowania.
, gdzie

2. Rozwiązać podane równanie różniczkowe.

3. Wykorzystując macierz przejścia z bazy standardowej odpowiedniej przestrzeni liniowej do bazy danej znaleźć współrzędne wektora v w tej bazie :

4. Narysować na płaszczyźnie zespolonej zbiór wszystkich liczb spełniających podany warunek :

5. Korzystając z różniczki funkcji obliczyć przybliżoną wartość wyrażenia .

6. Korzystając z lematu Burnside’a określić, na ile istotnie różnych sposobów można pokolorować kwadrat 3×3 (złożony z 9 kwadracików) za pomocą trzech kolorów, jeżeli dwa pokolorowania uznajemy za równoważne, gdy jedno z nich można otrzymać z drugiego przez obrót lub symetrię.

7. Korzystając z własności transformaty Fouriera wyznaczyć dla funkcji

Powodzenia!