---

Hej!

Jeg er ikke lige så stærk på det matematiske område og har brug for
noget hjælp her:

Jeg har en række tal a1 <> a2 <> ... <> aN - dvs. alle tallene er
forskellige.

Desuden har jeg et tal S

På hvilken måde kan jeg nemmest afgøre om der findes en række heltal h1
... hN, hvor det gælder at:

h1 * a1 + h2 * a2 + ... + hN * aN = S

Jeg skal ikke finde en eller flere mulige kombinationer af tallene h1
.... hN, men blot afgøre om der findes en kombination eller ej.

Er det muligt på en nem måde? Man kan vel starte med S modulus aN, og så
tage resten og bruge den på S modulus (aN - 1) osv, osv, men det kræver
en del iterationer.

Mvh
Thomas

---

"Thomas Daugaard" <noreply@toemail.th> skrev i en meddelelse news:cgv85i$1jv9$1@news.cybercity.dk...
>
> På hvilken måde kan jeg nemmest afgøre om der findes en række heltal h1
> .. hN, hvor det gælder at:
>
> h1 * a1 + h2 * a2 + ... + hN * aN = S
>
> Jeg skal ikke finde en eller flere mulige kombinationer af tallene h1
> ... hN, men blot afgøre om der findes en kombination eller ej.
>
> Er det muligt på en nem måde?

Du kan se om S er et multiplum af gcd(a1,a2 ... an)

Mvh
Martin

---

Martin Larsen wrote:

> Du kan se om S er et multiplum af gcd(a1,a2 ... an)

Det er vel ikke nok?

gcd(3, 5) = 1

Hvis S er 7 ... så er det vel et multiplum af 1? Men der findes ikke en
sådan kombination, jeg taler om.

Misforstår jeg noget?

Mvh
Thomas

---

Thomas Daugaard <noreply@toemail.th> writes:

> gcd(3, 5) = 1
>
> Hvis S er 7 ... så er det vel et multiplum af 1? Men der findes ikke
> en sådan kombination, jeg taler om.

7 = 4*3+(-1)*5. Du skrev ikke at heltallene skulle være positive.

--
Stefan Holm
"The female clitoris?

---

Stefan Holm wrote:
> Thomas Daugaard <noreply@toemail.th> writes:
>>gcd(3, 5) = 1
>>Hvis S er 7 ... så er det vel et multiplum af 1? Men der findes ikke
>>en sådan kombination, jeg taler om.
> 7 = 4*3+(-1)*5. Du skrev ikke at heltallene skulle være positive.

Nej ... det skal de ... altså >= 0


Mvh
Thomas

---

Scripsit Thomas Daugaard <noreply@toemail.th>
> Stefan Holm wrote:

> > Du skrev ikke at heltallene skulle være positive.

> Nej ... det skal de ... altså >= 0

I så fald er dit problem NP-komplet, og du skal derfor ikke forvente
at kunne finde en effektiv løsningsalgoritme.

Bevisskitse: Først og fremmest er det let at se at vi kan erstatte
"går op i S" med "lig med S" i beskrivelsen af dit problem; det ændrer
ikke på svaret.

Hvis du begrænser dit problem yderligere til at koefficienterne skal
være enten 0 eller 1, får du Delmængdesumproblemet (også af og til
omtalt som Rygsækproblemet), som velkendt er NP-komplet.

Hvis jeg har et orakel for dit problem kan jeg løse det traditionelle
Delmængdesumproblem: Lad de givne tal være XXXX, YYYY, Z og WWWW og
den ønskede sum være SSSSS. Skriv dette problem om til følgende
instans af dit:

h1 * 100XXXX0001 + h5 * 10000000001
+ h2 * 100YYYY0010 + h6 * 10000000010
+ h3 * 100Z0100 + h7 * 10000000100
+ h4 * 100WWWW1000 + h8 * 10000001000
= 40SSSSS1111

De forreste ettaller gør at summen af h'erne højst kan være 4. For nu
de *bageste* ettaller til at stemme må h1+h5 = 1 (mod 10), men det
betyder at h1+h5 må være 1, for 11, 21, etc giver for stor en sum.
Altså er netop netop ét af h1 og h5 1 og den anden koefficient 0.
Tilsvarende får vi h2+h6 = h3+h7 = h4+h8 = 1. Det vil sige at denne
instans af dit problem må have samme svar som den oprindelige instans
af Delmængdesumproblemet.

