Search
 
 
  Engleski
 
 
 
Open in this window (click to change)
Forum@DeGiorgi: Početna
Forum za podršku nastavi na PMF-MO
Login Registracija FAQ Smajlići Članstvo Pretražnik Forum@DeGiorgi: Početna

Zadatak s natjecanja i halting problem (objasnjenje gradiva)
WWW:

Moja sarma
 
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji 2. godine -> Osnove algoritama
Prethodna tema :: Sljedeća tema  
Autor/ica Poruka
krcko
Forumaš nagrađen za životno djelo
Forumaš nagrađen za životno djelo


Pridružen/a: 07. 10. 2002. (15:57:59)
Postovi: (18B3)16
Sarma = la pohva - posuda
655 = 759 - 104

PostPostano: 18:09 pet, 20. 1. 2017    Naslov: Zadatak s natjecanja i halting problem Citirajte i odgovorite

Jučer je održano natjecanje iz informatike (školska razina). Za 7. razred OŠ postavljen je ovaj zanimljivi zadatak.

[quote][b]Zadatak: Bomboni[/b] (90 bodova)

U dječjem vrtiću "Tulipan" odgajateljica je djeci podijelila bombone. Ali, jao! Neka djeca dobila su manje bombona od drugih.

Reći ćemo da je neko dijete [b]uplakano[/b] ako svako drugo dijete ima strogo više bombona od njega. Odgajateljica je slaba na suze pa se i sama rasplače kad vidi uplakano dijete. Ona tada posegne za golemom vrećom bombona i uplakanom djetetu [b]udvostruči[/b] broj bombona. Na primjer, ako uplakano dijete ima 3 bombona, dobit će još 3 bombona pa će imati 6 bombona.

Ako se tada opet pojavi neko uplakano dijete, odgajateljica će učiniti isto, i taj će se postupak ponavljati dok god postoji bilo koje uplakano dijete. Ako u nekom trenutku [b]nijedno[/b] dijete više nije uplakano, što znači da nijedno dijete nema manje bombona od svakog drugog djeteta, postupak se zaustavlja. Moguće je i da se postupak ponavlja [b]beskonačno[/b], a u tom će slučaju odgajateljica naručivati nove bombone iz tvornice kad god joj ponestane bombona. (Još nije poznato kako će ih platiti.)

Napiši program koji, za dane početne količine bombona svakog djeteta, ispisuje njihove konačne količine bombona ako se postupak zaustavi, ili riječ "INFINITY" ako će postupak trajati beskonačno.

[b]ULAZNI PODACI[/b]

U prvom retku nalazi se prirodan broj [i]N[/i] (2≤[i]N[/i]≤10), broj djece. U sljedećih [i]N[/i] redaka nalaze se prirodni brojevi, manji od 100. To su količine bombona koje su dobila djeca od prvog do [i]N[/i]-tog.

[b]IZLAZNI PODACI[/b]

Ako se postupak u nekom trenutku zaustavlja, u jedini redak ispiši završni niz količina bombona, odvojene razmakom. Ako postupak traje beskonačno, ispiši samo riječ "INFINITY".

[b]PRIMJERI TEST PODATAKA[/b]

[b]ulaz[/b]
2
5
6
[b]izlaz[/b]
INFINITY

[b]ulaz[/b]
5
14
6
8
10
12
[b]izlaz[/b]
14 12 16 20 12
[/quote]

Kao što vidite sastavljači zadataka su se zbilja potrudili, čak i oko humora. (Odgajateljice, ne brini! Lokalni izbori se bliže i gradonačelnik će sigurno platiti beskonačnu narudžbu bombona.) Osim ovog zadatka sedmašima su zadali još dva lakša zadatka, a ovaj je zanimljiv jer ima dvije razine. Prvo treba razumjeti algoritam po kojem odgajateljica postupa dok ima uplakane djece - nazovimo ga [b]algoritam za odplakivanje[/b]. Recimo da su početne količine bombona spremljene u niz [i]a[/i].

[code:1]1. Pronađi minimalni element niza a.
2. Ako je jedinstven, pomnoži minimalni element s 2 i vrati se na korak 1; inače ispiši niz.
[/code:1]

