Zadanie 1

for i := k to m do instr

for(i = k; i <= m; i++) instr

Zadanie 2

--------------------------------------------------------------

Zadanie 3

Zadanie 4

----------------------------------------------------------

Zadanie 5

• Mamy tablicę t indeksową liczbami z [1,N] w której przechowujemy listy par (klucz, wartość). Listy te na początku są puste.
• Mając słowo w najpierw obliczamy wartość funkcji mieszającej h = f(w)
• Nastepnie wykonujemy wyszukiwanie na liście przechowywanej w t[h]. Jeśli nie znajdziemy w to dodajemy je do tej listy.

Oszacować średnią długość list po wstawieniu m elementów, zakładając że f(w) przyjmuje losowe wartości, niezależne i równo rozłożone w przedziale 1..N. Porównać oczekiwaną liczbę operacji i zajętość pamięci przy wyszukiwaniu w tabeli mieszającej i w drzewie binarnym.

Zadanie 6

W celu powiększenia wydajności programów staramy się by dostęp do zmiennych był wyrównany, tzn. jeśli potrzebna jest zmienna 2 bajtowa to przechowujemy ją pod adresem podzielnym przez 2, jeśli 4-bajtowa to pod adresem podzielnym przez 4 i tak dalej aż do długości słowa komputera. Aby to osiągnąc w struktórach wprowadza się dodatkowe nieużywane miejsce pomiędzy końcem jednej składowej a początkiem następnej. Ponadto na końcu struktury może być potrzeba dodatkowa nieużywana przestrzeń, tak by jeśli struktury są umieszczone w pomięci po kolei (np. jako elementy tablicy) pola następnej struktury znalazły się we właściwym miejscu.

Mamy następujące deklaracje struktur:

struct { char c; long l; short s; int i;} st1;

struct { long l; short s; char c;} st2;

Jak będzie wyglądało ich rozmieszczenie w pamięci zakładając że 2-bajtowe short i 4-bajtowe int i long oraz że short, int i long muszą być przechowywane pod adresami podzielnymi przez 2. Jak to się zmieni jeśli int i long muszą być przechowywane pod adresami podzielnymi przez 4. Jak to się zmieni jeśli long jest 8-bajtowy i musi być przechowywany pod adresami podzielnymi przez 8.

Zadanie 7

Rozważmy następującą deklarację w C:

struct {
    struct {
       int i1;
       char c1;
    } s1[3];
    int i2;
    struct {
       int i2;
       char * str1;
    } s2;
} s3[5];

Zadanie 8

int z = 0;
void foo() { z++;}
....
{
s1 = 0;
s2 = 0;
b = random();
for(i = 0; i < 100; i++) {
    foo();
    k = 5;
    c = b;
    d = c + k;
    f = random();
    g = d + z;
    s1 += f;
    s1 += g;
    s2 += d;
}
}

• jawne stałe i zmienne do których nie ma przypisania wewnątrz pętli
• co wyżej plus wartości funkcji ze stałymi argumentami
• jawne stałe i zmienne lokalne (niewidoczne dla innych funkcji) do których nie ma przypisania wewnątrz pętli
• jak wyżej plus uznajemy za stałe wyrażenia arytmetyczne ze stałymi argumentami

Zadanie 9

Uwaga: powyżej piszę o wykonywanych operacjach ponieważ proporcje instukcji w treści programu często znacznie się różnia od proporcji w trakcie wykonania. Po prostu niektóre (zwykle małe) fragmenty programu są znacznie częściej wykonywane niż inne części programu.

Zadanie 10