INE2022 - Program wykładu "Języki Programowania 1"

Politechnika Wrocławska, Wydział Elektroniki, Kierunek: Informatyka ( 1 rok, 2 semestr )

INE 2022 - JĘZYKI PROGRAMOWANIA (1)

Termin sprawdzianu zaliczeniowego z wykładu ustalono na: 3 czerwca 2004, o godz.7.20
Przykładowe zadania na kolokwium.
Wyniki będą podane 10-13 czerwca na "Tablicy ogłoszeń"

Konsultacje: wtorki i czwartki w godz. 13.15-15.00 pok. 324 C-3

Program laboratorium 2003/2004

Program wykładu: (prow. dr Marek Piasecki)

Część I. Statyczne agregacyjne modele danych i ich implementacja w języku C++

Wstęp. Elementarne, złożone i abstrakcyjne typy danych,
Rola abstrakcji i metod formalnych w informatyce.
Przykłady różnych sposobów zaimplementowania
operacji wstawiania / pobierania elementu tablicy.
Folie z przykładowymi programami do 1 wykładu (PDF 25KB)

Zastosowania tablicowej reprezentacji danych
- tablicowa implementacja listy,
- standardowe zastosowania: stos, kolejka (naturalna, bufor cykliczny)
- kolejka z operacją wstawiania na początek (cofania)
- lista (kolejka) uporządkowana
Folie z przykładowymi programami do 2 wykładu (PDF 22KB)
Złożone statyczne agregacje danych - tablice struktur
- standardowa lista (tablica struktur z licznikiem)
- lista struktur z flagami zajęte/wolne
- tablicowa implementacja kolejki priorytetowej
Indeksowe struktury wiązane
- tablica struktur sortowana z wykorzystaniem tablic indeksów
- tablicowa implementacja listy wiązanej / uporządkowanej (struktury z polem "następna")
Folie z przykładowymi programami do 3 wykładu (PDF 20KB)

Elementy języka C++ wspomagające abstrakcję danych
- definicje typów (typedef)
- wzorce-szablony funkcji i klas (template<>)

Część II. Dynamiczne struktury danych i ich implementacja w języku C++

Powtórzenie (zarządzanie pamięcią - klasy pamięci ,
zmienne: automatyczne, zewnętrzne, statyczne, dynamiczne
alokowanie pamięci na stercie, wskaźniki, arytmetyka wskaźników)
Dynamiczne tablice liczb i dynamiczne tablice struktur
Reprezentacje wiązane za pomocą wskaźników.
Folie z przykładowymi programami do 4 wykładu (PDF 92KB)
Cd. reprezentacji wiązanych za pomocą wskaźników
Dynamiczne tablice wielowymiarowe.
Tablica struktur sortowana z wykorzystaniem indeksowych tablic
Rekurencyjne struktury danych - dynamiczna lista jednokierunkowa (stos, kolejka)
Folie z przykładowymi programami do 5 wykładu (PDF 30KB)
Dynamiczna lista dwukierunkowa, cykliczna, uporządkowana
Lista list, drzewa, grafy.

Część III. Programowanie modułowe

Tworzenie i zarządzanie złożonymi programami.
Projekty - programy wieloplikowe
- dyrektywy preprocesora, kompilacja warunkowa
- podział programu na pliki źródłowe i nagłówkowe
- wykorzystanie istniejących i tworzenie własnych bibliotek
Folie z przykładami do 7 wykładu: (PDF 162KB) , (PDF 19KB)

Część IV. Metody formalne w informatyce
(W tej części wykładu wykorzystane zostaną materiały przygotowane przez dr Zofię Kruczkiewicz)

Metodologia ADT - projektowanie Abstrakcyjnych Typów Danych
Folie z przykładami do 8 wykładu: (przykład_1 PDF 30KB) , (przykład_2 PDF 12KB)
Logika w informatyce: rachunek zdań, tautologie, metody dowodzenia,
rachunek kwantyfikatorów, dedukcja naturalna,
zupełność, niesprzeczność, nierozstrzygalność
Folie do 9 wykładu: (PDF 270KB)
Testowanie programów
Folie do 10 wykładu: (PDF 214KB)
Złożoność strukturalna programów 1 - Metryki złożoności modułowej
Folie do 11 wykładu: (PDF 146KB) (PDF 209KB)
Złożoność strukturalna programów 2 - Metryki międzymodułowe
Folie do 12 wykładu: (PDF 155KB)
Logika programów Hoare'a
Języki formalne, gramatyki, notacja BNF

Część V.

Sprawdzian zaliczeniowy

Literatura:

A. Aho, J. Ullman - "Wykłady z informatyki z przykładami w języku C"
( Zagadnienia dotyczące modeli, pojęć i technik z zakresu matematyki dyskretnej i informatyki.
Modele danych oparte na drzewach, listach i zbiorach. Relacyjny i grafowy model danych
Wzorce, automaty i wyrażenia regularne, rekurencyjny model wzorców
Gramatyki bezkontekstowe, wyrażenia regularne,
Tautologie i metody dowodzenia. Logika zdań. Logika predykatów. )

Robert Sedgewick “Algorytmy w C ++ “
( Elementarne struktury danych: tablice, listy, metody przetwarzania list
Abstrakcyjne typy danych, Obiekty abstrakcyjne i zbiory obiektów,
Stos, Kolejki FIFO i kolejki uogólnione, Tablice symboli i drzewa )

A. Aho, J. Hopcroft, J. Ullman - "Algorytmy i struktury danych"
(Abstrakcyjne typy danych oraz ich implementacje: listy, stosy, kolejki, mapowania,
struktury drzewiaste, zbiory, tablice haszowane, kolejki priorytetowe, grafy )

Niklaus Wirth "Algorytmy + struktury danych = programy"
( Dynamiczne struktury informacyjne: wskaźniki, listy, struktury drzewiaste,
uwaga: przykłady są implementowane w Pascalu)

Zalewski Andrzej - "Programowanie w językach C i C++ z wykorzystaniem pakietu Borland C++"
( Dynamiczne struktury danych: stosy, kolejki, listy jednokierunkowe, dwukierunkowe, cykliczne, drzewa.
Tworzenie i zarządzanie złożonymi programami. Wielomodułowość programów w języku C/C++.
Konstrukcja zbioru nagłówkowego. Tworzenie bibliotek. Projekty. )

Kenneth A. Reek - "Język C. Wskaźniki"
(różne metody implementacji często stosowanych abstrakcyjnych typów danych,
Wykorzystanie struktur i wskaźników: lista jednokierunkowa, dwukierunkowa.
Klasyczne przykłady abstrakcyjnych typów danych: stosy, kolejki, drzewa.)

Kyle Loudon "Algorytmy w C"
(listy wiązane, stosy, kolejki, zbiory, tablice asocjacyjne, drzewa, sterty, kolejki priorytetowe i grafy)

Piotr Wróblewski - "Algorytmy, struktury danych i techniki programowania"
( listy jednokierunkowe, dwukierunkowe, stos, kolejki FIFO i priorytetowe,
drzewa, elementy algorytmiki grafów )

Ostatnia aktualizacja: 21.04.2004