Oblicz sumę Σ{i=0}n.2^i dla różnych n. Czy to się różni od Σ{j=0}n.2^j?
Udowodnij przez indukcję matematyczną, że Σ{i=0}n.2^i=2^(n+1)-1.
Ile to jest Σ{i=1}0.2^i? a ile Π{i=1}0.2^i?
Dyskusja programu suma=0;for(i=1;i≤n;i++) suma+=a[i]; i analogicznego dla mnożenia.
Oblicz sumy Σ{i=0}3.Σ{j=0}4.2^(i+j) oraz Σ{j=0}4.Σ{i=0}3.2^(i+j)
Czy tak samo można zamienić sumowania w Σ{n=1}3.Σ{j=0}n.2^j

Dane zbiory A={1,2,3,4}, B={2,4,6}, C={3,4,5,6}. Jakie są ich moce? Oblicz sumy, przekroje, różnice, różnice symetryczne.
Indeksowane rodziny zbiorów, działania na nich. Wyznacz iloczyn kartezjański {A,B,C}x{1,2,3,4} i {1,2,3,4}x{A,B,C}.

Ile jest grafów nieskierowanych o wierzchołkach {a,b,c}? Narysuj je wszystkie.
Izomorfizm grafów, sprawdź, że jest to relacja równoważności, które z narysowanych grafów są izomorficzne?
Ile jest grafów skierowanych o wierzchołkach {a,b,c}? (512, a bez pętelek 64).
Izomorfizm grafów skierowanych. Narysuj wszystkie grafy o trzech wierzchołkach z dokładnością do izomorfizmu (powinno być 16 klas).

Zadania związane z relacjami.

Złożenia relacji zapisanych w postaci tabelarycznej.
Złączenia relacji, również niebinarnych.
Zapis relacji binarnej w postaci grafu skierowanego.
Relacja równoważności, przykład: izomorfizm grafów, przykłady klas równoważności.
Zbiór {1,2,3,...,30} i klasy relacji przystawania modulo 2,3,6.

Wypisz 10 kolejnych słów ze zbioru {a,b,c}* w porządku leksykograficznym i kanonicznym.

Wykonaj operacje dodawania, odejmowania i mnożenia liczb zapisanych w innych układach liczenia.
Zamień liczby zapisane w układzie dziesiętnym na dwójkowy, ósemkowy i szestnastkowy. Zamień liczby zapisane w układach 2,8,16. Ile cyfr mogą mieć liczby po zamianie na inny układ liczenia?
Wykonaj operacje dodawania i mnożenia liczb zapisanych w układzie uzupełnieniowym U2. Dla celów uproszczenia zadania przyjmujemy reprezentację 8-bitową liczb całkowitych [-128..127].
Relacja równoważności modulo 16 (4-bity), działania na reprezentantach klas.

Algorytm wyszukiwania fałszywej monety. Drzewa binarnych wyszukiwań: wstawianie, wypisywanie w porządku, drzewa zrównoważone.

Zasada szufladkowa Dirichleta, przykład: dla 5 cyfr istnieją dwa różne zestawy z tą samą sumą.

Zasada włączania/wyłączania, liczby pierwsze do 100 (podzielne przez 2,3,5,7 oraz reszta).

Ile numerów rejestracyjnych jest podobnych do GSP1234, ile do GK12345, ile do GKA12X3 gdzie może ale nie musi wystąpić jedna litera w drugiej części numeru?
Ile jest ciagów 4-bitowych dla których x1=0, albo x1=1, albo x0=x1, albo x1=1 i x1=x0, albo x1=1, x2=0 i x1=x2?
Ile jest funkcji ze zbioru {a,b,c,d} do zbioru {X,Y,Z}? Ile z nich spełnia f(a)=f(b), ile f(a)!=f(b)?
Ile jest monotonicznych ciągów bitów długości 32?

Permutacje (bez powtórzeń): oblicz złożenia i permutacje odwrotne do podanych. Ile permutacji zbioru {1,2,3,4,5} spełnia σ(1)=2? a ile σ(1)=2 oraz σ(3)=2? Ile permutacji zbioru {1,2,3,4,5} spełnia σ(1)<σ(2)? a ile σ(2)<σ(1)?
Ile jest sposobów ułożenia obrazka 3x4 z 12 kostek, które można dowolnie przestawiać i obracać?
Permutacje z powtórzeniami: ile różnych słów można ułożyć z liter WÓLKA? WALKA? KALKA?
Kombinacje (bez powtórzeń = podzbiory): ile jest podzbiorów w {a,b,c}?

Liczba podzbiorów, funkcje charakterystyczne. Symbol Newtona. Dwumian Newtona. Przykłady liczbowe: Σⁿ_k=0 n po k=2ⁿ, Σⁿ_k=0(-1)^k n po k=0 dla n>0. Funkcja rosnąca w pierwszej połowie, malejąca w drugiej.
Na ile sposobów można ułożyć 13 kart tak by as i dama były obok siebie? A na ile sposobów, by as był bardziej z lewej niż dama (niekoniecznie obok siebie)?
Podziały uporządkowane i nieuporządkowane. Liczba ustawień trójkami, liczba podziałów na trójki.
Ile jest funkcji monotonicznych ze zbioru {1,..,5} do zbioru {1,..,10}? A ile ściśle monotonicznych?
Liczba funkcji niemalejących n->k (n+k-1 po n), liczba rozwiązań Σ^k_i=1 a_i=n.
Na ile sposobów można wybrać trzy liczby ze zbioru 1--60? tak by suma była parzysta? nieparzysta?
Generowanie podzbiorów (kolejne liczby, kod Graya), k-elementowych, wielozbiorów, permutacji.

