Teoretyczne Podstawy Informatyki

Teoretyczne Podstawy Informatyki

Informatyka Stosowana

Wydział Fizyki, Astronomii i Informatyki Stosowanej,

Uniwersytet Jagielloński w Krakowie

Rok akademicki 2017/2018

Konsultacje: wtorek, godz. 14:00 - 15:00; pokój D-2-11.

Egzamin I: 31.01, godz. 13.00-15.00, sala A-1-06, A-1-08
Egzamin II: 23.02, godz. 9.30-11.30, sala A-1-06
Wykład: poniedziałek, 14.15 - 16.00, sala A-1-06

Data	Tytuł
13.10.2017	Informacja i sposoby jej zapisu.
16.10.2017	Struktury danych i algorytmy.
20.10.2017	Złożoność obliczeniowa algorytmów;
30.10 2017	Iteracja, rekurencja i indukcja. Algorytmy sortujące. Rozwiazywanie rekurencji.
6.11.2017	Modele danych: wstep Lista, stos, kolejka.
13.11.2017	Modele danych: zbiory i drzewa
20.11.2017	Modele danych: relacyjne bazy danych
27.11.2017	Modele danych: grafy
4.12.2017	Data Science: Dane w postaci grafów. Algorytm PageRanking Kominatoryka i algorytmy probabilistyczne
18.12.2017	Opis wzorców: automaty i wyrażenia regularne
19.12.2017	Opis wzorców: gramatyki
15.01.2018 i 16.01.2018	Data Science: Metody eksploracji danych Data Science: Algorytmy grupowania Data Science: Algorytmy uczenia maszynowego
22.01.2018	Repetytorium: Algorytmy i schematy blokowe Repetytorium: Złożoność obliczeniowa Repetytorium: Twierdzenia dowodzone przez indukcje Metody programistyczne

Zakres tematyczny:

-> co to jest informacja
-> algorytmy i struktury danych, poprawność algorytmu;
-> złożoność obliczeniowa algorytmów
-> rekursja, indukcja, iteracja, teoria prawdopodobieństwa;
-> modele danych: drzewa, listy, zbiory, relacje, grafy;
-> wzorce, automaty, wyrażenia regularne i gramatyki;

Literatura

1. H. Abelson, G. J. Sussman, J. Sussman, Struktura i intepretacja programow komputerowych.
2. A. V. Acho, J. D. Ullman, Wyklady z informatyki z przykładami w jezyku C.
3. T. H. Cormen, Ch. F. Leiserson, R. L. Rivest, Wprowadzenie do algorytmów.
4. A. Drozdek, D. L. Simon, Struktury danych w jezyku C.
5. L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, WNT 1996.
6. D. Harel, Rzecz o istocie informatyki.
7. J.E. Hopcroft, J. Ullman, Wprowadzenie do teorii automatów, jezyków i obliczeń.
8. S. Kowalski, A. W. Mostowski, Teoria automatow i lingwistyka matematyczna.
9. Ch. H. Papadimitriou, Złożoność obliczeniowa.
10. W. Sikorski, Wykłady z podstaw informatyki.
11. T.H. Cormen, Ch.E. Leirson, R.L. Rivest, Wprowadzenie do algorytmów.
12. N. Wirth, Algorytmy i struktury danych = programy.
13. M. Foryś, W. Foryś, "Teoria automatów i jezyków formalnych", AOW Exit,Wwa 2005.

Ćwiczenia:

grupy prowadzone przez prof. dr hab. E. Richter-Wąs

Nr ćwiczeń	Data (tydzień)	Temat zadań	Materiały uzupełniające (dla zainteresowanych) link
1.	13.10.2017	zestaw 1	Standard IEE 754, Binarne kodowanie liczb Systemy liczbowe Reprezentacja liczb (ćwiczenia)
2.	16.10.2017	zestaw 2	Wstęp do algorytmów Prostokąty i odcinki (ćwiczenia) Problem plecakowy Schemat Hornera
3.	20.10.2017	zestaw 2	Algorytmy w przykladach quicksort heapsort mergesort
4.	30.10.2017	zestaw 3	Poprawność i złożoność obliczeniowa algorytmów Asymptotyka Indukcja Rekurencja
5.	6.11.2017	zestaw 4	Ciąg arytmetyczny, ciąg geometryczny,permutacje
6.	10.11.2017	kontynuacja zestaw 2-4
7.	13.11.2017	zestaw 5	Listy, Zbiory, Stos, Kolejka Listy (ćwiczenia), kod: list.cpp, list.h
	20.11.2017	I Kolokwium: zestaw 2-4
8.	27.11.2017	zestaw 6	Drzewa Drzewa (ćwiczenia)
9.	4.12.2017	zestaw 6
	11.12.2017	cwiczenia odwolane
	15.12.2017	cwiczenie dodatkowe godz 14.15, sala A-2-07
10.	18.12.2017	zestaw 7	Grafy Algorytmy grafowe I Algorytmy grafowe II
	20.12.2017	II Kolokwium: zestaw 5-6 godz 8-10, sala A-1-13
11.	8.01.2017	zestaw 8 i 9
12.	15.01.2018	zestaw 8 i 9
13.	22.01.2018	III Kolokwium: zestaw 7-9

Ostatnia modyfikacja: 14 grudzien 2018

Elzbieta Richter-Was

Wstecz