Ćwiczenie nr 1 Wprowadzenie do Informatyki



Pobieranie 88.45 Kb.
Data07.05.2016
Rozmiar88.45 Kb.
Plik źródłowy: ; Data: 2007-10-5 11:18:00 AM

J.Nawrocki, M. Antczak, G. Palik, A. Widelska


Ćwiczenie nr 1

Wprowadzenie do Informatyki


Zad. 1. Narysować graf nieskierowany. Zmodyfikować go w taki sposób, aby stał się grafem skierowanym. Czy w tym grafie znajduje się cykl? Jeżeli nie, to zmodyfikować graf w taki sposób, aby zawierał cykl.

Zad. 2. Narysować klikę i mając do dyspozycji rysunek, zaznaczyć poprawne odpowiedzi (wiele może być poprawnych). Klika to:

  1. graf, w którym każdy wierzchołek jest bezpośrednio połączony z każdym z pozostałych wierzchołków,

  2. graf skierowany,

  3. graf nieskierowany,

  4. graf G4 jest kliką o rozmiarze 3,

  5. graf G5 jest kliką o rozmiarze 3,

  6. liczba krawędzi dla kliki o rozmiarze n wynosi k(n)=k(n-1)+n-1.

Zad. 3. Narysować drzewo i zaznaczyć następujące wierzchołki: korzeń, liście, ojca, dziecko. Mając do dyspozycji rysunek, zaznaczyć poprawne odpowiedzi (wiele może być poprawnych). Drzewo to:

  1. graf skierowany,

  2. graf nieskierowany,

  3. w strukturze drzewa wierzchołki mogą jednocześnie pełnić funkcje ojców i dzieci,

  4. wszystkie wierzchołki w drzewie pełnią funkcje jednocześnie ojca jak i dziecka,

  5. korzeń drzewa będąc ojcem jednocześnie pełni funkcje dziecka,

  6. liście w drzewie nie pełnią funkcji ojców.

Co to jest maksymalna głębokość drzewa? Ile wynosi maksymalna głębokość drzewa dla powyższego przykładu?

Zad. 4. Narysować acykliczny graf skierowany. Czy drzewo jest acyklicznym grafem skierowanym? Dlaczego?

Zad. 5. Problem kolorowania grafu w klasycznej postaci dotyczy kolorowania węzłów grafu nieskierowanego (czyli „grafu bez strzałek”). Należy pokolorować węzły w taki sposób, aby każda para węzłów połączonych krawędzią miała różne kolory i aby liczba użytych kolorów była minimalna. Oto przykład grafu pokolorowanego właściwie (połączone węzły mają różne kolory) i minimalną liczbą kolorów (zmniejszenie liczby kolorów doprowadziłoby do niewłaściwego pokolorowania):

lub

Pokoloruj optymalnie (czyli minimalną liczbą kolorów) następujące grafy:



2

G1



G2



G3(*)




G5


G4(*)



G6(*)




Zad. 6. Jeśli graf jest kliką o rozmiarze n, to ile potrzeba do jego pokolorowania kolorów. Narysuj klikę o rozmiarze 4 i 5. Ile krawędzi ma klika o rozmiarze n.

Zad. 7(*). Pokoloruj następujący graf (dla ułatwienia podwójną linią zaznaczono węzły tworzące klikę):

G8


Zad. 8(*). Ile kontenerów potrzeba, aby przewieźć wilka (W), gęś (G), kozę (K), marchew (M) i psa myśliwskiego (P). Zakładamy, że w kontenerze nie ma żadnych klatek, ścianek działowych itp. Chcemy zminimalizować liczbę kontenerów i bezpiecznie dowieść dobytek. Jakbyśmy wszystko wpakowali do jednego kontenera, to koza mogłaby zjeść marchew chyba, że wcześniej zjadłby ją wilk, albo pies mógłby zagryźć gęś chyba, że byłby zajęty walką z wilkiem, albo ... Rozwiąż problem za pomocą kolorowania grafu. Jaki wpływ na rozwiązanie problemu ma nasza niewiedza co do zamiarów psa względem kozy? (Może chcieć ją zagryźć albo wskutek dobrej tresury lub respektu przed rogami będzie ją pilnować – różnie to może być.)


