Paradygmaty programowania/Ćwiczenia 3: Typy, typy abstrakcyjne

Zadanie 1

Zaimplementuj bibliotekę do obsługi liczb w reprezentacji stałopozycyjnej. Biblioteka powinna umożliwiać tworzenie liczb w reprezentacji stałopozycyjnej o różnych wielkościach (tzn. o danej liczbie cyfr przed i po przecinku) oraz prowadzenie typowych obliczeń — powiedzmy działań arytmetycznych, potęgowania i pierwiastkowania. Pamiętaj, że rzecz ma sens tylko wtedy, gdy będzie działała szybko.

Wskazówka:

Należy zadbać nie tylko o dobre struktury danych, ale i algorytmy. Dodawanie jest mało kontrowersyjne, ale już mnożenie można zrobić lepiej niż jako „mnożenie pisemne”... Tym bardziej potęgowanie — nie wolno stosować algorytmu naiwnego, mnożącego liczbę przez siebie odpowiednio wiele razy.

Zadanie 2

Napisz klasę w C++ lub Javie implementującą napisy w pełni dynamiczne. Oczywiście nie korzystaj z gotowych klas w rodzaju StringBuilder lub StringBuffer. Klasa powinna dawać przynajmniej takie metody: tworzenie napisu (pustego, ze stałej lub z innego napisu), sprawdzanie równości, porównywanie alfabetyczne, konkatenacja, długość, wycinanie fragmentu.

Wskazówka:

Pamiętaj o tym, by przy porównywaniu brać pod uwagę długość napisów. Rozważ różne sposoby alokowania pamięci, np. z naddatkiem w stosunku do tworzonego napisu, by mieć zapas „na później”.

Zadanie 3

Zapisz ogólną postać wzoru na adres elementu tablicy wielowymiarowej pamiętanej wierszami przy założeniu, że tablica ma k wymiarów, indeksujemy od zera, liczba elementów w poszczególnych wymiarach to $n_1,n_2,...,n_k$, a indeks, dla którego liczymy adres, to $i_1,i_2,...,i_k.$

Zadanie 4

Zaimplementuj tablice asocjacyjne w dowolnym języku (oczywiście nie korzystając z gotowego mechanizmu, jeśli on w języku już istnieje). Implementacja za pomocą funkcji haszujących pozwala uzyskać stały średni czas dostępu do tablicy, podczas gdy drzewo binarne daje średni czas rzędu log n, gdzie n jest liczbą elementów w tablicy. Czy w takim razie tablice haszujące są bezwzględnie lepsze od drzew w tej roli? W jakich sytuacjach drzewo mogłoby być lepsze?

Zadanie 5

Zaimplementuj sparametryzowaną klasę w C# lub Javie, obsługującą stos elementów dowolnego typu, z operacjami włożenia na stos, zdjęcia ze stosu i sprawdzenia, czy stos jest pusty. Jak zwykle, nie korzystaj z gotowych rozwiązań... Czy są sytuacje, gdzie lepiej zaimplementować kilka klas dla konkretnych typów zamiast jednej klasy sparametryzowanej?

Zadanie 6

Implementując klasy sparametryzowane, twórcy Javy zastosowali dość proste w istocie rozwiązanie. Kompilując kod sparametryzowany, kompilator usuwa z niego informacje o parametrach „typowych” i zastępuje je ogólnym typem Object, następnie generuje kod jak dla klas bez parametrów i w razie potrzeby dodaje konwersje typów. Jak sądzisz, dlaczego zdecydowano się na takie rozwiązanie?

Wskazówka:

Klasy sparametryzowane zostały dodane do Javy dopiero w wersji 5.0 (zwanej też 1.5). Dzięki takiej implementacji kod stworzony w nowszej wersji działa na starszych maszynach wirtualnych Javy. Wadą tego rozwiązania jest jednak nie najlepsza efektywność dla typów prostych (które muszą być „opakowywane”) oraz utrata dynamicznej informacji o typach.

Zadanie 7

Implementacja sparametryzowanych klas w C++, C# i Javie to trzy różne podejścia do sprawy. Jakie są wady i zalety tych rozwiązań? Ciekawe porównanie tych implementacji można znaleźć pod adresem http://www.artima.com/intv/generics.html.

Test

Pojęcie typu w językach imperatywnych bliskie jest pojęciu:

całki Riemanna Źle

pary uporządkowanej Źle

zbioru nieskończonego Źle

zbioru skończonego Dobrze

Który z opisanych poniżej typów można uznać za typ abstrakcyjny? Rzecz dzieje się w języku C:

struktura wraz z kilkoma działającymi na niej funkcjami Źle

typ wskaźnikowy T *, gdzie T jest zdefiniowane następująco\: typedef int T[10]; Źle

wbudowany typ float Dobrze

unia złożona z pól tego samego typu Źle

W której sytuacji tablica asocjacyjna byłaby istotnie wygodniejsza niż zwykła tablica?

mamy katalogi ponumerowane od 1 do 100 i zapisujemy ich rozmiar Źle

sortujemy obszerną tablicę liczb typu double Źle

wyszukujemy największą liczbę w tablicy Źle

zapisujemy kolor przejeżdżających samochodów, identyfikując je numerami rejestracyjnymi Dobrze

Ewentualne luki między przechowywanymi w pamięci polami rekordu biorą się z:

konieczności sprawdzenia zgodności typów Źle

konieczności umieszczania pól pod adresami, których 1 lub 2 najmniej znaczące bity są zerami Dobrze

niedoskonałości kompilatorów Źle

szybkich przesunięć cyklicznych w jednostce arytmetyczno-logicznej procesora Źle

Załóżmy, że w języku C sprawdzamy równość struktur (oczywiście tego samego typu). Dlaczego w ogólności nie można tego zrobić przez porównywanie bloków pamięci?

istnieje kilka rozmiarów liczb całkowitych Źle

napisy mogą zawierać nieistotne znaki za znacznikiem końca Dobrze

nie można z góry przewidzieć, czy napisy są zapisane w kodzie ASCII, czy Unicode Źle

reprezentacja liczb float i double nie jest jednoznaczna Źle

Który operator języka C jest potrzebny, gdy wykorzystujemy wskaźniki do adresowania pośredniego?

& Dobrze

++ Źle

-- Źle

nawiasy kwadratowe do indeksowania Źle

Załóżmy, że p jest zmienną wskaźnikową. W którym języku wyrażenie ++p jest poprawne?

C++ Dobrze

C\# Źle

Java Źle

Pascal Źle

Które stwierdzenie jest fałszywe w odniesieniu do klas w języku C++?

definicja klasy nie musi zawierać destruktora Źle

funkcje z klasy mogą być kompilowane jako inline Źle

konstruktor ma taką samą nazwę jak klasa Źle

konstruktor nie może być przeciążany Dobrze

W Javie obiekty są alokowane:

dynamicznie na stercie Dobrze

dynamicznie na stosie Źle

statycznie na stercie Źle

statycznie na stosie Źle

Sparametryzowane typy abstrakcyjne uzyskuje się w C++ za pomocą deklaracji z użyciem słowa kluczowego:

args Źle

generic Źle

params Źle

template Dobrze