Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI MATEMATIKA U INFORMATICI

Odrediti klase kompleksnosti zadatih problema

Brojni sistemi, Bulova algebra, binarna aritmetika itd.

Odrediti klase kompleksnosti zadatih problema

Postod korisnicko_ime » Ponedeljak, 26. Jun 2017, 13:22

Imam sledeća tri primera:

1. Dat je niz od [inlmath]n[/inlmath] tačaka u dvodimenzionom koordinatnom sistemu i indeksi dviju tačaka iz tog niza. Da li je najkraća zatvorena putanja koja prolazi kroz sve tačke kraća od najkraće putanje između datih dviju tačaka?

2. U socijalnoj mreži od [inlmath]n[/inlmath] osoba, da li najveći skup osoba koje se međusobno poznaju sadrži više od [inlmath]k[/inlmath] osoba?

3. Da li je u električnoj mreži koja povezuje međusobno svaki od [inlmath]n[/inlmath] gradova najkraća dužina dalekovoda koji samo jednom prolazi kroz svaki grad i povezuje sve gradove u zatvorenu mrežu manja od [inlmath]k[/inlmath]?

Odrediti kojim klasama kompleksnosti pripadaju ovi problemi pod pretpostavkom da je [inlmath]P\neq NP[/inlmath].

Kako odrediti kojim klasama kompleksnosti pripadaju ovi problemi? Da li postoji generalizovani postupak?
Šta znači da je [inlmath]P\neq NP[/inlmath]?
 
Postovi: 14
Zahvalio se: 0 puta
Pohvaljen: 0 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+

Povratak na MATEMATIKA U INFORMATICI

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 2 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Subota, 16. Decembar 2017, 15:48 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs