Semestr letni 2003/2004

1. Wstęp do informatyki
2. Równania różniczkowe z labem 
   

1. listy: zaprogramowanie zadań z egzaminu, InsertSort na tablicy ewentualnie  BubbleSort i SelectionSort - 18/02/2004
2. MergeSort na liście 1-wskaźnikowej i MergeSort tablicowy- wersje  rekurencyjna i nierekurencyjna, ewentualnie QuickSort - 25/02/2004
3. Dokończenie MergeSortu. QuickSort rekurencyjny na tablicy, Randomized QuickSort - porównywanie czasu działania dla losowych tablic - wypisywanie ilości porównań i czasu rzeczywistego. Sortowanie kubełkowe - 11/03/2004
4. BST: dodawanie, usuwanie z listy, wypisywanie postaci liniowej, badanie wysokości drzewa,   - 18/03/2004.
5. dokończenie algorytmów z poprzednich labów,  procedura ktora dla zadanego węzła drzewa BST dokonuje rotacje w lewo albo prawo (o ile to możliwe) , sortowanei kubełkowe połaczone z MergeSortem - sortujemy kubełkowo nazwiska względem pierwszej litery alfabetu tworząc jednokierunkowe listy  dla każdej litery (wskaźniki do początków list trzymamy np w tablicy  z indeksem typu char) , ewentualnie to samo względem 2 pierwszych liter - więcej kubełków tylko - następnie sortujemy te listy MergeSortem (algorytm Państwo macie z Labu 2).- 31/03/2004
   

1. Sortowanie topologiczne grafu skierowanego metodą z twierdzenia  na wykładzie - znajdujemy się wierzchołek z którego nie wychodzi żadna krawędź (jeśli takowego nie ma tzn że istnieje cykl i graf cykliczny czyli nie da się go posortować topologicznie)i ten wierzchołek jest ostatni w porządku topologicznym (nie ma jednoznaczności!), usuwa się następnie krawędzie związane z tym wierzchołkiem i powtarza procedure - 07/04/2004
2. Algorytm przeszukiwania grafu w głąb z zastosowaniem do sortowania topologicznego i znajdowania silnie spójnych składowych GS - 5/05/2004
3. Zaliczenie zadań i algorytmy szukania MST np Prim ewent. alg Dijikstry szukanie minimalnych ścieżek ze żródła - 19/05/2004.
4. Algorytmy szukania minimalnej (najkrótszej) ścieżki z każdego wierzchołka do każdego- 26 maja 2004.
   

1. MergeSort - rekurencyjny na liście 1-wskaźnikowej - lab - 2 pkt
   
2. MergeSort - rekurencyjny na tablicy - dodatkowe - 2  pkt
   
3. MergeSort - nierekurencyjny na liście 1-wskaźnikowej lub tablicy - dodatkowe-1pkt (chyba że to jedyny MS oddany wtedy 2pkt)
4. QuickSort rekurencyjny na tablicy z opcją przełaczania na wersje zrandomizowną - lab-2pkt
5. Sortowanie kubełkowe + MergeSort - dla nazwisk - kubełki - pierwsze litery nazwiska - dodatkowe - 2pkt.
   

1. Dodawanie z wyszukiwaniem do/w BST z wypisywaniem postaci liniowej - lab - 2 pkt. 
2. Treść pkt 1. + usuwanie z BST - 3pkt - dodatkowe.
   
3. Dodawanie/usuwanie z wyszukiwaniem do/z AVL z wypisywaniem postaci liniowej (obejmuje (2) 6pkt) - dodatkowe

