Programista_73.pdf

(13039 KB) Pobierz
ZRÓWNOLEGLANIE OBLICZEŃ W PRZETWARZANIU OBRAZÓW · STREFA CTF
Index: 285358
www
•
programistamag
•
pl
Magazyn
programistów
i
liderów
zespołów
IT
6
/
2018
(
73
)
lipiec/sierpień
Cena 23,90 zł (w tym VAT 5%)
KWANTOWY ALGORYTM
WYSZUKIWANIA
CO DZIEJE SIĘ POD MASKĄ?
RZUT OKIEM NA JĘZYK D
MAŁE JEST PIĘKNE – ARM
CORTEX-M0
EDYTORIAL
Qbitowy świat
Poprzednie wydanie zdominowały mniej techniczne
teksty. Uznaliśmy, że choć jeden wakacyjny numer
powinien być lżejszy w odbiorze. W końcu to czas
odpoczynku i relaksu, a zaokienne temperatury zu-
pełnie nie nastrajają do pracy. W tym numerze nato-
miast postanowiliśmy powrócić do naszej standardo-
wej formy, wypełniając je praktycznymi artykułami.
Choć komputerów kwantowych nie mamy
na biurkach, w tym miesiącu zapraszamy na po-
czątek do zapoznania się z kwantową przyszłością
informatyki pod postacią okładkowego artykułu
pt. „Q# – czas na kwantowe języki programowania”
autorstwa Marka Sawerwaina.
Mimo panujących za oknami upałów mamy
nadzieję, że znajdziecie odrobinę energii, by spró-
bować wykorzystać w praktyce wiedzę zawartą w tek-
ście opowiadającym o tym, jak nowoczesne proceso-
ry wykonują współczesny wysokopoziomowy kod.
Zainteresowani? To zapraszamy do lektury artykułu
Wojtka Sury „Co dzieje się pod maską?”.
Wielu z nas ma w głowach setki różnych pomy-
słów: wiadomo – programiści są w większości ludź-
mi kreatywnymi. Często są to pomysły z pogranicza
majsterkowania, elektroniki i komputerów, a do ich
realizacji potrzebujemy określonego mikrokontrole-
ra. Rodzajów układów jest wiele, różnią się wszyst-
kim, począwszy od ilości rdzeni, instrukcji, na wiel-
kości kończąc. Tym razem Rafał Kozik zaprasza do
zapoznania się z najmniejszym układem ARM Cor-
tex-M0 w swoim artykule „Małe jest piękne – ARM
Cortex-M0”.
Na koniec mała niespodzianka. Nasz redakcyj-
ny specjalista od C++, Paweł "KrzaQ" Zakrzewski,
tym razem zaprezentuje wybrane funkcjonalności
innego języka programowania – i nie będą to dy-
wagacje czysto teoretyczne. O jakim języku mowa?
Wystarczy tylko „Rzut okiem na język D”, by wszyst-
ko było jasne.
Pozostaje nam życzyć niższych temperatur,
więcej wolnego czasu i spokojnego wypoczynku.
Z naszym magazynem w ręce oczywiście :)
Miłej lektury!
Mariusz „maryush” Witkowski
JĘZYKI PROGRAMOWANIA
Q# – czas na kwantowe języki programowania
Marek Sawerwain
4
12
Rzut okiem na język D
Paweł "KrzaQ" Zakrzewski
PROGRAMOWANIE SYSTEMÓW OSADZONYCH
Małe jest piękne – ARM Cortex-M0
Rafał Kozik
18
PROGRAMOWANIE SYSTEMOWE
Co dzieje się pod maską? Zaglądamy do disassembly programów w C++
Wojciech Sura
28
PROGRAMOWANIE GRAFIKI
Zrównoleglanie obliczeń w przetwarzaniu obrazów
Maciej Szymkowski
44
INŻYNIERIA OPROGRAMOWANIA
Kwantowy algorytm wyszukiwania.
Przykład wykorzystania metody brute force
Andrzej Klejnberg
54
STREFA CTF
Google CTF 2018 (Quals) – Sandbox Compat
Ariel "ariel" Wasteskeen
56
64
Midnight Sun CTF 2018 – Badchair
Jarosław Jedynak
KLUB DOBREJ KSIĄŻKI
Nowoczesna kryptografia. Praktyczne wprowadzenie do szyfrowania
Mariusz „maryush” Witkowski
70
reklama
JĘZYKI PROGRAMOWANIA
Q# – czas na kwantowe
języki programowania
W jakim kierunku rozwijać się będą języki programowania? Pytanie wbrew po-
zorom jest dość trudne i możemy wskazać raczej tylko tendencje, jak np. wzra-
stającą popularność języków funkcyjnych lub dalsze zwiększanie roli języków
skryptowych czy interpretowanych. Jednakże powinniśmy też wziąć pod uwagę
fakt, iż od dłuższego czasu rozwijają się nowe podejścia do obliczeń, a takim no-
wym modelem obliczeniowym, jaki warto wymienić, są obliczenia kwantowe.
M
inie jeszcze sporo czasu, zanim na naszych biurkach za-
goszczą komputery w pełni kwantowe działające w tem-
peraturze pokojowej (ale to może stać się szybciej, niż
może nam się wydawać), jednak już dziś mamy kilka eksperymen-
talnych instalacji maszyn kwantowych, gdzie można wykony-
wać kwantowe algorytmy, testować wybrane protokoły. Działają
w temperaturze bliskiej zera absolutnego (zatem zwykła zamra-
żarka niestety nie wystarczy ;-)). Tworzone są także języki progra-
mowania dla przyszłych maszyn kwantowych, a jednym z nich
jest Q#. Choć nie mamy jeszcze dostępu do wydajnych kompu-
terów kwantowych, to jednakże można zastosować symulatory,
aby rozpocząć tworzenie programów, które co prawda będą tylko
symulowane, ale można już teraz zacząć uczyć się kwantowego
modelu obliczeniowego. Ma on kilka niezwykłych właściwości,
które będą w przyszłości stanowić o jego sile. W tym artykule
chcemy pokazać wybrane przykłady obliczeń kwantowych. Natu-
ralnie jest to bardzo skrótowe przedstawienie wybranych pojęć,
jednak bez większych kłopotów znajdziemy w Internecie wiele
dodatkowych informacji, zatem już teraz zachęcamy do dalszych
poszukiwań.
Rysunek 1. Qubit jako sfera Blocha
mnianym rysunku przedstawiono dwa bazowe przypadki stanów:
zero oraz jeden. Mamy też znaczone dwa inne stany będące tzw.
superpozycją stanów zero oraz jeden.
Kolejna istotna konstrukcja to rejestr kwantowy złożony
z n qubitów:
MODEL OBLICZEŃ KWANTOWYCH
W PIGUŁCE
Podstawy modelu obliczeń kwantowych opierają się na wektorach
i macierzach. Jednak nie będziemy tu wprowadzać wszystkich
podstawowych definicji. Zaczniemy od podstawowej jednostki in-
formacji kwantowej, czyli qubitu:
Zdefiniowaliśmy dwa podstawowe stany: zero oraz jeden. Stosuje-
my też notację Diraca, tj. zero zapisujemy jako
. Qubit o niezna-
nym stanie
to suma dwóch podstawowych stanów zera oraz
jedynki (wektory te stanowią też tzw. standardową bazę oblicze-
niową). Wartości alfa oraz beta to liczby zespolone i zakłada się, iż
kwadrat ich modułów sumuje się do jedności. Jest to tzw. inter-
pretacja probabilistyczna, ale same wartości alfa i beta nazywamy
amplitudami prawdopodobieństwa.
Na Rysunku 1 przedstawiono wizualizację qubitu za pomocą
sfery Blocha, bowiem choć mamy dwa wektory zero oraz jeden,
to qubit można ukazać jako trajektorię na sferze Blocha. Na wspo-
Poszczególne qubity są połączone za pomocą operacji iloczynu
tensorowego, ale istotniejszym jest fakt, ile informacji można zgro-
madzić w rejestrze kwantowym. Jeśli mamy n qubitów, to możemy
zapisać
klasycznej informacji w qubicie. Inaczej mówiąc, mamy
wykładniczo więcej informacji w qubitach niż w klasycznych no-
śnikach informacji. Trzeba także dodać, iż nie zawsze można sto-
sować iloczyny tensorowe do zapisu stanu rejestru kwantowego.
Występują tzw. stany splątane, które nie rozkładają się na iloczyn
tensorowy, np. dwóch qubitów. Stany splątane są bardzo ważnym
elementem informatyki kwantowej, np. pozwalają na realizację te-
leportacji kwantowej.
W naszym krótkim wprowadzeniu opiszemy jeszcze operację
unitarną. Przetwarzanie rejestru kwantowego realizujemy w taki
sposób:
co oznacza, iż stan kwantowy psi zero został za pomocą operacji
unitarnej U przekształcony do stanu psi jeden. I wbrew pozorom,
z punktu widzenia matematyki, jest to bardzo prosta operacja,
gdyż U jest macierzą unitarną, wystarczy zatem przemnożyć wek-
tor przez macierz, aby otrzymać nowy wektor. Upraszczając, bram-
ki kwantowe reprezentują różne operacje unitarne.
4
/
6 . 2018 . (73)
/

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin