Limite supérieure de fib (n + 2)

8

J'ai un problème de devoirs qui me rend perplexe parce que les mathématiques vont au-delà de ce que j'ai fait, même si on nous a dit qu'il n'était pas nécessaire de résoudre cela mathématiquement. Fournissez simplement une limite supérieure étroite et justifiez-la.

Soit Fournir une borne supérieure asymptotique sur comme .

f(n)=|{w{a,b}n:aaw}|.
fn

Jusqu'à présent:

nstringscompared to 2n122n0232n1352n3482n85132n186212n43

Les mathématiques qui me donneront une limite exacte me dépassent. Évidemment, est une limite supérieure, bien qu'elle ne soit pas particulièrement serrée.O(2n)

Des suggestions sur ce que je devrais essayer?

Wawa
la source
1
Bienvenue en informatique! Le titre que vous avez choisi n'est pas bien adapté pour représenter votre question. Veuillez prendre le temps de l'améliorer; nous avons rassemblé quelques conseils ici . Je vous remercie!
Raphael
Beaucoup de gens considéreraient fib (n + 1) comme une expression parfaitement fine pour une limite supérieure. Encore mieux car c'est exact :-)
gnasher729

Réponses:

8

Je ne suis donc pas complètement sûr, mais je pense que vous demandez de compter le nombre de chaînes de taille (sur l'alphabet ) où le facteur / sous-chaîne n'apparaît pas non?n{a,b}aa

Dans ce cas, vous pouvez adopter quelques approches combinatoires. Yuval et ADG ont tous deux donné des arguments plus simples et plus intuitifs, je suggère donc de vérifier leurs réponses! Voici l'un de mes favoris, c'est un peu étrange, mais c'est une approche très générale (et plutôt amusante).

Commençons par un langage plus simple, celui des mots qui commence et se termine par (également sans sous-chaîne de ). Nous pouvons regarder une chaîne admissible (par exemple ) comme une liste de séquences de s séparées par singulier s. Cela donne la construction: Maintenant, comment comptons-nous les phrases qui appartiennent à cette langue?baabbbababbbbba

w=(b+a)b+

Imaginons que nous développons ces expressions. Que signifie ? Eh bien, c'est simplement Maintenant, cela n'aura que très peu de sens, mais imaginons que soit une variable sur un champ numérique. En particulier, nous traiterons , et . Cela dit alors que Essayons de voir la motivation derrière cette étrange interprétation. Il s'agit presque d' une transformation bijective. En particulier, nous voulons conserver le nombre de chaquee

e=ϵeeeeeeeeee
eϵ1aba+babca×b×c
e1+e+ee+eee+
enmot, comme vous pouvez facilement le voir, nous le faisons. Cependant, il existe une différence cruciale entre les expressions de chaîne et les expressions numériques: la multiplication (concaténation en chaînes, en expressions numériques) est désormais commutative! Intuitivement, la commutativité nous permet de traiter toutes les permutations du même mot comme les mêmes; c'est-à-dire que nous ne faisons pas de entre l'expression et ; ils représentent tous les deux une chaîne avec 4 s et une . Par conséquent, cette transformation nous permet de conserver le décompte de chaque mot d'un certain nombre de et s, mais elle nous permet désormais de fermer les yeux sur les détails superflus dont nous ne nous soucions pas.×bbbabbbabbbaab

Si vous revenez au précalcul, vous pourriez reconnaître cette série comme 11e. Je sais que cela n'a aucun sens de réécrire cette expression régulière en tant que fonction à valeur numérique, mais juste à nu avec moi pendant un moment.

De même, e+=eee1e. Ce qui signifie que nous pouvons traduirew dans

w11(b1b×a)×b1b

À son tour, nous pouvons simplifier cela jusqu'à

w(a,b)=b×11(b+ba)

Cela nous dit que la langue west isomorphe à la langue (dont la traduction directe est déjà ) sans jamais avoir recours à des outils théoriques de la langue! C'est l'un des pouvoirs de traiter ces séries comme des fonctions de forme fermée: nous pouvons y effectuer des simplifications qui sont presque impossibles à réaliser autrement, ce qui les réduit à un problème plus simple.b(bab)b1bba

Maintenant, si vous vous souvenez encore de l'un de vos cours de calcul, vous vous souviendrez que certains types de fonctions (qui se comportent assez bien) admettent ces représentations en série appelées extensions de Taylor. Ne vous inquiétez pas, nous n'aurons pas vraiment à nous soucier de ces embêtants problèmes Calc 1; Je souligne simplement que ces fonctions peuvent être représentées comme la somme pour que donne le nombre de mots satisfaisant tel qu'il ait exactement occurrences de et occurrences de

w(a,b)=i,jwijaibj
wijwiajb . Cependant, nous ne nous soucions pas particulièrement de savoir si quelque chose est una ou un b. Nous nous soucions plutôt du nombre total de caractères dans la chaîne. Pour fermer les yeux entrea et b, nous pouvons juste (littéralement) les traiter de la même façon, par exemple z=a=b et obtenir
w(z)=w(z,z)=z1zz2=kwkzk

wk compte le nombre de mots de longueur satisfaisable k.

Il ne reste plus qu'à trouver wk. L'approche combinatoire habituelle ici serait de décomposer cette fonction rationnelle en sa fraction partielle: c'est-à-dire, étant donné le dénominateur1zz2=(zϕ)(zψ), nous pouvons réécrire z(zϕ)(zψ)=Azϕ+Bzψ(Il y a un peu d'algèbre impliqué ici, mais c'est une propriété universelle des fonctions rationnelles (un polynôme en divisant un autre)). Pour résoudre ce problème, vous pouvez refactoriser

Azϕ+Bzψ=z(zϕ)(zψ)
qui génère les contraintes A+B=1,Aψ+Bϕ=0. Indépendamment de quoiA et B sont, rappelez-vous que 11x=1+x+x2+on peut réorganiser
w(z)=Aϕz+Bψz=(Aϕ)11zϕ+(Bψ)11zψ=(Aϕ)(1+ϕ1z+ϕ2z2+)+(Bψ)(1+ψ1z+ψ2z2+)
par conséquent
wk=(Aϕ)ϕk+(Bψ)ψk
Ici, ϕ est le nombre d'or 1+52 et ψ=ϕ1est son conjugué. Nous avons alors une description facile du comportement asymptotique duw langue: il s'exécute dans Θ(ϕn). En fait, si vous développez tout, vous constaterez que
wk=ϕkψk5=ϕk5
Il existe également une connexion complexe à une autre classe combinatoire commune. Ce ne sont que les chiffres de Fibonacci!

Maintenant, supposons que vous ayez wk, qui compte le nombre de chaînes de taille k qui commence et se termine par k (et ne contient pas non plus aa sous-chaînes), comment pouvons-nous construire une chaîne qui peut commencer ou se terminer par un a? Eh bien, c'est simple: une chaîne admissible est soit dansw (commence et se termine par b), ou c'est aw (commence avec a), ou c'est wa (se termine par a), ou c'est awa (commence et se termine par a). Donc:

f(n)=wn+wn2+2wn1
Rappeler que wn est la séquence fibonacci, donc wn1+wn2=wn, ce qui signifie que
f(n)=(wn+wn1)+(wn2+wn1)=wn+1+wn=wn+2
Donc, f(n)=fib(n+2)=ϕn+25

Maintenant, vous n'avez probablement pas besoin de faire cette analyse, mais le simple fait de savoir que cette séquence est une séquence de Fibonacci décalée devrait vous donner une idée d'autres interprétations combinatoires que vous pouvez essayer.

Lee
la source
7

La réponse de Lee Gao est excellente. Voici un compte différent. Considérez l'automate suivant:

Automate pour la langue

Il s'agit d'un automate fini sans ambiguïté (UFA) sansϵtransitions: un NFA tel que chaque mot a exactement un chemin d'acceptation. Le nombre de mots de longueurn est donc le nombre de chemins de longueur n de l’état de départ à l’état d’acceptation (car il n’existe pas de ϵ transitions).

Nous pouvons compter le nombre de chemins dans un graphe en utilisant l'algèbre linéaire. LaisserMêtre la matrice de transition de l'automate:M(qi,qj) est le nombre de flèches de qj à qi(chaque flèche est associée à un seul symbole). alors

M2(qi,qj)=kM(qi,qk)M(qk,qj),
qui est exactement le nombre de chemins de longueur 2 à partir de qj à qi. De même,Mn(qi,qj) est le nombre de chemins de longueur n de qj à qi. Dans notre cas, nous voulons compter le nombre de chemins de longueurn de q0 à {q0,q1}, et donc
f(n)=(11)(1110)n(10).
La façon standard de calculer une telle expression est de diagonaliser M (ou, plus généralement, en calculant la forme jordanienne de M). Les valeurs propres deM sont facilement calculés pour être 1±52, et donc pour une matrice P,
f(n)=(11)P((1+52)n00(152)n)P1(10)=A(1+52)n+B(152)n,
pour certains coefficients A,B. DéterminerA,B on peut soit diagnostiquer M explicitement, ou tout simplement mettre en place un système linéaire en utilisant des valeurs connues de f. Depuisf(0)=1 et f(1)=2, cette dernière approche montre que
A+B=11+52A+152B=2
En résolvant ce système (par exemple en utilisant l'élimination gaussienne), nous découvrons que A=5+3510 et B=53510. Donc
f(n)=5+3510(1+52)n+53510(152)n=Θ(λmaxn), where λmax=1+52.
La même approche fonctionne pour chaque langue régulière.
Yuval Filmus
la source
C'est une approche amusante! J'adore toujours voir des réductions algébriques linéaires pour les problèmes liés aux chemins :)
Lee
4

@Lee Gao est trop complexe (je n'ai même pas tout lu), voici une approche simpliste:

Soit f (n) toutes les chaînes souhaitées parmi lesquelles a (n) les chaînes se terminant en a et b (n) les chaînes se terminant en b.

Maintenant, pour chaque chaîne qui se termine par b, nous pouvons ajouter directement a pour obtenir ba en fin et une chaîne valide:

(1)a(n)=b(n1)
Notez que nous ne pouvons pas ajouter un à la fin des chaînes qui se terminent par un sinon nous aurons un aa à la fin.

Nous pouvons ajouter b à n'importe quelle chaîne:

(2)b(n)=a(n1)+b(n1)

Maintenant nn1 dans (1) et remplacer dans (2):

b(n)=b(n2)+b(n1)
Donc b (n) est fib (n) et puisque a (n) est b (n-1), donc a (n) est fib (n-1). Maintenant f (n) est:
f(n)=a(n)+b(n)=fib(n)+fib(n1)=fib(n+1)
Comme fib (n) est (φnφn)/5, donc f (n) est O(φn), φ=1+521.618. (Priseφ/5 aussi constant et négligent φn pour grand n pour obtenir une asymptote)

Remarque: fib (0) = 0, fib (1) = 1.

RE60K
la source
Cependant, votre limite supérieure n'est pas très bonne: chaque langue {a,b} a tout au plus 2n mots de longueur n!
Yuval Filmus
@YuvalFilmus quel est le problème, vous voulez un lien plus étroit puis utilisez fib(n)=(ϕnϕn)/5
RE60K
C'est bien! Les paires de constructions inductives à pas dea et bc'était aussi ce à quoi je pensais.
Lee