--
Henning Makholm "Jeg køber intet af Sulla, og selv om uordenen griber
planmæssigt om sig, så er vi endnu ikke nået dertil hvor
ordentlige mennesker kan tillade sig at stjæle slaver fra
hinanden. Så er det ligegyldigt, hvor stærke, politiske modstandere vi er."

---

Henning Makholm wrote:

> Scripsit Thomas Daugaard <noreply@toemail.th>
>>>Du skrev ikke at heltallene skulle være positive.
>>Nej ... det skal de ... altså >= 0
> I så fald er dit problem NP-komplet, og du skal derfor ikke forvente
> at kunne finde en effektiv løsningsalgoritme.
>
> Bevisskitse: Først og fremmest er det let at se at vi kan erstatte
> "går op i S" med "lig med S" i beskrivelsen af dit problem; det ændrer
> ikke på svaret.
>
> Hvis du begrænser dit problem yderligere til at koefficienterne skal
> være enten 0 eller 1, får du Delmængdesumproblemet (også af og til
> omtalt som Rygsækproblemet), som velkendt er NP-komplet.
>
> Hvis jeg har et orakel for dit problem kan jeg løse det traditionelle
> Delmængdesumproblem: Lad de givne tal være XXXX, YYYY, Z og WWWW og
> den ønskede sum være SSSSS. Skriv dette problem om til følgende
> instans af dit:
>
> h1 * 100XXXX0001 + h5 * 10000000001
> + h2 * 100YYYY0010 + h6 * 10000000010
> + h3 * 100Z0100 + h7 * 10000000100
> + h4 * 100WWWW1000 + h8 * 10000001000
> = 40SSSSS1111
>
> De forreste ettaller gør at summen af h'erne højst kan være 4. For nu
> de *bageste* ettaller til at stemme må h1+h5 = 1 (mod 10), men det
> betyder at h1+h5 må være 1, for 11, 21, etc giver for stor en sum.
> Altså er netop netop ét af h1 og h5 1 og den anden koefficient 0.
> Tilsvarende får vi h2+h6 = h3+h7 = h4+h8 = 1. Det vil sige at denne
> instans af dit problem må have samme svar som den oprindelige instans
> af Delmængdesumproblemet.

"My cat's name is Mittens."

Jeg er ikke stærk i matematik, så jeg forstår ikke alle de begreber du
anvender, men jeg tror dig på dit ord :) Mange tak for svaret, som jeg i
hvert fald kan bruge til at kaste i hovedet på mine kollegaer, hvis de
påstår at kunne løse problemet nemmere end mig.

Jeg skal nemlig bruge det i noget software, og her er der i dette
tilfælde så lille afstand mellem S og a'erne at en numerisk udregning
tilsyneladende kan lade sig gøre.

Tak igen,
Thomas

---

Scripsit Thomas Daugaard <noreply@toemail.th>

> Jeg er ikke stærk i matematik, så jeg forstår ikke alle de begreber du
> anvender, men jeg tror dig på dit ord :)

Undskyld. Det er i øvrigt mere datalogi end matematik, men i mørke er
alle katte jo grå...

> Mange tak for svaret, som jeg i hvert fald kan bruge til at kaste i
> hovedet på mine kollegaer, hvis de påstår at kunne løse problemet
> nemmere end mig.

Det er det ikke nødvendigvis godt til. Jeg har vist at der med stor
sikkerhed ikke er nogen *god* løsning til problemet i almindelighed
(hvor "god" betyder at dens køretid ikke vokser alt for voldsomt
efterhånden som man begynder at have flere a'er eller længere tal).

Men det betyder ikke at man ikke kan finde en *mindre dårlig* løsning
end hvad end du nu ender med at brygge sammen.

> Jeg skal nemlig bruge det i noget software, og her er der i dette
> tilfælde så lille afstand mellem S og a'erne at en numerisk udregning
> tilsyneladende kan lade sig gøre.

Aha - hvis du ved at der er et fast lille tal K så det mindste a altid
er større end S/K, er problemet (for et fast K) ikke længere
NP-hårdt. Dermed ikke sagt at jeg kan hitte på en bedre algoritme end
at prøve alle muligheder, men "alle muligheder" bliver færre hvis man
giver op på forhånd når summen overstiger S.

--
Henning Makholm "You propose to avoid dying? I will be
interested to hear the method you plan for this endeavour."

---

Henning Makholm wrote:
> Scripsit Thomas Daugaard <noreply@toemail.th>
>>Jeg er ikke stærk i matematik, så jeg forstår ikke alle de begreber du
>>anvender, men jeg tror dig på dit ord :)
> Undskyld. Det er i øvrigt mere datalogi end matematik, men i mørke er
> alle katte jo grå...

