Sommario:
- Gestire le ricerche di testo
- Differenziare le parole
- Determinare se un'applicazione finirà
- Creazione e uso delle funzioni unidirezionali
- Moltiplicazione di numeri veramente grandi
- Dividere ugualmente una risorsa
- Riduzione del tempo di calcolo della distanza di modifica
- Risoluzione rapida dei problemi
- Giocare al gioco della parità
- Capire le questioni spaziali
Video: Map of Computer Science 2024
Gli algoritmi esistono da secoli, quindi penseresti che gli scienziati avrebbero scoperto e risolto ogni algoritmo. Sfortunatamente, è vero il contrario. La soluzione di un particolare algoritmo spesso presenta alcune altre domande che l'algoritmo non risolve e che non sembra apparente fino a quando qualcuno non ha trovato la soluzione.
Gli algoritmi sono una serie di passaggi utilizzati per risolvere un problema e non è necessario confonderli con altre entità, come le equazioni. Un algoritmo non è mai una soluzione in cerca di un problema. Nessuno creerebbe una serie di passaggi per risolvere un problema che non esiste ancora (o potrebbe non esistere mai).
Questo elenco riguarda problemi algoritmici che potrebbero servire a uno scopo se qualcuno dovesse trovare una soluzione per loro.
Gestire le ricerche di testo
Molte ricerche di testo implicano l'uso di espressioni regolari - una sorta di abbreviazione che dice al computer cosa trovare. La grammatica utilizzata per l'espressione regolare dipende dalla lingua o dall'applicazione, ma puoi trovare espressioni regolari utilizzate in numerosi luoghi, inclusi word processor, applicazioni di posta elettronica, finestre di ricerca e in tutti i tipi di altri luoghi in cui è necessario fornire una ricerca precisa termini per una gamma di elementi di testo.
Uno dei problemi attuali con le espressioni regolari è che sembra che ogni ambiente applicativo abbia un insieme simile di regole, ma con le differenze appena sufficienti da rendere difficile la creazione di un termine di ricerca. Il problema di altezza stellare generalizzato cerca di scoprire se esiste una sintassi di espressione regolare generalizzata. In tal caso, l'algoritmo risultante consentirebbe a qualcuno di apprendere un solo metodo per creare espressioni regolari per eseguire ricerche.
Differenziare le parole
Quando si lavora con i caratteri, un computer vede numeri, non lettere. I numeri sono in realtà solo una serie di 0 e 1 al computer e in realtà non hanno alcun significato. La combinazione di caratteri in stringhe rende solo la serie di 0 e 1 più. Di conseguenza, confrontare due stringhe, qualcosa che un umano può fare a colpo d'occhio, può richiedere del tempo all'interno di un computer, e probabilmente c'è confusione tra i coniugati. Ad esempio, a meno che tu non stia attento a costruire l'algoritmo, un computer potrebbe confondere enlist e ascoltare. Più importante, il computer avrebbe bisogno di tempo per distinguere la differenza tra i due. Il problema delle parole di separazione cerca di trovare il più piccolo (e più veloce) algoritmo possibile (un automa finito deterministico, DFN, in questo caso) per eseguire la separazione delle parole.L'obiettivo è accettare una parola e rifiutarne un'altra, con due parole di una lunghezza particolare.
Determinare se un'applicazione finirà
Uno dei problemi che Alan Turing propose nel 1936 è la questione se un algoritmo, data una descrizione di un programma e un input, possa determinare se il programma alla fine si fermerebbe (il problema di interruzione). Quando si lavora con una semplice applicazione, è facile determinare in molti casi se il programma si fermerà o continuerà a funzionare in un ciclo infinito. Tuttavia, con l'aumentare della complessità del programma, determinare il risultato dell'esecuzione del programma con qualsiasi dato input diventa più difficile. Una macchina di Turing non può fare questa determinazione; il risultato è un codice buggy con loop infiniti. Nessun numero di test che utilizza la tecnologia attuale può risolvere questo problema.
Un ipercomputer è un modello di calcolo che va oltre la macchina di Turing per risolvere problemi come il problema dell'arresto. Tuttavia, tali macchine non sono possibili utilizzando la tecnologia attuale. Se fossero possibili, saresti in grado di chiedere loro tutti i tipi di imponderabili che i computer non possono attualmente rispondere. Questo articolo ti fornisce una buona idea di cosa succederebbe se qualcuno fosse in grado di risolvere questo problema.
Creazione e uso delle funzioni unidirezionali
Una funzione unidirezionale è una funzione che è facile da usare per ottenere una risposta in una direzione, ma quasi impossibile da usare con l'inverso di quella risposta. In altre parole, si utilizza una funzione unidirezionale per creare qualcosa come un hash che apparirebbe come parte di una soluzione per la crittografia, l'identificazione personale, l'autenticazione o altre esigenze di sicurezza dei dati.
L'esistenza di una funzione a senso unico è meno misteriosa e più una questione di prova. Molti sistemi di telecomunicazione, e-commerce e e-banking si basano attualmente su funzioni che sono presumibilmente a senso unico, ma nessuno sa veramente se sono davvero a senso unico. L'esistenza di una funzione a senso unico è attualmente un'ipotesi, non una teoria. Se qualcuno fosse in grado di dimostrare che esiste una funzione unidirezionale, i problemi di sicurezza dei dati sarebbero più facili da risolvere dal punto di vista della programmazione.
Moltiplicazione di numeri veramente grandi
Esistono numeri veramente grandi in molti posti. Ad esempio, si consideri l'esecuzione dei calcoli che coinvolgono distanze su Marte, o forse Plutone. Attualmente esistono metodi per eseguire la moltiplicazione su numeri veramente grandi, ma tendono ad essere lenti perché richiedono più operazioni da completare. Il problema si verifica quando i numeri sono troppo grandi per adattarsi ai registri del processore. A quel punto, la moltiplicazione deve avvenire in più di un passaggio, il che rallenta notevolmente le cose. Le soluzioni attuali includono:
- Algoritmo di moltiplicazione complesso di Gauss
- Moltiplicazione di Karatsuba
- Toom-Cook
- Metodi di trasformazione di Fourier
Anche se molti dei metodi attualmente disponibili producono risultati accettabili, tutti richiedono tempo e quando hai un sacco di calcoli da eseguire, il problema del tempo può diventare critico. Di conseguenza, la moltiplicazione dei numeri di grandi dimensioni è uno di quei problemi che richiede una soluzione migliore rispetto a quelli disponibili oggi.
Dividere ugualmente una risorsa
Dividere le risorse allo stesso modo non può sembrare difficile, ma gli umani, essendo il tipo invidioso, potrebbero vedere la risorsa divisa in modo non equo a meno che non si riesca a trovare un modo per assicurare a tutti che la divisione è equa. Questo è il problema del taglio della torta senza invidia. Naturalmente, quando tagli una torta, non importa quanto tu provi a farlo, c'è sempre la percezione che la divisione sia ingiusta. Creare una divisione equa delle risorse è importante nella vita quotidiana per minimizzare il conflitto tra le parti interessate in ogni organizzazione, rendendo tutti più efficienti.
Esistono già due soluzioni per il problema del taglio della torta senza invidia con un numero specifico di persone, ma non esiste una soluzione generale. Quando ci sono due persone coinvolte, la prima taglia la torta e la seconda sceglie il primo pezzo. In questo modo, ad entrambe le parti viene assicurata una divisione equa. Il problema diventa più difficile con tre persone, ma puoi provare la soluzione Selfridge-Conway per il problema. Tuttavia, dopo aver raggiunto quattro persone, non esiste alcuna soluzione.
Riduzione del tempo di calcolo della distanza di modifica
La modifica della distanza tra due stringhe è il numero di operazioni necessarie per trasformare una stringa nell'altra stringa. Il calcolo della distanza ruota attorno alle operazioni a distanza di Levenshtein, che sono la rimozione, l'inserimento o la sostituzione di un personaggio nella stringa. Questa particolare tecnica vede l'uso nelle interfacce del linguaggio naturale, la quantificazione della sequenza del DNA e tutti i tipi di altri luoghi in cui è possibile avere due stringhe simili che richiedono una sorta di confronto o modifica.
Esistono attualmente un certo numero di soluzioni per questo problema, tutte abbastanza lente. In effetti, la maggior parte di essi richiede un tempo esponenziale, quindi il tempo richiesto per eseguire una trasformazione si aggiunge rapidamente al punto in cui gli utenti possono vedere le pause nell'elaborazione dell'input. La pausa non è poi così male quando si utilizza un elaboratore di testi che esegue controlli automatici di parole e cambia una parola errata in quella corretta. Tuttavia, quando si usano le interfacce vocali, la pausa può diventare piuttosto evidente e causare l'errore da parte dell'operatore umano.
Risoluzione rapida dei problemi
Quando l'apprendimento automatico decolla e contiamo sempre di più sui computer per risolvere i problemi, il problema della rapidità con cui un computer può risolvere un problema diventa fondamentale. Il problema P contro NP chiede semplicemente se un computer può risolvere rapidamente un problema quando può verificare rapidamente la soluzione al problema. In altre parole, se il computer può ragionevolmente accertare che una risposta umana a un problema è corretta in un tempo polinomiale o inferiore, può anche risolvere il problema stesso in tempo polinomiale o inferiore?
Questa domanda fu originariamente discussa negli anni '50 da John Nash in lettere alla National Security Agency (NSA) e di nuovo in lettere tra Kurt Gödel e John von Neumann. Oltre all'apprendimento automatico (e all'IA in generale), questo particolare problema riguarda molti altri campi, tra cui la matematica, la crittografia, la ricerca sugli algoritmi, la teoria dei giochi, l'elaborazione multimediale, la filosofia e l'economia.
Giocare al gioco della parità
All'inizio, risolvere un gioco potrebbe non sembrare tutto ciò che è utile nella vita reale. Sì, i giochi sono divertenti e interessanti, ma in realtà non forniscono uno sfondo per fare qualcosa di utile - almeno, questa è la teoria generale. Tuttavia, la teoria dei giochi entra in gioco in un gran numero di scenari di vita reale, molti dei quali implicano processi complessi che qualcuno può capire più facilmente come giochi che come processi reali. In questo caso, il gioco aiuta le persone a comprendere la verifica automatica e la sintesi del controller, tra le altre cose. Puoi leggere di più sul gioco di parità. In effetti, puoi giocarci.
Capire le questioni spaziali
Per mettere questo particolare problema nel contesto, pensa a spostare le scatole in un magazzino o in altre situazioni in cui devi considerare lo spazio in cui le cose si muovono. Ovviamente, se hai molti box in un grande magazzino e tutti richiedono un carrello elevatore da raccogliere, non vuoi provare a capire come memorizzarli in modo ottimale riordinandoli fisicamente. Qui è dove devi lavorare attraverso il problema visualizzando una soluzione.
Tuttavia, la domanda è se tutti i problemi spaziali abbiano una soluzione. In questo caso, pensa a uno di quei puzzle per bambini che ti fanno mettere insieme una foto facendo scorrere le piccole tessere. Sembra come se una soluzione dovesse esistere in tutti i casi, ma in alcune situazioni, un cattivo punto di partenza può portare a una situazione che non ha soluzione.
Matematici come Sam Loyd usano spesso enigmi per dimostrare complessi problemi di matematica, alcuni dei quali non hanno soluzione oggi. Visitare questi siti è divertente perché non solo ricevi un po 'di intrattenimento gratuito, ma anche spunti di riflessione. Le questioni sollevate da questi enigmi hanno applicazioni pratiche, ma sono presentate in modo divertente.