Problem je što za neke nizove algoritam ne završava za konačno mnogo koraka. To treba prepoznati i ispisati poruku "INFINITY". Zadatak bi se mogao riješiti "inžinjerskim pristupom" (pokrenemo algoritam za odplakivanje i zaustavimo ga ako ne završi u nekom vremenu), ali nismo FER-ovci nego matematičari i nećemo se time zadovoljiti. Dakle, tražimo karakterizaciju nizova za koje odplakivanje traje beskonačno, i to takvu koja se može provjeriti u konačno mnogo koraka! Neka je [i]h[/i]([i]a[/i])=1 ako algoritam odplakivanja za niz [i]a[/i] završava u konačno mnogo koraka, a [i]h[/i]([i]a[/i])=0 inače. Kad smislimo konačan algoritam za izračunavanje funkcije [i]h[/i], ovako izgleda rješenje zadatka.

[code:1]1. Učitaj niz a.
2. Izračunaj h(a). Ako je h(a)=0 ispiši "INFINITY", a inače izvedi algoritam za odplakivanje.
[/code:1]

Tko se prvi dosjeti algoritma za [i]h[/i]([i]a[/i]) i opiše ga ovdje na forumu, dobiva peticu iz zalaganja i celebrity status na usmenom :D (Molim sve koji nisu upisali Osnove algoritama 2016./17. da [b]ne[/b] pišu rješenje!) Inače, ovo je specijalni slučaj takozvanog [url=https://en.wikipedia.org/wiki/Halting_problem]halting problema[/url]. Treba algoritamski provjeriti završava li zadani algoritam sa zadanim ulazom u konačno mnogo koraka, ili se izvodi beskonačno. U specijalnom slučaju algoritma za odplakivanje to je moguće napraviti, ali općenito je taj problem [b]neodlučiv[/b]. To znači da [b]ne postoji[/b] algoritam za izračunavanje generalizirane funkcije [i]h[/i]. Svih mogućih programa i svih ulaznih podata ima prebrojivo beskonačno, tj. možemo ih indeksirati prirodnim brojevima. Funkcija [i]h[/i] definirana je ovako: [i]h[/i]([i]m[/i],[i]n[/i])=1 ako [i]m[/i]-ti program s [i]n[/i]-tim ulaznim podacima završava u konačno koraka, a [i]h[/i]([i]m[/i],[i]n[/i])=0 inače.

Alan Turing je 1936. dokazao da ne postoji algoritam za tako generaliziranu funkciju [i]h[/i]. Dokaz podsjeća na paradoks o brici: "Brico brije sve ljude u selu koji ne briju sami sebe. Tko brije bricu?". Ako brico brije sam sebe, onda se ne brije. Ako se ne brije, onda se brije. Dakle, takav brico ne postoji. Slično, pretpostavimo da možemo napisati program koji izračunava [i]h[/i]([i]m[/i],[i]n[/i]). Promotrimo ovaj program:

[code:1]1. Učitaj m.
2. Izračunaj h(m,m). Ako je h(m,m)=1, onda uđi u beskonačnu petlju, a inače stani.
[/code:1]

Neka je to [i]m[/i]-ti program. Što je [i]h[/i]([i]m[/i],[i]m[/i])? Ako je 1, program će ući u beskonačnu petlju i trebalo bi biti 0, a ako je 0 stat će i trebalo bi biti 1. Dakle, takav program ne postoji, tj. funkcija [i]h[/i] nije izračunljiva.

U zadatku s natjecanja treba smisliti algoritam za restrikciju funkcije [i]h[/i] kad se za prvu varijablu uvrsti broj koji odgovara algoritmu za odplakivanje.
Jučer je održano natjecanje iz informatike (školska razina). Za 7. razred OŠ postavljen je ovaj zanimljivi zadatak.

Citat:
Zadatak: Bomboni (90 bodova)

U dječjem vrtiću "Tulipan" odgajateljica je djeci podijelila bombone. Ali, jao! Neka djeca dobila su manje bombona od drugih.

Reći ćemo da je neko dijete uplakano ako svako drugo dijete ima strogo više bombona od njega. Odgajateljica je slaba na suze pa se i sama rasplače kad vidi uplakano dijete. Ona tada posegne za golemom vrećom bombona i uplakanom djetetu udvostruči broj bombona. Na primjer, ako uplakano dijete ima 3 bombona, dobit će još 3 bombona pa će imati 6 bombona.

Ako se tada opet pojavi neko uplakano dijete, odgajateljica će učiniti isto, i taj će se postupak ponavljati dok god postoji bilo koje uplakano dijete. Ako u nekom trenutku nijedno dijete više nije uplakano, što znači da nijedno dijete nema manje bombona od svakog drugog djeteta, postupak se zaustavlja. Moguće je i da se postupak ponavlja beskonačno, a u tom će slučaju odgajateljica naručivati nove bombone iz tvornice kad god joj ponestane bombona. (Još nije poznato kako će ih platiti.)

Napiši program koji, za dane početne količine bombona svakog djeteta, ispisuje njihove konačne količine bombona ako se postupak zaustavi, ili riječ "INFINITY" ako će postupak trajati beskonačno.

ULAZNI PODACI

U prvom retku nalazi se prirodan broj N (2≤N≤10), broj djece. U sljedećih N redaka nalaze se prirodni brojevi, manji od 100. To su količine bombona koje su dobila djeca od prvog do N-tog.

IZLAZNI PODACI

Ako se postupak u nekom trenutku zaustavlja, u jedini redak ispiši završni niz količina bombona, odvojene razmakom. Ako postupak traje beskonačno, ispiši samo riječ "INFINITY".

PRIMJERI TEST PODATAKA

ulaz
2
5
6
izlaz
INFINITY

ulaz
5
14
6
8
10
12
izlaz
14 12 16 20 12


Kao što vidite sastavljači zadataka su se zbilja potrudili, čak i oko humora. (Odgajateljice, ne brini! Lokalni izbori se bliže i gradonačelnik će sigurno platiti beskonačnu narudžbu bombona.) Osim ovog zadatka sedmašima su zadali još dva lakša zadatka, a ovaj je zanimljiv jer ima dvije razine. Prvo treba razumjeti algoritam po kojem odgajateljica postupa dok ima uplakane djece - nazovimo ga algoritam za odplakivanje. Recimo da su početne količine bombona spremljene u niz a.

Kod:
1. Pronađi minimalni element niza a.
2. Ako je jedinstven, pomnoži minimalni element s 2 i vrati se na korak 1; inače ispiši niz.


Problem je što za neke nizove algoritam ne završava za konačno mnogo koraka. To treba prepoznati i ispisati poruku "INFINITY". Zadatak bi se mogao riješiti "inžinjerskim pristupom" (pokrenemo algoritam za odplakivanje i zaustavimo ga ako ne završi u nekom vremenu), ali nismo FER-ovci nego matematičari i nećemo se time zadovoljiti. Dakle, tražimo karakterizaciju nizova za koje odplakivanje traje beskonačno, i to takvu koja se može provjeriti u konačno mnogo koraka! Neka je h(a)=1 ako algoritam odplakivanja za niz a završava u konačno mnogo koraka, a h(a)=0 inače. Kad smislimo konačan algoritam za izračunavanje funkcije h, ovako izgleda rješenje zadatka.

Kod:
1. Učitaj niz a.
2. Izračunaj h(a). Ako je h(a)=0 ispiši "INFINITY", a inače izvedi algoritam za odplakivanje.


Tko se prvi dosjeti algoritma za h(a) i opiše ga ovdje na forumu, dobiva peticu iz zalaganja i celebrity status na usmenom Very Happy (Molim sve koji nisu upisali Osnove algoritama 2016./17. da ne pišu rješenje!) Inače, ovo je specijalni slučaj takozvanog halting problema. Treba algoritamski provjeriti završava li zadani algoritam sa zadanim ulazom u konačno mnogo koraka, ili se izvodi beskonačno. U specijalnom slučaju algoritma za odplakivanje to je moguće napraviti, ali općenito je taj problem neodlučiv. To znači da ne postoji algoritam za izračunavanje generalizirane funkcije h. Svih mogućih programa i svih ulaznih podata ima prebrojivo beskonačno, tj. možemo ih indeksirati prirodnim brojevima. Funkcija h definirana je ovako: h(m,n)=1 ako m-ti program s n-tim ulaznim podacima završava u konačno koraka, a h(m,n)=0 inače.

Alan Turing je 1936. dokazao da ne postoji algoritam za tako generaliziranu funkciju h. Dokaz podsjeća na paradoks o brici: "Brico brije sve ljude u selu koji ne briju sami sebe. Tko brije bricu?". Ako brico brije sam sebe, onda se ne brije. Ako se ne brije, onda se brije. Dakle, takav brico ne postoji. Slično, pretpostavimo da možemo napisati program koji izračunava h(m,n). Promotrimo ovaj program:

Kod:
1. Učitaj m.
2. Izračunaj h(m,m). Ako je h(m,m)=1, onda uđi u beskonačnu petlju, a inače stani.


Neka je to m-ti program. Što je h(m,m)? Ako je 1, program će ući u beskonačnu petlju i trebalo bi biti 0, a ako je 0 stat će i trebalo bi biti 1. Dakle, takav program ne postoji, tj. funkcija h nije izračunljiva.

U zadatku s natjecanja treba smisliti algoritam za restrikciju funkcije h kad se za prvu varijablu uvrsti broj koji odgovara algoritmu za odplakivanje.



_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail Posjetite Web stranice
hstefek
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 13. 02. 2017. (17:44:25)
Postovi: (1)16
Sarma = la pohva - posuda
= 0 - 0

PostPostano: 17:51 pon, 13. 2. 2017    Naslov: Citirajte i odgovorite

[code:1]
#include<stdio.h>
#include<math.h>

int minimal(int *a,int n)
{
int min=a[0],i;
for (i=0;i<n;i++) if (a[i]<min) min=a[i];
return min;
}

int visekratnik(int a,int b)
{
int pom=b;
while (a>pom)
{
pom*=2;
}
if (a==pom) return 1;
return 0;
}

int check(int *a,int n, int min)
{
int i;
for (i=0;i<n;i++)
if(a[i]!=min&&visekratnik(a[i],min)==1) return 0;
if (n>2)
{
int *b=a;
for (i=0;i<n;i++) if (b[i]==min) b[i]*=2;
int min1=b[0];
for (i=0;i<n;i++) if (b[i]<min1) min1=b[i];
if ((2*min)>=min1) return 0;
}
return 1;
}

int unique(int *a,int n, int min)
{
int br=-1,i;
for (i=0;i<n;i++) if (a[i]==min) br++;
return br;
}

void double_min(int *a,int n, int min)
{
int i;
for (i=0;i<n;i++) if (a[i]==min) a[i]*=2;
}

int main(void)
{
int n,a[n],i,test=0,min;
scanf("%d\n", &n );
for (i=0;i<n;i++)
scanf("%d\n", &a[i]);
min=minimal(a,n);
while(unique(a,n,min)==0)
{
test=check(a,n,min);
if (test==1) break;
double_min(a,n,min);
min=minimal(a,n);
}
if (test==1) printf("INFINITY\n");
else
for (i=0;i<n;i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
[/code:1]

Poštovani profesore, algoritam (cijeli program) napisan u C-u. Radi za testne primjere i one koje sam ja testirao. Ako slučajno naletite na pogrešku javite mi.

Kod:

#include<stdio.h>
#include<math.h>

int minimal(int *a,int n)
{
  int min=a[0],i;
  for (i=0;i<n;i++) if (a[i]<min) min=a[i];
  return min;
}

int visekratnik(int a,int b)
{
  int pom=b;
  while (a>pom)
  {
    pom*=2;
  }
  if (a==pom) return 1;
  return 0;
}

int check(int *a,int n, int min)
{
  int i;
  for (i=0;i<n;i++)
    if(a[i]!=min&&visekratnik(a[i],min)==1) return 0;
  if (n>2)
  {
    int *b=a;
    for (i=0;i<n;i++) if (b[i]==min) b[i]*=2;
    int min1=b[0];
    for (i=0;i<n;i++) if (b[i]<min1) min1=b[i];
    if ((2*min)>=min1) return 0;
  }
  return 1;
}

int unique(int *a,int n, int min)
{
  int br=-1,i;
  for (i=0;i<n;i++) if (a[i]==min) br++;
  return br;
}

void double_min(int *a,int n, int min)
{
  int i;
  for (i=0;i<n;i++) if (a[i]==min) a[i]*=2;
}

int main(void)
{
  int n,a[n],i,test=0,min;
  scanf("%d\n", &n );
  for (i=0;i<n;i++)
      scanf("%d\n", &a[i]);
  min=minimal(a,n);
  while(unique(a,n,min)==0)
  {
    test=check(a,n,min);
    if (test==1) break;
    double_min(a,n,min);
    min=minimal(a,n);
  }
  if (test==1) printf("INFINITY\n");
  else
    for (i=0;i<n;i++) printf("%d ", a[i]);
    printf("\n");
  return 0;
}


Poštovani profesore, algoritam (cijeli program) napisan u C-u. Radi za testne primjere i one koje sam ja testirao. Ako slučajno naletite na pogrešku javite mi.



[Vrh]
Korisnički profil Pošaljite privatnu poruku
Prethodni postovi:   
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji 2. godine -> Osnove algoritama Vremenska zona: GMT + 01:00.
Stranica 1 / 1.

 
Forum(o)Bir:  
Možete otvarati nove teme.
Možete odgovarati na postove.
Ne možete uređivati Vaše postove.
Ne možete izbrisati Vaše postove.
Ne možete glasovati u anketama.
You cannot attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2002 phpBB Group
Theme created by Vjacheslav Trushkin
HR (Cro) by Ančica Sečan