Semestr zimowy 2003/04

1. Wstęp do informatyki (ćwiczenia do wykładu prof. L. Plaskoty)
2. Metody numeryczne (ćwiczenia do wykładu prof. K. Moszyński)
   

• 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: prosty  notes w trybie tekstowym. Maja Panstwo miec dane osob z telefonami, imionami i nazwiskami i adresami  na dysku w pliku tekstowym (tak aby mozna bylo niezaleznie ten plik edytowac). Program ma umożlić wczytanie/zapisywanie danych do/z tego pliku, w trybie tekstowym wypisanie listy nazwisk w porzadku alfabetycznym albo posortowanych wg imienia, następnie możliwość oglądania danych dla danego nazwiska (lub imienia), edycje danych, dodawanie/usuwanie  danych w pliku na dysku . Wyszukiwanie rekordu o zadanym nazwisku.  W zakres projektu wchodzi  też zaprojektowanie jak ma ten program szczegółowo działać. Nie ma w tym projekcie żadnych trudności algorytmicznych poza ewentualnym sortowaniem (można zastosować możliwie prosty algorytm sortowania o koszcie kwadratowym jak selection-sort) ale może to być dość żmudne - trzeba zadbać o wiele szczegółów: jaką strukturę danych wybrać - jak  wypisywać na ekranie listę co zrobić jak się nazwiska nie zmieszczą na ekranie  itp. Ewentualne uproszczenia np trzymanie danych nie w pliku tekstowym a pliku rekordów będzie skutkowało obniżeniem ilości pktów.
• Projekt 3: Zaimplementować algorytm HeapSort - sortowania przez kopcowanie dla listy dwuwskaźnikowej. 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ą 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).   Uwaga! Ponieważ w grudniu na wykładzie nie było listy 2-wskaźnikowej to można zaimplementować algorytm na tablicy wskaźników -> Projekt 3' poniżej.
• Projekt 3': Zaimplementować algorytm HeapSort - sortowania przez kopcowanie dla rekordów trzymanych w tablicy wskaźników, pozostałe wymagania jak w Projekcie 3. (Tzn wpisujemy adresy wczytanych rekordów do tablicy - i działamy na tej tablicy  - praktycznie ta wersja HeapSortu niewiele sie różni od wersji tablicowej a nie musimy przepisywać potencjalnie dużych rekordów)

• wstępne zapoznanie sie ze środowskiem Turbo Pascala lub Free pascala, 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 Pętle while, repeat until, program na dzielenie modulo z wykorzystaniem tylko dodawania liczb calkowitych, program zapis dowolnej liczby calkowitej binarnie, itp  Nowe typy zmiennych jak tablice. (15X)
• Kontynuacja.  Procedury, funkcje. (22X)
•  Rekordy, Sprytne potęgowanie - z wykorzystanie rozkładu binarnego potęgi, podobne dzielenie całkowite (przy założeniu że mamy dostępne operacje dodawania całk., mn, dziel. oraz brania reszty z dzielenia  przez 2), algorytm Hornera - liczenie wartości wiel. w pkcie i ewentualnie znajdowanie unormowanych pochodnych w pkcie.  Unity np. unit z rekordem imitujacym liczby zespolone i dzialaniami na tych liczbach jak dodawanie, mnozenie, modul, odwrotnosc itp, rekurencja: programy rekurencyjne na: silnia, wieże Hanoi, dwumian Newtona - ich wersje nierekurencyjne. (5,12XI)
  
• Kontynuacja. Ewent. sortowanie o koszcie kwadratowym - bubble sort, insort itp(26XI).
• Pliki, stos, kolejka. Listy jedno-dwukierunkowe, wskaźniki.
• Zaliczenie zadań komputerowych (14 I 2004)

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))  ma dokładnie n różnych zer : -1<x _i<1, które z tego wzoru od razu dają się policzyć). Rysowanie na ekranie może być za pomocą jakiegoś narzędzia np gnuplota pod linuxem.  (Czyli zgrać wyniki do pliku i gnuplotem wyświetlić.)
   
2.  Kwadratura trapezów złożona : 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.