Sprawdzić czy zachodzą tożsamości w algebrze Boole'a: p+qr=q+pr? (p⊕q)⊕p=p⊕q?
Zapisać w tabelce funkcję (x+¬y)·(y+¬z).
Wyliczyć tę funkcję dla wektorów x=11001101, y=01000101, z=10010010, dla zbiorów X={1,2,3,6}, Y={2,5,6,8}, Z={1,3,4,7,8}
Liczby naturalne jako ciągi bitów (operacje niskopoziomowe w jęz. C).
Ile jest funkcji boolowskich Bⁿ→B? Wypisać wszystkie dla n=2.
Analiza operatorów nand i nor, generują wszystkie inne.
Koniunktywna i dyzjunktywna postać normalna funkcji boolowskich.

Algorytm Euklidesa, wersja rekurencyjna NWD(a,b)=NWD(b,a%b), NWD(a,0)=a. Złożoność algorytmu (logarytmiczna czyli liczba cyfr binarnych argumentu). NWD(a,b) jest kombinacją liniową a i b. Jeśli jest równy 1 (liczby względnie pierwsze), to można obliczać odwrotności. Obliczanie odwrotności modularnych wykonuje się rozszerzonym algorytmem Euklidesa:

		p,q,r,s=1,0,0,1
		while b:a,b,p,q,r,s=b,a%b,r,s,p-a/b·r,q-a/b·s
	

Rozwiązania równań w arytmetyce modularnej.
W Z₁₇ każde równanie ma rozwiązanie, np. 8*x=2 mod 17 rozwiązujemy znajdując najpierw 8^-1=-2=15 mod 17 i dalej x=2*8^-1=2*15=13 mod 17.
W Z₁₄ równanie 6*x=9 mod 14 nie ma rozwiązania bo 6*x jest zawsze parzyste a 9+14*coś zawsze nieparzyste. Z kolei równanie 6*x=2+14*coś rozwiązujemy dzieląc przez 2, 3*x=1+7*coś rozwiązujemy jednoznacznie jak wyżej, x=5, wracając do oryginalnego równania rozwiązania są dwa, x=5,12.

Chińskie twierdzenie o resztach, np. a=3 mod 5 i a=4 mod 6 rozwiązujemy tylko gdy moduły spełniają NWD(6,5)=1, wówczas istnieje kombinacja 1=p·6+q·5 i rozwiązaniem jest a=3·p·6+4·q·5=3·1·6+4·(-1)·5=-2=28 mod 30. Twierdzenie pozwala znaleźć nietrywialne pierwiastki z jedynki, np. skoro 15=3·5, to możemy rozwiązywać równania a=1 mod 3 i a=-1 mod 5 otrzymując a=4 mod 15 i a²=1 mod 15.

Test Fermata polega na podnoszeniu do potęgi a^n-1 mod n. Dla liczby pierwszej wynik musi być 1, jeśli nie jest, liczba nie jest pierwsza. Wykonaliśmy kilka testów np. 4¹⁴ i 3¹⁴ mod 15. Elementem zadania jest szybkie potęgowanie czyli wykorzystanie wzorów aⁿ=(a²)^n/2 dla parzystych wykładników oraz aⁿ=a^n-1*a dla nieparzystych. Mnożenie jest modularne, po każdym działaniu oblicza się resztę modulo.

Rekurencja liniowa (ciąg Fibonacciego). Rozwiązanie dokładne dla definicji f(0)=1, f(1)=1, f(n+2)=3·f(n+1)-f(n) (postulowane rozwiązanie f(n)=xⁿ, stąd równanie kwadratowe, pierwiastki i kombinacja liniowa wynikająca z warunków początkowych).

Rekurencyjne definicje funkcji silnia(n), NWD(a,b), potęga(a,n), newton(n,k).
Metoda podstawiania dla definicji M(n)=2·M(n/2)+n i podobnych (podział i scalanie). Wynik dokładny dla n=2^k.
Algorytm szybkiego mnożenia: podział bitów każdej z liczb na dwie grupy x = x1 x2, y = y1 y2 a następnie trzy mnożenia, x1·y1, x2·y2 oraz (x1+x2)·(y1+y2) pozwalające wyznaczyć x1·y2+x2·y1, iloczyn składa się z tych trzech grup bitów. Oszacowanie złożoności M(n)=3·M(n/2)+n, M(1)=1 co prowadzi do złożoności wielomianowej M=O(n^{log 3}) lepszej niż kwadratowa.
Trzy wersje w zależności od potęgi przy scalaniu i proporcji kosztów podziału.

Definicje rekurencyjne funkcji dla drzew binarnych. Przeszukiwanie wszerz i wgłąb.
Definicje rekurencyjne algorytmów przeszukiwania. Notacja polska (beznawiasowa) prosta i odwrotna (RPN), wzajemna zamiana napisów
/ * + a b / c d - e + f g
((a+b)*(c/d))/(e-(f+g))
a b + c d / * e f g + - /

Grafy nieskierowane, sposoby reprezentacji. Algorytm przeszukiwania wgłąb i wszerz, drzewa spinające graf.
Ścieżki i cykle Eulera, Hamiltona. Klasy grafów, graf pełny (ma cykl Hamiltona, nie ma cyklu Eulera gdy n parzyste), graf pełny dwudzielny (nie ma cyklu Hamiltona gdy liczności dwu klas wierzchołków są różne, nie ma cyklu Eulera gdy choć jedna z klas ma nieparzystą liczbę wierzchołków).
Przykłady grafów.

Grafy skierowane, sposoby reprezentacji. Algorytm przeszukiwania wgłąb i wszerz.
Algorytm Dijkstry szukania najkrótszej ścieżki w grafie.
Przykłady grafów.