Dans un test de pièce pour la préparation de GATE, il y avait une question: f(n): if n is even: f(n) = n/2 else f(n) = f(f(n-1)) J'ai répondu "Il se terminera pour tous les entiers", car même pour certains entiers négatifs, il se terminera par une erreur de dépassement de pile . Mais mon ami...
Voici le contexte ( Structure et interprétation des programmes informatiques , section 1.1.8, sous la rubrique "Noms locaux"): Un paramètre formel d'une procédure a un rôle très spécial dans la définition de la procédure, en ce que le nom du paramètre formel n'a pas d'importance. Un tel nom est...
Étant donné une chaîne de valeurs AAAAAAAABCAAAAAAAABCAAAAAAAABC , l'entropie de Shannon dans la base de log 222 s'élève à 0.9220.9220.922 . D'après ce que je comprends, dans la base 222 l'entropie de Shannon arrondie est le nombre minimum de bits en binaire pour représenter une seule des...
Les CPU sont dans une certaine mesure conçus en tenant compte du logiciel que les gens vont écrire pour cela, implicitement ou explicitement. Il me semble que si vous regardez la conception des architectures de jeux d'instructions, elles sont très "impératives", dans le sens où chaque instruction...
Étant donné un labyrinthe à 2 dimensions où vous pouvez donner 4 commandes "monter / descendre / droite / gauche". Connaître le labyrinthe mais pas où se trouve la personne, comment trouver la séquence minimale de commandes qui garantit la sortie du labyrinthe? Je recherche une seule séquence de...
Je suis un peu confus quant à la signification exacte d'une «clé» en informatique. Je comprends les paires clé-valeur, clés primaires, etc ... Mais je ne trouve pas de définition de ce que le terme "clé" signifie par lui-même. Pour autant que je sache, cela signifie simplement une donnée. Dans...
Une liste de nnn éléments peut être vérifiée comme triée en comparant chaque élément à son voisin. Dans mon application, je ne pourrai pas comparer chaque élément avec son voisin: au lieu de cela, les comparaisons se feront parfois entre des éléments distants. Étant donné que la liste contient plus...
Je veux générer un Sudoku complètement aléatoire . Définissez une grille Sudoku comme une grille d'entiers entre et où certains éléments peuvent être omis. Une grille est un casse-tête valide s'il existe un moyen unique de le compléter pour correspondre aux contraintes de Sudoku (chaque ligne,...
Existe-t-il une approche algorithmique pour identifier les dates données dans un paragraphe en corrélation avec des événements (phrases) particuliers dans le paragraphe? Exemple, considérons le paragraphe suivant: En juin 1970, le grand chef prête serment. Mais ce n'est qu'après mai 1972, après la...
Un jeu simple habituellement joué par des enfants, le jeu de guerre est joué par deux personnes en utilisant un jeu standard de 52 cartes à jouer. Initialement, le jeu est mélangé et toutes les cartes sont distribuées entre les deux joueurs, de sorte que chacun a 26 cartes aléatoires dans un ordre...
Lorsque l'on rapporte la complexité algorithmique d'un algorithme, on suppose que les calculs sous-jacents sont effectués sur une machine abstraite (par exemple RAM) qui se rapproche d'un processeur moderne. De tels modèles nous permettent de rendre compte de la complexité temporelle et spatiale...
Soit S={Si}1≤i≤nS={Si}1≤i≤n\cal{S}=\{S_i\}_{1\leq i\leq n} une conception partielle (m,k)(m,k)(m,k) et f:{0,1}m→{0,1}f:{0,1}m→{0,1}f: \{0,1\}^m \to \{0,1\} une fonction booléenne. Le générateur de Nisan-Wigderson Gf:{0,1}l→{0,1}nGf:{0,1}l→{0,1}nG_f: \{0,1\}^l \to \{0,1\}^n est défini comme suit:...
Je lisais un article qui décrit le basculement entre l'espace utilisateur et l'espace noyau qui se produit lors d'un appel système. L'article dit Une application attend la fin de l'appel système avant de reprendre l'exécution en mode utilisateur. Maintenant, jusqu'à présent, je supposais que...
Considérez le protocole suivant, destiné à authentifier (Alice) à B (Bob) et vice versa.AAABBB A→B:B→A:A→B:“I'm Alice”,RAE(RA,K)E(⟨RA+1,PA⟩,K)A→B:“I'm Alice”,RAB→A:E(RA,K)A→B:E(⟨RA+1,PA⟩,K) \begin{align*} A \to B: &\quad \text{“I'm Alice”}, R_A \\ B \to A: &\quad E(R_A, K) \\ A \to B: &\quad...
Le problème post-correspondance (PCP) est indécidable. La version limitée du PCP est complète et la version marquée du PCP (les mots de l'une des deux listes doivent différer dans la première lettre) est en P S P A C E [1].N PNP\mathrm{NP}P S P A C EPSPUNECE\mathrm{PSPACE} Ces versions restreintes...
Le problème 3-Partition demande si un ensemble de entiers peut être partitionné en ensembles de trois nombres entiers tels que chacun des montants mis en place pour un certain nombre entier donné . Le problème de partition équilibrée demande si entiers peuvent être partitionnés en deux ensembles de...
Je travaille souvent avec lexer / parsers , par opposition à un combinateur d'analyseurs et je vois des gens qui n'ont jamais suivi de cours d'analyse, poser des questions sur l'analyse des données binaires. En règle générale, les données sont non seulement binaires, mais également contextuelles....
Je suis confus quant à la façon dont les taps sont choisis pour les registres à décalage à rétroaction linéaire. J'ai un diagramme qui montre un LFSR avec un polynôme de connexion . Les cinq étapes sont étiquetées: R 4 , R 3 , R 2 , R 1 et R 0 et les prises sortent de R 0 et R 3 .C( X) = X5+ X2+...
LLL est une langue régulière sur l'alphabet . Le quotient gauche de concernant est le langage L w ∈ Σ ∗ w - 1 L : = { v ∣ w v ∈ L }Σ={a,b}Σ={a,b}\Sigma = \{a,b\}LLLw∈Σ∗w∈Σ∗w \in \Sigma^*w−1L:={v∣wv∈L}w−1L:={v∣wv∈L}w^{-1} L := \{v \mid wv \in L\} Comment puis-je prouver que est...
Supposons que l'on me donne entiers de largeur fixe (c'est-à-dire qu'ils s'inscrivent dans un registre de largeur w ), a 1 , a 2 , … a n tels que leur somme a 1 + a 2 + ⋯ + a n = S s'inscrit également dans un registre de largeur w .nnnwwwa1,a2,…ana1,a2,…ana_1, a_2, \dots...