1. Sortowanie topologiczne grafu skierowanego (GS) zadanego macierza - algorytmem z dowodu na warunek niecykliczności GS z wykładu. Algorytm ma  podac dane wejściowe i jako wynik wierzchołki w kolejności wg porządku topologicznego - lab -  2pkt
2. Algorytm przeszukiwania grafu w głąb - tworzący drzewa w postaci list z czasami odkrycia i zaczernienia z zastosowaniem do sortowania topologicznego grafu skierowanego 4pkt - lab.
3. Treść jak 2. ale z zastosowaniem do znajdowania spójnych składowych grafu skierowanego - dodatkowe (4 jak zamiast 2. lub 1pkt razem z 2. 

1. Algorytm Kruskal - wyszukuje krawędź o minimalnej wadze i sprawdza czy jest ona bezpieczna jak ta kzostaje dodana do zbioru krawędzi który w końcu stworzy MST -  4pkt - dodatkowe
2. Algorytm Prim - tworzy od razu drzewo (zaczynając od [ustego i określonego wierzchołka) stopniowo dodając bezpieczne krawędzie aż to drzewo rozepnie cały graf -4 pkt - dodatkowe

1. Algorytm Dijikstry - 4 pkt - dodatkowe

Równania różniczkowe zwyczajne z laboratorium
Lab odbywa się co dwa tygodnie. Plan wykładu (dane od wykładowcy prof P. Rybki) i terminy i krótkie opisy kolejnych zajęc na laboratorium:

• Program wykładu

• Laboratorium
  

Warunki zaliczenia: 2 kolokwia na ćwiczeniach(2x40=80pkt)  +  pktu z zadań na labie (2x10=20pkt). Zaliczenie: suma pktów z kolokwiów i labu > 40pkt pktów.

• pierwsze - 25 marca 2004 czwartek 12:15-13:45 - na ćwiczeniach -  zakres: wszystko co było na ćwiczeniach przed kolok., tzn m.in. rów. o zmiennych rozdzielonych, r. jednorodne, różniczka zupełna (met. szukania całki pierwszej gdy równanie Fdx+Gdy=0 spełnia dF/dy=dG/dx poprzez całkowanie po konturze), czynnik całkujący,  rząd schematu, proste schematy np Eulera otw. i midpoint, równanie liniowe skalarne, r. Bernouliego i Ricattiego, tw o istnieniu i jednoznacz., o przedłużaniu (o ile zdążymy przed kolokwium), tworzenie równań poprzez ich własności geometryczne, czy poprzez model fizyczny np piłkę o masie 1kg kopnięto w górę w polu grawitacyjnym z pręd 5m/s  siła oporu powietrza jest proporcjonalna do kwadratu prędkości (st. prop. = 1)  obliczyć prędkość w zależności od czasu.
• drugie - 13 maja 2004  czw 12:15-13:45- zakres: wszystko co było do tego terminu na ćwiczeniach; w szczególności: obliczanie pochodnych względem parametru czy warunków początkowych, jednoznaczność lokalna i globalna rozwiązania, rozwiązania wysycone; Równania liniowe ze stałymi współczynnikami, jednodrodne, niejednorodne - znajdowanie rozwiązań ogólnych,  zag. początkowego.  Równania wyższych rzędów  ze zmiennymi i stałymi współczynnikami,: znajdowanie rozwiązań r,. jednorodnego i met. zmiennych współczynników czy  uzmienniania stałych znajdowania rozwiążań dla r. niejednorodnego.  Wrońskian, układ fundamentalny np  badanie czy dany układ fun. tworzy układ fundamentalny  dla r. liniowego itp 
  

Literatura:

1. W. I. Arnold,  Równania różniczkowe zwyczajne. Państwowe Wydawnictwo Naukowe, (PWN) Warszawa 1975. Tłumaczenie z rosyjskiego. Książka wyłącznie o teorii równań różniczkowych zwyczajnych.
2. N. M.  Matwiejew Metody całkowania  równań różniczkowych zwyczajnych. Państwowe Wydawnictwo Naukowe, (PWN) , Warszawa 1986. Klasyczny podręcznik, głównie metody rozwiązywania równań.
   
3. N. M.  Matwiejew Zadania z równań różniczkowych zwyczajnych. Państwowe Wydawnictwo Naukowe, (PWN) , Warszawa 1976.  Zbiór zadań.
   
4. Jerzy Ombach Wykłady z równań różniczkowych wspomagane komputerowo-Maple. Wydawnictwo Uniwersytetu Jagielońskiego,   Krakow 1999. Tylko teoria  rrz, bez schematów numerycznych ale za to sporo o Maple.
5. Andrzej Palczewski Równania Różniczkowe zwyczajne   Teoria i metody numeryczne z wykorzystaniem komputerowego systemu obliczeń symbolicznych. Wydawnictwo Naukowo-Techniczne (WNT) ,Warszawa 1999. Teoria równań różniczkowych i schematów, trochę o maple'u.
6. A. F. Filippow Sbornik zadaczi po difieriencjalnym urawnieniam. Nauka, Moskwa, 1979, zbiór zadań, po rosyjsku.