Jeg må næsten komplimentere dig for denne elegante tilsvining ...

>>Jeg skal nemlig bruge det i noget software, og her er der i dette
>>tilfælde så lille afstand mellem S og a'erne at en numerisk udregning
>>tilsyneladende kan lade sig gøre.
> Aha - hvis du ved at der er et fast lille tal K så det mindste a altid
> er større end S/K, er problemet (for et fast K) ikke længere
> NP-hårdt. Dermed ikke sagt at jeg kan hitte på en bedre algoritme end
> at prøve alle muligheder, men "alle muligheder" bliver færre hvis man
> giver op på forhånd når summen overstiger S.

I hvert fald kan jeg fortsætte med min hidtidige løsning med rimelig god
samvittighed. Den kører også helt fint, men det ville være trist, hvis
nu der eksisterede en meget nem matematisk løsning lige ved siden af mig
i det mørke, jeg famler i.

Mvh
Thomas

---

Scripsit Thomas Daugaard <noreply@toemail.th>
> Henning Makholm wrote:
> > Scripsit Thomas Daugaard <noreply@toemail.th>

> >>Jeg er ikke stærk i matematik, så jeg forstår ikke alle de begreber du
> >>anvender, men jeg tror dig på dit ord :)

> > Undskyld. Det er i øvrigt mere datalogi end matematik, men i mørke er
> > alle katte jo grå...

> Jeg må næsten komplimentere dig for denne elegante tilsvining ...

Tilsvining? Sådan var det bestemt ikke ment. Du skal vist have
justeret dit pyrometer.

--
Henning Makholm "PROV EN FORFRISKNING FRISKLAIL DEM"

---

Henning Makholm wrote:

> Scripsit Thomas Daugaard <noreply@toemail.th>
>>Jeg må næsten komplimentere dig for denne elegante tilsvining ...
> Tilsvining? Sådan var det bestemt ikke ment. Du skal vist have
> justeret dit pyrometer.

Hehe ... det kan godt være ;) Nogle gange er det lidt for nemt at
misforstå her i nyhedsgrupperne. Eller også er det bare fordi jeg er
lidt træt af at jeg ikke selv kunne vise det ... !!

Mvh
Thomas

---

Thomas Daugaard wrote:
>
> >>Jeg er ikke stærk i matematik, så jeg forstår ikke alle de begreber du
> >>anvender, men jeg tror dig på dit ord :)

> > Undskyld. Det er i øvrigt mere datalogi end matematik, men i mørke er
> > alle katte jo grå...
>
> Jeg må næsten komplimentere dig for denne elegante tilsvining ...

Datalogi, er det ikke bare én ud af mange underdiscipliner inden for
matematikken? Er det ikke lidt »krukket« at dataloger ikke vil være
en delmængde af matematikere?

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Scripsit Jeppe Stig Nielsen <mail@jeppesn.dk>

> Datalogi, er det ikke bare én ud af mange underdiscipliner inden for
> matematikken?

Teoretisk datalogi støder direkte op til matematik, og skillelinjen er
i et vist omfang blot et spørgsmål om konvention. Områder som formel
logik og kategoriteori eller grafteori eller numerisk analyse kan i
praksis betragtes som fælles grænselande mellem datalogi og matematik.

Men i den anden ende af datalogien finder vi områder som
menneske-maskin-interaktion eller konstruktion af styresystemer som
kun bærer ganske ringe præg af matematik andet end som værktøjsfag.

Der er et kontinuum af datalogiske discipliner (og så har jeg endda
slet ikke nævnt alle de anvendte hjørner af datalogien), og selvom den
ene ende af kontinuet overlapper med matematik vil det næppe være
praktisk at nægte at skelne overhovedet.

> Er det ikke lidt »krukket« at dataloger ikke vil være en delmængde
> af matematikere?

Tja, personligt er jeg en temmelig teoretisk datalog, og jeg ville
ikke have problemer med at kalde hvad jeg laver, for en form for
matematik. Men jeg formoder at de rigtige matematikere vil blive
fornærmede hvis jeg begynder at kalde mig for matematiker.

--
Henning Makholm "Man vælger jo selv sine forbilleder."

---

