WSISiZ Wydział Informatyki Studia Zaoczne Rok I Semestr II
Warszawa, luty 2003 r.
Podstawy Programowania – program wykładu (8 wykładów × 2 godz.) Cele poznawcze Celem wykładu jest zapoznanie studenta z podstawami programowania przy użyciu języka C/C++. Program przewiduje poznanie podstawowych typów danych, operatorów oraz zasad budowania wyrażeń i funkcji. Następnym punktem programu będą zmienne wskazujące i zmienne referencyjne, oraz budowa i zastosowania funkcji iteracyjnych jak i rekurencyjnych. W końcowej części wykładów przewiduje się typ strukturalny oraz algorytmy pracujące na tablicach i strukturach wiązanych: listach, stosach, kolejkach i drzewach. Literatura postawowa H.M.Deitel, P.J.Deitel: Arkana C++ - rozdziały: 1, 2, 3, 4, 5, 11, 14, 16, 17 (preprocesing) B.W.Kernigham, D.M.Ritchie: Język ANSI C, WNT B.Stroustrup: Język C++ WNT Warszawa, 2000 - rozdziały 4, 5, 6, 7 (str 77 - 183) David Vandevoorde: Język C++, ćwiczenia i rozwiązania, WNT, 2001 - rozdziały 2 – 7 (rozwiązania wybranych zadań z poz. 3. powyżej)
1. 2. 3. 4.
Literatura – algorytmy i struktury danych 1. Piotr Wróblewski: Algorytmy, struktury danych i techniki programowania, Helion, 1997 2. Adam Drozdek, Donald L. Simon: Struktury danych w języku C, WNT, 1996 3. Robert Sedgewick: Algorytmy w C++, RM, 1999 Egzamin PP Aby przystąpić do egzaminu z PP trzeba mieć pozytywnie zaliczone PP Zaliczenie PP Każdy prowadzący zajęcia laboratoryjne określa tryb zaliczania uwzględniając obecność, pracę w domu i aktywność na zajęciach w formie:
min. 5 prac domowych (np. warianty prac laboratoryjnych, zadania z wykładów) dwa kolokwia (środkowe – 1 godz. i końcowe – 2 godz.) projekt (robią zdecydowanie Ci, którzy chcą uzyskać wyższą ocenę)
Student może uzyskać zwolnienie z egzaminu, o ile w rozliczeniu zajęć laboratoryjnych uzyska ocenę 4+ lub wyżej.
PP – tematy wykładów Wykład 1 : Podstawowe konstrukcje języka C/C++ - wyrażenia Ogólna charakterystyka C/C++, uwagi historyczne i programowe. Preprocesing, kompilacja i konsolidacja programu Słowa kluczowe, przykład programu w języku C/C++: funkcja main(), funkcje użytkownika a funkcje biblioteczne, dołączanie plików nagłówkowych. Budowanie wyrażenia arytmetycznego i funkcji reprezentującej to wyrażenie: Typy wbudowane(podstawowe): znakowy, logiczny bool, całkowity i rzeczywisty. Tworzenie zmiennych i stałych Operatory arytmetyczne i wyrażenia arytmetyczne. Reguły pierwszeństwa i łączności, konwersja i rzutowanie Operatory logiczne i wyrażenia logiczne. Reguły pierwszeństwa i łączności, wartościowanie wyrażenia Operator przypisania „=”, instrukcja przypisania. skróty ++, --, +=, *= itp. Proste użycie strumieni cin, cout do czytania i wysyłania danych Wykład 2 : Podstawowe konstrukcje języka C/C++ - instrukcje sterujące Instrukcje sterujące: wyboru: if, if-else, switch-case, pętle: for, while, do-while Tablice jedno- i dwuwymiarowe, funkcja sizeof. Iteracje ilustrujące pracę instrukcji sterujących Odwołania do funkcji bibliotecznych sqrt(), exp(), log(), sin(),... Wykład 3 : Wskaźniki i referencje. Funkcja i jej prototyp. Dynamiczne zarządzanie pamięcią. Pojęcie zmiennej, wskaźnika, referencji. Arytmetyka na wskaźnikach. Funkcja: typ_funkcji nazwa_funkcji(argumenty){instrukcje} a prototyp funkcji: typ_funkcji nazwa_funkcji(argumenty); Zmienna, wskaźnik i referencja jako argumenty funkcji Tablice i wskaźniki Pojęcie napisu w stylu C, operacje na napisach, standardowe funkcje napisowe (strcmp(), strcpy(), strlen(),...) Dynamiczne zarządzanie pamięcią: operatory new i delete, funkcje memcpy(), memcmp(),... Biblioteczne funkcje modułów , , ... Wykład 4: Typ strukturalny. Strumienie we/wy – –
typ wyliczeniowy, pojęcie struktury ( struct) , unii (union), użycie typedef Zaawansowane działania na wskaźnikach Inicjalizacja składowych struktur i dostęp do składowych. Struktura argumentem funkcji, wartością zwracaną przez funkcję, Strumienie we/wy – czytanie i zapisywanie w pliku na dysku
Wykład 5 : Iteracja a rekurencja Iteracja a rekurencja. Funkcja rekurencyjna. Wybrane algorytmy rekurencyjne i ich odpowiedniki iteracyjne: Algorytmy wyznaczania NWP i NWW dla liczb całkowitych Wartościowanie wielomianu n-tego stopnia – schemat Hornera Sortowanie przez wstawianie, algorytm bąbelkowy, q-sort,... Wyszukiwanie liniowe (na tablicy nieposortowanej) i binarne (na tablicy posortowanej) Metoda bisekcji znajdywania miejsca zerowania funkcji jednej zmiennej Wykład 6 : Abstrakcyjne Typy Danych (ATD) - tablice –
Tablice struktur: implementacja stosu, implementacja listy, implementacja kolejki – Zaawansowane działania na wskaźnikach:, wskaźnik typu void* Wykład 7 : Abstrakcyjne Typy Danych (ATD) – listy i kolejki – Struktury wiązane: lista i lista cykliczna struktur stos implementowany jako lista dowiązaniowa kolejka jako lista dowiązaniowa – Rozwiązania rekurencyjne i iteracyjne Wykład 8 : Abstrakcyjne Typy Danych (ATD) - drzewa Drzewo BST. Strategie przeglądu drzewa. Inne drzewa
dr inż. Bożena Łopuch grupy IZ101-IZ108
dr inż. Henryk Potrzebowski grupy IZ109-IZ112
IBS PAN, pok. 403, 837 35 78 w. 184 e-mail: Bożena.Ł
[email protected]
IBS PAN, pok. 310, 837 35 78 w. 245 e-mail:
[email protected]
