Semestr zimowy 2002/03 - archiwum

• Projekt 1 (wstępny) (dla chętnych, odrobinę trudniejszy może być napisany w Pascalu,C, lub C++ ), termin : do ostatniego labu czyli pierwszy albo drugi tydzień stycznia 2003 ( plik pdf )
• Projekt 2:  Napisać program a w nim procedure która dla zadanej liczby naturalnej znajduje jej rozkład na możliwie małą liczbę kwadratów liczb naturalnych tzn dane jest n, znadujemy k _i , i=1,..p takie że n=k₁*k₁ +..k _p *k _p .  Program ma umożliwić wprowadzenie n z klawiatury a następnie wypisać na ekran n, p i liczby k_i czyli np  81=9*9 z p=1 a 10=1+9 z p=2- rozkład nie zawsze jest jednoznaczny. Termin do ostatniego labu  (pierwszy albo drugi tydzień stycznia 2003). W ramach testowania programu zastosować dla np 10000 losowych liczb naturalnych możliwie dużych - w Pascalu z zakresu longint). Jakie wychodzi największe p dla tych losowych liczb? Można tez przetestować np dla wszystkich liczb od  1000 do 10000 itp  (Wsk: najbardziej prosty - algorytm to przeszukanie wszystkich możliwych p-tek liczb - no bo największe p może być n, a największa liczba k _i - część całkowita z pierwiastka n oznaczmy ją na moment przez k <n   czyli co najwyżej   kⁿ <=n^(n/2) możliwości - oczywiście należy to zmodyfikować aby  nie sprawdzać  tych samych liczb k _i po kilka razy czy zaczynać od p=n  bo może być że np. n=81. Tak więc można wykorzystać ten algorytm w możliwie zmodyfikowanej formie - ale może ktoś wymyśli/znajdzie gdzieś inny algorytm? Trzeba jednak umieć uzasadnić dlaczego dany algorytm działa - sam fakt że działa dla jakichś liczb nie wystarcza ).
• Projekt 3: zaimplementować algorytm HeapSort - sortowania przez kopcowanie dla listy dwuwskaźnkowej. Wczytywać rekordy z pliku na dysku a następnie posortowane mają być zapisane na dysku w pliku o innej ustalonej nazwie.  Jako test posortować rekordy z kluczem typu integer i porządkiem '<=' z kluczami losowymi np. ze zbioru {-1000,..1000}, niech jeden program je wylosuje np. 20 albo 50 rekordów, i zapisze na dysk, drugi posortuje HeapSortem a trzeci wczyta z dysku i pokaże na ekranie, dodatkowo  niech podczas sortowania program drugi (HeapSort) wypisze klucze najpierw nie uporządkowane (wylosowane), potem wypisze kopiec (tylko klucze) a na końcu klucze posortowane.  (Ponieważ algorytm HeapSort jak i lista dwuwskaźnikowa  będą/były opisane szczegółowo na wykładzie więc wydaje się być ten projekt  najłatwiejszym - tylko że od wprowadzenia wskaźników do terminu oddania jest mało czasu: realnie ze 2-3 tygodnie - chyba że ktoś samodzielnie znajdzie potrzebne informacje).   
• Projekt 3' Projekt 3 ale HeapSort na tablicy wskaźników do rekordów - obniżona ilość pktów w stosunku do  tego co można dostać za pozostałe projekty.
  

1. zmiana hasła, wstępne zapoznanie sie ze środowskiem Turbo Pascala np 7.0, kompilacja możliwie prostych programów, instrukcje I/O write,witeln, read,realn, pętla 'For'. Program na sumowanie liczb od 1 do n dla zadanego n, ewentalnie wszystkich parzystych itp (16.X-pn,14.X-sr)
2. Kontynuacja: pętle while, repeat until, program na dzielenie modulo z wykorzystaniem tylko dodawania liczb calkowitych, program zapis dowolnej liczby calkowitej binarnie, wykorzystanie tego do programu na potęge liczby dodatniej a do potęgi k, a>0, k naturalna. Implementacja programów omówionych na ćwiczeniach tablicowych czy na wykładzie. (30.X-pn, 23.X-sr)
3. Funkcje i procedury, przerobienie części poprzednich programów na funkcje, parametry wywoływane przez wartość i zmienną. C.D. prostych algorytmów np dzielenie całkowite x div y kosztem rzędu log₂(x/y). (6XIśr,17XIpon)
4. Unit - przyklady , programy rekurencyjne przykłady - wieże Hanoi, symbol Newtona - wersja rekurencyjna i nierekurencyna, proste sortowanie np Bubblesort, SelectionSort itd wersja rekurencyjna i nie rekurencyjna. (20XI-sr,2XII-pon)
5. Kontynuacja dla grupy srodowej (4XII-sr).
6. Kontynacja programow rekurencyjnych. Obsługa plików - wczytać rekordy z pliku - posortować np Bubblesort - wypisać do tego samego albo innego pliku rekordy posortowane wg pola o typie porzadkowym. Ewentualnie to samo z wczytywaniem/wypisywaniem rekordów do pliku tekstowego typu text (16.XII-pon,18.XII-sr)
7. Ocena projektu zaliczającego.  Wskaźniki - implementacja stosu wskaźnikowa ewen. listy jedno czy dwukierunkowej.(styczeń - drugi tydzień i być może połowa zajęć w 1 tygodniu zajęć)
   