"Henning Makholm" <henning@makholm.net> skrev i en meddelelse news:87fz602xef.fsf@kreon.lan.henning.makholm.net...
>
> Tja, personligt er jeg en temmelig teoretisk datalog, og jeg ville
> ikke have problemer med at kalde hvad jeg laver, for en form for
> matematik. Men jeg formoder at de rigtige matematikere vil blive
> fornærmede hvis jeg begynder at kalde mig for matematiker.
>
Med en begyndende fremkomst af kvantecomputeren skal
datalogerne vel også være kvantefysikere?

Mvh
Martin

---

Martin Larsen wrote:
>
> Med en begyndende fremkomst af kvantecomputeren skal
> datalogerne vel også være kvantefysikere?

Det bliver i så fald nogle andre dataloger end mig. Ét semester kursus i
kvantecomputere (med tilhørende gennemlæsning af Nielsen&Chuangs
"Quantum Computation and Quantum Information") var rigeligt til at få
mit hoved til at bryde spontant ud i flammer.

--
mvh.
Karsten Strandgaard Jørgensen
http://www.daimi.au.dk/~karsten

---

"Martin Larsen" <mlarsen@post7.tele.dk> writes:

> "Henning Makholm" <henning@makholm.net> skrev i en meddelelse news:87fz602xef.fsf@kreon.lan.henning.makholm.net...
> >
> > Tja, personligt er jeg en temmelig teoretisk datalog, og jeg ville
> > ikke have problemer med at kalde hvad jeg laver, for en form for
> > matematik. Men jeg formoder at de rigtige matematikere vil blive
> > fornærmede hvis jeg begynder at kalde mig for matematiker.
> >
> Med en begyndende fremkomst af kvantecomputeren skal
> datalogerne vel også være kvantefysikere?

Ikke mere end nuværende dataloger behøver være halvlederfysikere. En
datalog skal bare bruge en programmeringsmodel, og det er kendt, hvad
denne er for kvantecomputere (nemlig unitære operationer).

   Torben

---

"Torben Ægidius Mogensen" <torbenm@diku.dk> skrev i en meddelelse news:7z8ybnd064.fsf@pc-032.diku.dk...
> "Martin Larsen" <mlarsen@post7.tele.dk> writes:
>
> > Med en begyndende fremkomst af kvantecomputeren skal
> > datalogerne vel også være kvantefysikere?
>
> Ikke mere end nuværende dataloger behøver være halvlederfysikere. En
> datalog skal bare bruge en programmeringsmodel, og det er kendt, hvad
> denne er for kvantecomputere (nemlig unitære operationer).
>
En kvantedatalog vil automatisk have et vist kendskab til
kvantefysik. Men du har vel ret i at det behøver man ikke
at fortælle ham

Mvh
Martin

---

Thomas Daugaard <noreply@toemail.th> writes:

>>>Jeg er ikke stærk i matematik, så jeg forstår ikke alle de begreber du
>>>anvender, men jeg tror dig på dit ord :)
>> Undskyld. Det er i øvrigt mere datalogi end matematik, men i mørke er
>> alle katte jo grå...
>
> Jeg må næsten komplimentere dig for denne elegante tilsvining ...

Tilsvining?
½
--
Peter Makholm | If you can't do any damage as root, are you still
peter@makholm.net | really root?
http://hacking.dk | -- Derek Gladding about SELinux

---

Peter Makholm wrote:
> Thomas Daugaard <noreply@toemail.th> writes:
>>>>Jeg er ikke stærk i matematik, så jeg forstår ikke alle de begreber du
>>>>anvender, men jeg tror dig på dit ord :)
>>>Undskyld. Det er i øvrigt mere datalogi end matematik, men i mørke er
>>>alle katte jo grå...
>>Jeg må næsten komplimentere dig for denne elegante tilsvining ...
> Tilsvining?

Jeg misforstod muligvis, men det lyder som en slags tilsvining.

Jeg er dog stadig meget glad for svaret :)

Mvh
Thomas

---

---

> Kan du fortælle mere om unitære operationer? Hvad hedder det i øvrigt på
> engelsk?
>
>
>>   Torben

Hej Torben

Kig på:

http://mathworld.wolfram.com/Unitary.html

og

http://en.wikipedia.org/wiki/Unitary

mvh/Glenn

-

---

>
> Er det muligt på en nem måde?

Jeg er sikker på at genetiske algoritmer er det magiske ord. Her er et link
til en side jeg selv har fundet ret interessant:

http://www.ai-junkie.com/ga/intro/gat1.html

Hans eksempel på hvordan man kan kode sine problemer med chromosomer og så
lade evolutions regler finde en løsning
til dig, minder meget om det problem du stiller her.

Mvh. Rasmus