LO3

02.02.2012 - Jakub Łopuszański
Trudność

RSA for dummies

 

29.01.2010
TrudnośćTrudność

Wyszukiwanie wzorca a wielomiany

Dzisiaj na zajęciach wróciliśmy do problemu wyszukiwania wzorca, tym razem poznając pewne bardzo dobre w praktyce algorytmy oraz drogę rozumowania potrzebną do ich wymyślenia.

Najpierw zauważyliśmy, że porównywanie dwóch dużych obiektów, można rozpocząć od porównania wartości ich funkcji hashujących. Powiedzieliśmy sobie, że funkcje hashujące występują w informatyce w dwóch kontekstach znaczeniowych:

11.12.2009
TrudnośćTrudność

Wyszukiwanie wzorca

Przypomnieliśmy sobie co to jest automat skończony oraz w jaki sposób można automat skończony może pomóc w znajdowaniu wystąpień wzorca.

Dla wzorca $ p=p_0 \ldots p_{m-1} $, automat taki ma $ m+1 $ stanów $ q_0,\ldots,q_m $.

04.12.2009
Trudność

Algorytmy grafowe, tekstowe i granica

Poznaliśmy pojęcie automatu skończonego, czyli czegoś co składa się z:

  • $ \Sigma $, czyli alfabetu, czyli skończonego zbioru znaczków jakie mogą się pojawić na drodze robaczka
  • $ Q $, czyli stanów, czyli skończonego zbioru pewnych abstrakcyjnych konfiguracji pamięci robaczka
  • $ q_0 $, czyli stanu początkowego, $ q_0 \in Q $ z jakim rodzi się robaczek
  • $ F $, czyli stanów akceptujących, $ F \subset Q $
  • $ \delta $, czyli funkcji przejścia, $ \delta : F \times Q \rightarrow Q $, opisującej proces kognitywny robaczka, czyli w jaki sposób życie wpływa na jego wi
27.11.2009
Trudność

Liczby pierwsze

Analizując złożoność sita Erastotenesa, natrafiliśmy na dość częstego bohatera: liczby harmoniczne:

$$H_k = \sum _ {i=1} k \frac {1}{i} $$
Powiedzieliśmy sobie, że zachodzi $ H_n \in \Theta(\lg n) $, co da się pokazać prosto dla n będących potęgami dwójki, a następnie dla pozostałych korzystając z tego że $ H_n $ jest monotoniczną funkcją $ n $:

20.11.2009
Trudność

gcd

Omówiliśmy sobie Algorytm Euklidesa i parę jego zastosowań. Polecam gorąco artykuł Damiana Rusaka.

13.11.2009
Trudność

UnionFind

Na zajęciach poznaliśmy też inną struktruę danych, która posiada "explicit layout", jaką jest union-find, zaimplementowany jako pojedyncza tablica.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int u[N];
int find(int x);
bool unite(int x,int y){
  x=find(x);
  y=find(y);
  if(x==y)return false;
  if(u[x]<u[y]){
    u[y]=x;
  }else if(u[y]<u[x]){
    u[x]=y;
  }else{
    u[x]=y;
    --u[y];
  }
  return true;
}
memset(u,-1,sizeof(u));

13.11.2009
Trudność

Kopiec

Dzisiaj na zajęciach opowiedzieliśmy sobie o tym jak zadbać o porządek w kopcu i jak zorganizować sobie strukturę danych w pamięci, aby nie potrzebować wskaźników. Idea była taka, żeby trzymać wszystko w tablicy:

1
2
3
const int N=1000;
typedef int T;
T heap[N+1];
i ponumerować wierzchołki drzewa z góry na dół od lewej do prawej, począwszy od 1 a na N skończywszy. Tu może dygresja, żeby pamiętać o tym, iż albo tablica musi mieć o jeden element więcej, albo (jak komuś żal RAMu) należy przesunąć wskaźnik o jeden.

11.11.2009
Trudność

Element k-ty co do wielkości

Jednym z trudnych do napisania samemu algorytmów dostępnych w STLu, jest nth_element. Funkcja z grubsza służy do tego, aby wyszukać k-ty co do wielkości element w podanej tablicy i o tym problemie traktuje niniejszy artykulik.

Zastanówmy się, jak znaleźć ów k-ty element bez korzystania z tej funkcji?

Pomysł 1. sort

Pomysł, który wielu osobom się narzuca, to posortować tablicę i zwrócić jej (n-k)-ty element. Rozwiązanie proste i poprawne, ale o złożoności $ \Theta(n \lg n) $, gdzie n to rozmiar tablicy.

10.11.2009
TrudnośćTrudnośćTrudność

Mapowanie stringów na inne obiektu

Z pewnych względów nie mogłem odpowiedzieć na to pytanie przed CEPCem, ale teraz postaram się zrewanżować.

W niektórych zadaniach chcielibyśmy przyporządkować napisom jakieś obiekty. Czyli chcielibyśmy mieć coś co w STLu nazwalibyśmy map<string,T> gdzie T to typ obiektów jakie chcemy przyporządkować stringom.

10.11.2009
Trudność

Grafy -- teoria

Graf, to pojęcie, które jest fundamentalne dla zrozumienia większości olimpijskich problemów i ich rozwiązań. Definicję na pewno znajdziecie w sieci, a większość opracowań zadań używa go bez zbędnych wyjaśnień.

10.11.2009
Trudność

Grafy -- praktyka

Graf, to pojęcie, które jest fundamentalne dla wymyślenia rozwiązania i zaimplementowania większości olimpijskich zadań.

Jak wiemy z części teoretycznej graf powinien mieć zbiór wierzchołków i zbiór krawędzi. W praktyce jednak, przyjmujemy, że wierzchołki nazywają się od 0 do n-1, i nie musimy nigdzie pamiętać ich zbioru, a jedynie pamiętać, że jest ich n.

10.11.2009

Startowanie w zawodach

Przyjdzie Wam zapewne nie raz startować w zawodach o formule "ACMowej", np. w Dolnośląskich Zawodach w Programowaniu Zespołowym. W najbliższy weekend, odbywają się na Uniwersytecie Wrocławskim najbardziej prestiżowe zawody w tej części Europy, czyli właśnie ACM ICPC CEPC. Parę osób od nas zostało zaproszonych poza konkursem, aby poczuć ducha tej imprezy.

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com