1. Interpolacja Lagrange'a na dowolnym  [a,b] i węzłach dowolnych, przy czym testować w szczególności dla węzłów równodległych i węzłów Czebyszewa dla funkcji 1/(1+x*x) na odcinku [-5,5] i sin(x) na [0, 2Pi]. Rysować na ekranie funkcję i wielomian interpolacyjny z węzłami i pktami przecięcia . (Węzły Czebyszewa to zera n-tego wielomianu Czebyszewa T _n  odpowiednio przesunięte i przeskalowane - n-ty wielomian Czebyszewa na [-1,1] jest zdefiniowany jako T_n(x)=cos(n*arccos(x)) i ma dokładnie n różnych zer : -1<x _i<1, które z tego wzoru od razu dają się policzyć).
   
2. Kwadratura trapezów złożona -czyli sumowanie wartości funkcji z wagami: testować funkcje różnej gładkości na  [0,1] dla których całka jest znana np sin(x), wielomiany niskich stopni np 1,2 czy x^p , p=k/2 k=1,2,3,4,5 itd, testować dla  h,h/2,h/4,h/8 dla h = 0.1 (h= 1/N gdzie N - ilość węzłów), porównywać błąd.Tzn obliczać całkę dla zadanego h i drukować bład między przybliżoną wartością całki a dokładna całką którą dla funkcji całkowych możemy obliczyć, przy okazji można obliczyć  i wypisać na ekranie iloraz błędu dla h przez błąd dla h/2.

1. Porównać algorytmy obliczania a*a-b*b = (a-b)*(a+b) pierwszy:  obliczamy a*a i b*b i odejmujemy, drugi:obliczamy a+b i a-b i mnożymy.  Zaprogramować oba i znaleźć takie liczby a,b aby widać było lepszość jednego z nichw arytmetyce fl. W raporcie zamieścic te liczby a i b i wyniki obu algorytmów w tabelce, wyniki w podwójnej precyzji typu double (w pascalu lub C - ta sama nazwa) - (30.X.2002).
2. Generować  macierze A_N=(a_ij)i,j=1..N dla N=1..300 o elementach losowych a_ij z [0,1] i następnie obliczać  normę Frobeniusa ||A_N||_F .  Raport:wykres tej normy jako funkcji wymiaru tj. F(N)= ||A_N||_F   . (13.XI.2002) Rozwiązanie: powinna wyjść  z małymi odchyleniami punkty na prostej:( n,n*3 ^-0.5)
3. Dla zadanego wektora u=(u₁,...,u₄₀₀) ^T w R⁴⁰⁰ i u^_i =(-1) ⁱ  dla i=1,..,400, napisać program który umożliwia dla dowolnego wektora z  R⁴⁰⁰ znalezienie jego obrazu przy przeksztalceniu Housholdera H=Id - 2w*w ^T takim  że przekształca u na a* e ^₁ gdzie a =-||u || ₂  a  e ^₁ - wersor. Jako raport podać 3 liczby: normy ||H|| _p dla p=1 i nieskończoność i normę drugą He₃ (wektora który jest obrazem wersora e ₃ przy przekształceniu H). Wszystko wykonać w arytmetyce double. Napisać jak państwo poradzili sobie z umieszczeniem w pamieci  H - tj. jak państwo zaimplementowali H - krótko w kilku zdaniach. (11.XII.2002)
4. Dla macierzy A= (k₁k₂) ,wymiaru 4x2 o pierwszej kolumnie, k₁=(1,1,1,1)^T i drugiej k₂=(0,1,2,3)^T napisać program  rozwiazujacy L.Z.N.K. (||Ax-f||₂=min||A y -f|| ₂) z prawą strona f=(f0,f1,f2,f3) ^T  dla fi - czterech losowych liczb z odcinka [0,1]. Ponieważ rozwiązanie to x =(x1,x2) ^T to jako raport narysować wykres x1+x2*t na odcinku [-1,4] zaznaczając równocześnie pkty (i,fi), i=0,1,2,3. Proszę zauważyć, że powyższe L.Z.N.K. daje nam wzór na prostą taką że mamy możliwie najmniejsze   |x1+x2*0 -f0|² + ...+  |x1+x2*3 -f3|² czyli ta prosta będzie przechodziła 'możliwie blisko ' pktów (i,fi), i=0,1,2,3. (18.XII.2002)
5. Napisać program który oblicza wielomian interpolujący zadaną funkcję f w 2 punktach: 0 i 1 z podwójną krotnością w 0 i pojedyńczą w 1, tzn tak żę wielomian w który otrzymamy spełnia w (i)= f(i), i=0,1; i w'(0)=f' (0) . Jako raport: na jednym obrazie wykres sin(4*x) i w dla tej funkcji na odcinku [-1,2] (y w zakresie [-2,2]). Zaznaczyć który wykres jest wiel. interp. a który funkcji.   (15.I.2003 - ostatnie zajęcia)