10 Algoritmiske problemer ennå å løse

Algoritmer har faktisk eksistert i århundrer, så du tror at forskere ville ha oppdaget og løst hver algoritme nå. Dessverre er motsatt sant. Å løse en bestemt algoritme presenterer ofte noen flere spørsmål som algoritmen ikke løser, og det virket ikke tydelig før noen kom opp med løsningen.

Algoritmer er en rekke trinn som brukes til å løse et problem, og du bør ikke forveksle dem med andre enheter, for eksempel ligninger. En algoritme er aldri en løsning på jakt etter et problem. Ingen ville opprette en rekke tiltak for å løse et problem som ikke eksisterer (eller kanskje aldri eksisterer).

Denne listen handler om algoritmiske problemer som ville tjene en hensikt hvis noen skulle finne en løsning for dem.

Håndtere tekstsøk

Mange tekstsøk involverer bruk av vanlige uttrykk - en slags stenografi som forteller datamaskinen hva du skal finne. Grammatikken som brukes til det vanlige uttrykket avhenger av språket eller applikasjonen, men du finner vanlige uttrykk som brukes på flere steder, inkludert tekstbehandlingsprogrammer, e-postprogrammer, søkedialoger og i alle andre steder hvor du må gi nøyaktig søk Vilkår for en rekke tekstartikler.

En av de nåværende problemene med regulære uttrykk er at det virker som om hvert applikasjonsmiljø har et lignende sett med regler, men med akkurat nok forskjeller for å lage et søkeord hardt. Det generaliserte stjernestørrelsesproblemet søker å oppdage om det finnes en generell syntetisk syntetisk syntaks. I så fall vil den resulterende algoritmen gjøre det mulig for noen å lære bare én metode for å lage vanlige uttrykk for å utføre søk.

Differentierende ord

Når du arbeider med tegn, ser en datamaskin tall, ikke bokstaver. Tallene er egentlig bare en serie med 0s og 1s til datamaskinen og har egentlig ingen mening. Kombinere tegn i strenger gjør bare serien på 0s og 1s lenger. Følgelig kan sammenligning av to strenger, noe som et menneske kan gjøre med et øyeblikk, ta tid i en datamaskin, og det er sannsynlig at forvirring er mellom konjugater. For eksempel, med mindre du er forsiktig med å konstruere algoritmen, kan en datamaskin forvirre enlist og lytte. Det er viktigere at datamaskinen krever tid for å skille forskjellen mellom de to. Det separerende ordproblemet søker å finne den minste (og raskeste) mulige algoritmen (en deterministisk endelig automat, DFN, i dette tilfellet) for å utføre ordseparasjon.Målet er å akseptere ett ord og avvise en annen, gitt to ord av en bestemt lengde.

Bestemme om et program vil avsluttes

Et av problemene som Alan Turing foreslo 1936, er spørsmålet om en algoritme, gitt en beskrivelse av et program og en inngang, kunne avgjøre om programmet til slutt skulle stoppe (stoppproblem). Når du arbeider med et enkelt program, er det i mange tilfeller enkelt å avgjøre om programmet vil stoppe eller fortsette å kjøre i en endeløs sløyfe. Men når programkompleksiteten øker, blir det vanskeligere å bestemme resultatet av å kjøre programmet med en gitt inngang. En Turing-maskin kan ikke gjøre denne bestemmelsen; Resultatet er buggy kode med uendelige løkker. Ingen mengde testing som bruker dagens teknologi, kan løse dette problemet.

En hyperkomputer er en datamodell som går utover Turing-maskinen for å løse problemer som stoppproblemet. Imidlertid er slike maskiner ikke mulige ved bruk av dagens teknologi. Hvis de var mulige, ville du kunne spørre dem alle slags imponderables at datamaskiner ikke kan svare på øyeblikket. Denne artikkelen gir deg en god ide om hva som ville skje hvis noen kunne løse dette problemet.

Opprette og bruke enveisfunksjoner

En enkelveisfunksjon er en funksjon som er enkel å bruke for å få svar i en retning, men nesten umulig å bruke med det omvendte svaret. Med andre ord bruker du en enveisfunksjon for å skape noe som en hash som ser ut som en del av en løsning for kryptering, personlig identifisering, godkjenning eller andre datasikkerhetsbehov.

Eksistensen av en enveisfunksjon er mindre mysterium og mer et spørsmål om bevis. Mange telekommunikasjons-, e-handels- og e-banksystemer er for tiden avhengige av funksjoner som angivelig er en måte, men ingen vet virkelig om de egentlig er en måte. Eksistensen av en enveisfunksjon er for tiden en hypotese, ikke en teori. Hvis noen kunne bevise at en enveisfunksjon eksisterer, ville datasikkerhetsproblemer være enklere å løse fra et programmeringsperspektiv.

Multiplikere virkelig store tall

Egentlig finnes store tall på mange steder. For eksempel, vurder å utføre beregningene som inkluderer avstander til Mars, eller kanskje Pluto. Metoder eksisterer for øyeblikket for å utføre multiplikasjon på virkelig store tall, men de har en tendens til å være sakte fordi de krever at flere operasjoner skal fullføres. Problemet oppstår når tallene er for store til å passe inn i prosessorens register. På det tidspunktet må multiplikasjonen forekomme i mer enn ett trinn, noe som bremser tingene betydelig. De nåværende løsningene inkluderer:

• Gauss komplekse multipliseringsalgoritme
• Karatsuba multiplikasjon
• Toom-Cook
• Fourier transformasjonsmetoder

Selv om mange av de tilgjengelige metodene frembringer akseptable resultater, tar de alle tid og når du har mange beregninger å utføre, kan tidsproblemet bli kritisk. Derfor er stort antall multiplikasjoner en av de problemene som krever en bedre løsning enn de som er tilgjengelige i dag.

Deler en ressurs likt

Det kan ikke virke vanskelig å dele ressurser, men mennesker, som er misunnelig, kan se at ressursen er ulik delt, med mindre du kan finne en måte å forsikre alle om at divisjonen er virkelig rettferdig. Dette er misunnelsesfritt kake-skjære problem. Selvfølgelig, når du kutter en kake, uansett hvor rettferdig du forsøker å gjøre det, er det alltid oppfatningen at divisjonen er urettferdig. Å skape en rettferdig ressursfordeling er viktig i det daglige livet for å minimere strid mellom interessenter i enhver organisasjon, noe som gjør alle mer effektive.

To løsninger eksisterer allerede for det misunnelsesfrie kakeskjæringsproblemet med et bestemt antall mennesker, men ingen generell løsning eksisterer. Når det er to involverte personer, kutter den første kaken og den andre velger det første stykket. På denne måten er begge parter sikret en lik divisjon. Problemet blir vanskeligere med tre personer, men du kan prøve Selfridge-Conway-løsningen for problemet. Men etter at du kommer til fire personer, finnes det ingen løsning.

Redusere redigering av avstandsberegningstid

redigeringsavstand mellom to strenger er antall operasjoner som kreves for å transformere en streng inn i den andre strengen. Avstandsberegningen dreier seg om Levenshtein avstandsoperasjoner, som er fjerning, innføring eller substitusjon av et tegn i strengen. Denne spesielle teknikken ser bruk i naturlige språkgrensesnitt, DNA-sekvenskvantifisering og alle andre steder hvor du kan ha to lignende strenger som krever en slags sammenligning eller modifikasjon.

En rekke løsninger for dette problemet eksisterer for tiden, alle er ganske sakte. Faktisk tar de fleste eksponentiell tid, så tiden som kreves for å utføre en transformasjon, legger raskt opp til det punktet hvor mennesker kan se pauser i behandlingen av inngangen. Pause er ikke så ille når du bruker et tekstbehandlingsprogram som utfører automatiske ordkontroll og endrer et feilstavet ord til riktig. Men når du bruker tale grensesnitt, kan pausen bli ganske merkbar og få den menneskelige operatøren til å gjøre feil.

Løse problemer raskt

Når maskinlæring tar av og vi teller mer og mer på datamaskiner for å løse problemer, blir spørsmålet om hvor raskt en datamaskin kan løse et problem, kritisk. P versus NP-problemet spør bare om en datamaskin raskt kan løse et problem når det raskt kan bekrefte løsningen på problemet. Med andre ord, hvis datamaskinen med rimelighet kan fastslå at et menneskelig svar på et problem er korrekt i polynomisk tid eller mindre, kan det med andre ord løse problemet selv i polynomisk tid eller mindre?

Dette spørsmålet ble opprinnelig diskutert på 1950-tallet av John Nash i brev til National Security Agency (NSA) og igjen i brev mellom Kurt Gödel og John von Neumann. I tillegg til maskinlæring (og AI generelt) er dette problemet et problem for mange andre felt, inkludert matematikk, kryptering, algoritmforskning, spillteori, multimediebehandling, filosofi og økonomi.

Spille paritetsspillet

I første omgang kan det ikke være alt som er nyttig i det virkelige livet å løse et spill. Ja, spill er morsomme og interessante, men de gir egentlig ikke en bakgrunn for å gjøre noe nyttig - i det minste er det den generelle teorien. Spillteorien kommer imidlertid til spill i et stort antall virkelige scenarier, hvorav mange innebærer komplekse prosesser som noen kan forstå lettere som spill enn som faktiske prosesser. I dette tilfellet hjelper spillet folk til å forstå automatisert verifikasjon og kontrolleresyntese, blant annet. Du kan lese mer om paritetsspillet. Faktisk kan du spille det.

Forståelse av romlige problemer

For å sette dette problemet i kontekst, tenk på flyttekasser rundt i et lager eller noen andre situasjoner der du må vurdere plassen der ting beveger seg. Selvfølgelig, hvis du har mange bokser i et stort lager, og de alle krever en gaffeltruck for å plukke opp, vil du ikke prøve å finne ut hvordan du oppbevarer dem optimalt ved å omorganisere dem på en riktig måte. Det er her du må jobbe gjennom problemet ved å visualisere en løsning.

Men spørsmålet er om alle romlige problemer har en løsning. I så fall tenk på en av disse barnas puslespill som har deg til å sette et bilde sammen ved å skyve de små fliser rundt. Det virker som om en løsning bør eksistere i alle tilfeller, men i noen situasjoner kan et dårlig startpunkt føre til en situasjon som ikke har noen løsning.

Matematikere som Sam Loyd bruker ofte puslespill for å demonstrere komplekse matteproblemer, hvorav noen ikke har noen løsning i dag. Å besøke disse stedene er morsomt fordi du ikke bare får litt gratis underholdning, men også mat for tanker. Problemene som disse oppgavene øker har praktiske applikasjoner, men de presenteres på en morsom måte.