Zad. 9(*). Dany jest graf reprezentujący pewną mapę z krawędziami opisanymi liczbami reprezentujący odległości między miejscowościami:

Znajdź taką drogę z miejsca zaznaczonego szarym kolorem, aby przejść przez wszystkie miejscowości i aby łączna długość przebytej drogi była minimalna (jeśli 2 razy idziemy tą samą drogą, to oczywiście liczymy jej długość podwójnie).



Zad. 10. Czy mając dany wykres przedstawiający wyniki z przeprowadzonych pomiarów danego algorytmu można na jego podstawie wnioskować o złożoności tego algorytmu?

Zad. 11(*). Rozwiąż problem podziału zbioru dla zbioru elementów A = {e1, .., e10}, których wartości są następujące: 300, 99, 1, 102, 86, 114, 120, 120, 60, 400.

Podpowiedź: Jeśli zbiory B, C stanowią podział zbioru A (formalnie: A = B  C oraz B  C = ) i suma wartości dla zbioru B jest równa sumie wartości dla zbioru C, to jaka jest relacja tej sumy do sumy wartości dla zbioru A? Inaczej mówiąc, czy można sumę wartości dla zbioru B wyznaczyć na podstawie sumy wartości dla zbioru A? Zbiór A jest dany, a zbioru B dopiero szukamy. Gdybyśmy znali sumę wartości zbioru B, to mogłoby to nam ułatwić jego poszukanie.

Zad. 12. Zaznaczyć poprawne odpowiedzi (wiele może być poprawnych). Wyróżniamy klasy złożoności algorytmów:

  1. wielomianowa,

  2. wykładnicza,

  3. NP-trudna.

Zad. 13. Zaznaczyć poprawne odpowiedzi (wiele może być poprawnych). Wyróżniamy klasy złożoności problemów:

  1. wielomianowa,

  2. wykładnicza,

  3. NP-trudna.





Zad. 14. Uzupełnij podany schemat blokowy tak, aby po wykonaniu obliczeń Wynik = an, gdzie n jest liczbą naturalną

(n >= 0).



Przykład:

an, gdzie a=2 i n=4 => 24=2*2*2*2




Zad. 15. Narysować schemat blokowy dla problemu wyznaczania największego wspólnego dzielnika dwóch liczb (NWD).

Parametry wejściowe: a,b – liczby dla których chcemy wyznaczyć NWD,

Parametr wyjściowy: NWD.

If (a>b)


a=a-b

else if (b>a)

b=b-a

else NWD=a=b;



Przykład:

a=8, b=5


    1. a(8)>b(5) => a=8-5=3

    2. b(5)>a(3) => b=5-3=2

    3. a(3)>b(2) => a=3-2=1

    4. b(2)>a(1) => b=2-1=1

    5. a(1)=b(1) => NWD=1.

Zad. 16(*). Narysować schemat blokowy dla problemu wyznaczania n-tego wyrazu ciągu Fibonacciego.

Parametry wejściowe: n – numer wyrazu ciągu Fibonacciego, który chcemy wyznaczyć (n>=3),

Parametr wyjściowy: Fib(n).

Fib(1)=1; Fib(2)=1;

Fib(n)=Fib(n-2)+Fib(n-1);

Przykład:

Fib(n), dla n=3?

Fib(3)=Fib(1)+Fib(2)=1+1=2.

Zad. 17(*) Narysować schemat blokowy dla problemu wyznaczania sumy cyfr dowolnej liczby naturalnej n

Parametry wejściowe: n – dowolna liczba naturalna.

Parametr wyjściowy: Sum(n).

Podpowiedź: Wykorzystać operatory części całkowitej (div) oraz reszty z dzielenia (mod) przy dzieleniu wejściowej liczby naturalnej (n) i liczby „10”.

Przykład:

n=12 => Sum(n)=1+2=3.


Zad. 18(*). Narysować schemat blokowy dla problemu wyznaczania minimalnej (min) wartości z tablicy zawierającej liczby naturalne.

Parametry wejściowe: n – tablica liczb naturalnych, size(n) – rozmiar tablicy n.



