Esiste una frase o una parola per descrivere un algoritmo o il programma è completo in quel dato qualsiasi valore per i suoi argomenti c'è un risultato definito?

6

C'è una frase o una parola per descrivere un algoritmo o un programma è completo in quel dato qualsiasi valore per i suoi argomenti c'è un risultato definito? cioè tutte le ramificazioni sono state considerate indipendentemente dal contesto?

Un semplice esempio potrebbe essere la seguente funzione:

function returns string get_item_type(int type_no)
{
  if(type_no < 10)
    return "hockey stick"
  else if (type_no < 20)
    return "bulldozer"
  else
    return "unknown"
}

(scusa il pseudo codice lugubre)

Indipendentemente dal numero fornito, tutte le possibilità sono soddisfatte. La mia domanda è: c'è una parola per riempire lo spazio vuoto qui:

"get_item_type() is ______ complete"

(La risposta non è Turing Complete - si tratta di qualcosa di molto diverso - ma io penso sempre fastidiosamente a qualcosa come "Turing Complete" quando penso a quanto sopra).

    
posta markmnl 11.06.2012 - 10:23
fonte

3 risposte

11

potresti dire che è una funzione pura

o se c'è uno stato da considerare oltre agli argomenti, potresti dire che è deterministico

    
risposta data 11.06.2012 - 10:36
fonte
13

Matematicamente parlando, il termine che stai cercando è " Total Function " (una funzione definita per ogni possibile valore in qualche dominio), al contrario di una "funzione parziale", che è definita solo per un sottoinsieme dei possibili valori di input.

Si noti che, in senso stretto, le funzioni matematiche sono sempre totali nel proprio dominio; chiamare una funzione "parziale" ha senso solo se lo si confronta con un altro dominio, come la funzione f(x) = 1/x : il dominio di questa funzione è il dominio di tutti i numeri reali tranne lo zero, ma contro il dominio di tutti i numeri reali (incluso zero), è parziale.

Nella programmazione, i tipi di input di una funzione indicano già un dominio, e non definendo la funzione per tutti loro, si potrebbe dire che la funzione è parziale. Tuttavia, molti linguaggi di programmazione ricadono in un comportamento predefinito quando non si restituiscono esplicitamente nulla: possono restituire 0, null , undefined , ecc. Tecnicamente parlando, tali funzioni sono ancora totali - restituiscono un valore per tutti possibili input -, ma concettualmente, ci sono lacune nella definizione. E non tutti i linguaggi di programmazione presentano tali fallback; le alternative si rifiutano di compilare, rispondendo con "comportamento indefinito", sollevando un'eccezione, ecc.

A proposito, nota che né il determinismo né la purezza hanno nulla a che fare con questo. Una funzione deterministica è quella che ha sempre lo stesso effetto dato lo stesso contesto (stato del sistema e input rilevanti); una funzione pura è una funzione che non ha effetti collaterali (in modo che restituisca sempre lo stesso valore dato gli stessi input, indipendentemente da qualsiasi stato esterno, e senza influenzare in alcun modo lo stato esterno). Puoi facilmente trovare una funzione parziale, ma completamente deterministica (ammesso che le funzioni parziali siano legali nel tuo linguaggio di programmazione e le lacune di definizione siano gestite in modo predicibile); e viceversa, se riesci a scrivere una funzione non deterministica, ad es. leggendo da una fonte di entropia hardware, non c'è motivo per cui debba essere totale (né parziale). Lo stesso vale per la purezza, a meno che una lacuna di definizione non introduca automaticamente effetti collaterali (allora anche tutte le funzioni pure devono essere totali).

    
risposta data 11.06.2012 - 22:25
fonte
4

Nel tuo caso ...

Nel tuo esempio particolare, quello che abbiamo è un puro surjective funzione (parziale) .

(Non lasciarti fuorviare dal "partial". Vedi sotto.)

Per rispondere alla tua domanda, dobbiamo considerare questi:

Algoritmi e funzioni

Gli algoritmi sono implementati usando:

Funzioni

Le funzioni possono anche essere considerate:

Tipi di funzioni

Inoltre, considera i seguenti tipi di funzioni da una prospettiva matematica:

Funzione Injective

Una funzione parziale in cui i risultati sono unici.

Funzione Surjective

Una funzione parziale in cui i risultati possono sovrapporsi.

Funzione Bijective

Una funzione totale, sia iniettiva che surjective , dove c'è un output per tutti i possibili input e dove tutti gli output possibili sono distinti e ottenuti da un input univoco, quindi perfettamente abbinati.

    
risposta data 12.06.2012 - 07:42
fonte

Leggi altre domande sui tag