Zadanie 1

Zakładamy że tablica mieszajaca jest zrealizowana następująco

Mając słowo w najpierw obliczamy wartość funkcji mieszającej h = f(w)
Nastepnie wykonujemy wyszukiwanie na liście której początek jest przechowywany w t[h]. Jeśli nie znajdziemy w to dodajemy je do tej listy.
Na początku wszystkie listy są puste.

Oszacować średnią długość list po wykonaniu m wyszukiwań, zakładając że f(w) przyjmuje losowe wartości, niezależne i równo rozłożone w przedziale 1..N.

Zadanie 2

Niskopoziomowe C dopuszcza tylko :

zmienne całkowitoliczbowe
podstawienie zmiennej pod zmienną postaci `zmienna1 = zmienna2' lub `zmienna1 = stała'
podstawienie wyniku działania pod zmienną, postaci `zmienna1 = zmienna2 operator zmienna3' (po prawej stronie może być tylko jeden operator, operatorami są `+', `-', `*', '/', '%', '<', '>', '==', '!=', '<=', '>=')
skok bezwarunkowy, postaci `goto etykieta'
skok warunkowy, postaci `if (zmienna) goto etykieta'

Przed dowolną instrukcją można umieścić etykietę.

Przetłumaczyć poniższe fragmenty programów z C do niskopoziomowego C (jako że zmienne są całkowitoliczbowe dla uproszczenia pomijam deklaracje):

if (a<b) {
  tmp = b;
  b = a;
  a = rmp;
}
while(a != b) {
  tmp = b;
  b = a % b;
  a = tmp;
}

i drugi fragment:

for(s=0, i=0; i<10; s+=i*i, i++);

i trzeci:

a = (a+b)*(c=a-b)+d++;

Zadanie 3

Maszyna stosowa operuje na liczbach całkowitych. Ma ona stos i dodatkową pamięć. Zmienne w dodatkowej pamięci są nazwane. Maszyna ma następujące instrukcje:

`push zmienna' -- umieszcza zmienną na szczycie stosu
`push stała' -- umieszcza stałą na szczycie stosu
`pop zmienna' -- pobiera wartość ze szczytu stosu i umieszcza w zmiennej
operacje "arytmetyczne": `+', `-', `*', '/', '%', '<', '>', '==', '!=', '<=', '>='. Pobierają one dwa argumenty ze szczytu stosu i umieszczają wynik na stosie
`jmp etykieta' -- instrukcja skoku bezwarunkowego
`jnz etykieta' -- instrukcja skoku warunkowego, skok wykonuje się gdy wartość na szczysie stosu jest różna od zera. Ta instrukcja usuwa przebadaną wartość ze stosu

Przed dowolną instrukcją można umieścić etykietę. Przetłumaczyć fragmenty C z zadania 1 na instrukcje maszyny stosowej.

Zadanie 4

Maszyna stosowa została zmodyfikowana, tak że komórki pamięci dodatkowej są numerowane. Do maszyny dodano dwie nowe instrukcje: `pushi' która odczytuje (i usuwa) numer (liczbę) NR ze stosu, a natępnie umieszcza zawartość komórki NR na stosie, oraz `popi' która odczytuje (i usuwa) numer (liczbę) NR ze stosu, a natępnie pobiera wartość szczytu stosu i umieszcza w komórce NR.

Jak można wykorzystać te nowe instrukcje do obsługi tablic. Przetłumaczyć poniższy program w C na instrukcje maszyny stosowej:

for(i=0; i<100; i++) {
  a[i]++;
}

zakładając że `a' jest 100 elementową tablicą.

Zadanie 5

W niektórych przypadkach, np. jeśli program nie zawiera pętli, można obliczyć ile komórek stosu on potrzebuje (a także do których komórek się odwołuje w poszczególnych instrukcjach) i zastąpić odwołania do stosu odwołaniami do zmiannych. Pozwala to podać tłumaczenie takich programów maszyny stosowej (tej z zadania 3) na niskopoziomowe C, tak by jedna instrukcja maszyny stosowej odpowiadała jednej instrukcji niskopoziomowego C. Np. instrukcja stosowa `+' będzie tłumaczona na `s115 = s116 + s115;' (zakładająć że n-tej komórce stosu damy nazwę sn i że śledząc użycie stosu wyszło nam że komórka nr 116 jest szczytem stosu przed wykonaniem tej instrukcji). Przetłumaczyć stosową wersję trzeciego fragmentu z zadania 1 na niskopoziomowe C używająć naszkicowane wyżej tłumaczenie 1-1. Porównać to z bezpośrednim tłumaczeniem na niskopoziomowe C.