Parametr wyjściowy: min.

Przykład:

n = {1,3,2,4,2,7,3}, size(n)=7 => min = 1.


Zad. 19. Uzupełnij podany schemat blokowy tak, aby znaleźć wartość y=Max {xi}, gdzie i jest liczbą naturalną <1,n>.


Zad. 20. Uzupełnij lub wybierz poprawne twierdzenia:

  1. pamięć wirtualna wykorzystuje algorytm ...............................................................(LRU eng. Least Recently Used), w celu pobierania stron z dysku twardego do pamięci operacyjnej.

  2. adresy logiczne (ladrs) to adresy: a) w pamięci, b) na dysku,

  3. adresy fizyczne (fadrs) to adresy: a) w pamięci, b) na dysku,

  4. zawartość komórki „Blok” w tablicy stron odpowiada.................................................................

Zad. 21. Rozmiar strony pamięci wirtualnej jest równy 3. Stan pamięci wirtualnej jest opisany podanym rysunkiem:






















0

























1







PAO







Tablica stron




2




0







Str

Blok

Jest




3




1







0

0

0




4




2







1

0

1




5




3







2

3

1




6




4







3

0

0




7




5



















8

























9

























10

























11



Czy zawartość komórki o adresie logicznym 1 znajduje się w pamięci operacyjnej (PAO)? A jak jest z zawartością komórki o adresie logicznym 7? Jeśli jej zawartość jest w pamięci operacyjnej, to wyznacz jej adres fizyczny. W jaki sposób można zmniejszyć rozmiar tablicy stron?



Zad. 22. Pamięć wirtualna składa się z 24 komórek o adresach logicznych od 0 do 23. Strona pamięci wirtualnej zawiera 4 komórki. Pamięć operacyjna ma 8 komórek o adresach fizycznych od 0 do 7 i jest podzielona na 2 bloki po 4 komórki. Stan pamięci operacyjnej i tablicy stron reprezentuje poniższy rysunek:




Pam.oper.







0

55




Tab.stron

1

66

0

-1

2

77

1

-1

3

88

2

-1

4

1111

3

4

5

2222

4

0

6

3333

5

-1

7

4444







Podaj wartości komórek pamięci wirtualnej a adresach logicznych 17 i 12?

Zad. 23(*). Pamięć wirtualna składa się z 24 komórek o adresach logicznych od 0 do 23. Strona pamięci wirtualnej zawiera 4 komórki. Pamięć operacyjna ma 8 komórek o adresach fizycznych od 0 do 7 i jest podzielona na 2 bloki po 4 komórki. Stan pamięci operacyjnej i tablicy stron reprezentuje poniższy rysunek:




Pam.oper.







0

55




Tab.stron

1

66

0




2

77

1




3

88

2




4

1111

3




5

2222

4




6

3333

5




7

4444







Uzupełnij zawartość komórek w tablicy stron na podstawie zawartości pamięci operacyjnej oraz poniżej zdefiniowanych zależności:

ladrs=15 => fadrs=7, ladrs=4 => fadrs=0.

Zad. 24. Zaznacz właściwe odpowiedzi (wiele może być poprawnych):

  1. kompilator składa się z analizatora i generatora,

  2. analizator to inaczej „backend”,

  3. generator to inaczej „frontend”,

  4. analizator to inaczej „frontend”,

  5. generator to inaczej „backend”,

  6. gdy powstają nowe procesory udostępniające więcej funkcji to podczas tworzenia nowych wersji kompilatora modyfikowany jest analizator,

  7. gdy powstają nowe procesory udostępniające więcej funkcji to podczas tworzenia nowych wersji kompilatora modyfikowany jest generator.

Zad. 25. Dlaczego podczas wykorzystywania metod numerycznych występują przekłamania? (podaj przynajmniej dwie odpowiedzi)

Zad. 26. Jaka forma reprezentacji liczb zmiennoprzecinkowych pozwala zachować w trakcie obliczeń informację o błędzie wyniku?

(*) gwiazdką oznaczone są zadania, które nie są realizowane na ćwiczeniach i są przeznaczone do wykonania jako zadania domowe.





©absta.pl 2019
wyślij wiadomość

    Strona główna