m

F Nous contacter

0

Documents  68Q30 | enregistrements trouvés : 58

O

-A +A

P Q

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Localisation : Colloque 1er étage (LOS)

20-02 ; 20Exx ; 20M35 ; 68Q30 ; 68Qxx

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 431 p.
ISBN 978-0-387-12920-4

Lecture notes in computer science , 0166

Localisation : Collection 1er étage

algorithme # algorithmique # complexité # informatique théorique # langage formel # logique # logique de programmation # logique mathématiques # programme # réseaux # système informatique

68-06 ; 68A05 ; 68CXX ; 68Q30 ; 68Qxx

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 486 p.
ISBN 978-0-12-386870-1

Perspectives in computing , 0015

Localisation : Colloque 1er étage (KYOT)

algorithme # co dage # code # complexite des algorithmes # cryptographie # mathematiques discretes # theorie de l' information

68Q25 ; 68Q30 ; 68R10 ; 94A60 ; 94Axx

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 305 p.
ISBN 978-3-540-17218-5

Lecture notes in computer science , 0246

Localisation : Collection 1er étage

algorithme # architecture et réseau # circuit intégré # classe de complexité # gestion des systèmes informatiques # grammaire # implementation # logique mathématiques # structure des données # système de réecriture

68Mxx ; 68Q05 ; 68Q30 ; 68Q50 ; 68Qxx

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 456 p.
ISBN 978-3-540-13331-5

Lecture notes in computer science , 0171

Localisation : Collection 1er étage

algorithme # automate # complexité # indécidabilité # logique # machine

03D05 ; 20F10 ; 68Q30 ; 68Qxx

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 196 p.
ISBN 978-3-540-19368-5

Lecture notes in computer science , 0311

Localisation : Collection 1er étage

algorithme # codage # complexité des algorithmes # théorie de l'information # théorie des codes

68Q30 ; 94Bxx

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.


ISBN 978-0-8186-0644-1

Localisation : Colloque 1er étage (PONT)

algorithme # automatique # informatique # ordinateur

68-06 ; 68Q25 ; 68Q30 ; 68Q70 ; 68R10

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 400 p.
ISBN 978-3-540-16486-9

Lecture notes in computer science , 0223

Localisation : Collection 1er étage

algorithme # complexité # logique

68Q30

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 495 p.
ISBN 978-3-540-54343-5

Lecture notes in computer science , 0519

Localisation : Collection 1er étage

algorithme # algorithmique # énumération # graphe # structure des données

68P05 ; 68Q20 ; 68Q22 ; 68Q25 ; 68Q30

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.


ISBN 978-0-7923-0007-6

Nato a.s.i. series

Localisation : Colloque 1er étage (OTTA)

algorithme # algorithmiqu e # combinatoire # complexite # donnee graphique # ensemble ordonne # informatique graphique # logique # ordre # structure de donnee graphique # structure ordonnee

68Q25 ; 68Q30

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 719 p.
ISBN 978-3-540-55719-7

Lecture notes in computer science , 0623

Localisation : Collection 1er étage

algorithme de graphes # algorithme géométrique # analyse d'algorithme # automate fini # calcul parallèle # calcul symbolique # complexité de Kolmogorov # développement de programme # grammaire de graphes # langage # langage formel # logique # modèle # programmation # spécification de temps # sémantique concurrence # équivalence de processus

68Q10 ; 68Q25 ; 68Q30 ; 68Q50 ; 68R10

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 510 p.
ISBN 978-3-540-56279-5

Lecture notes in computer science , 650

Localisation : Collection 1er étage

algorithme # algorithme combinatoire # algorithme des couleurs # algorithme des graphes # algorithme parallèle # algorithmique # calcul # complexité # graphe # géométrie de l'informatique # stucture des données # théorie de la complexité

68P05 ; 68Q25 ; 68Q30 ; 68Qxx ; 68R05

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 654 p.
ISBN 978-3-540-60216-3

Lecture notes in computer science , 0959

Localisation : Collection 1er étage

algorithme de graphe # algorithme parallèle # apprentissage # base de données # calcul distribué # combinatoire # conception combinatoire # géométrie informatique # logique distribuée # modèle de machine # planification # théorie de la complexité # tracé de graphe

05Cxx ; 68Q20 ; 68Q25 ; 68Q30 ; 68R05

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 419 p.
ISBN 978-3-540-61332-9

Lecture notes in computer science , 1090

Localisation : Collection 1er étage

algorithme non numérique # analyse des algorithmes # calcul # combinatoire # complexité des problèmes # grammaire # informatique de la géométrie # informatique théorique # modélisation d'objet # opération et gestion # réseau # réécriture des systèmes # système distribué # système informatique # théorie de l'information algorithmique # théorie des graphes

05Cxx ; 68Q20 ; 68Q25 ; 68Q30 ; 68R05

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Theoretical computer science , 0175

Localisation : Colloque 1er étage (LYON)

algorithme # algorithme parallèle # application # architecture # encodage # fonction booléenne # graphe # informatique théorique # problème d'interval # reconnaissance # structure et représentation de treillis # treillis booléens

68Q10 ; 68Q20 ; 68Q30 ; 68R10 ; 68Rxx ; 68T10

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- pag. multi.

Localisation : Colloque 1er étage (NICE)

algorithmique

68-06 ; 68Q30

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;Computer Science;Logic and Foundations

Carleson's Theorem states that for $1 < p < \infty$, the Fourier series of a function $f$ in $L^p[-\pi,\pi]$ converges to $f$ almost everywhere. We consider this theorem in the context of computable analysis and show the following two results.
(1) For a computable $p > 1$, if $f$ is a computable vector in $L^p[?\pi,\pi]$ and $t_0 \in [-\pi,\pi]$ is Schnorr random, then the Fourier series for $f$ converges at $t_0$.
(2) If $t_0 \in [-\pi,\pi]$ is not Schnorr random, then there is a computable function $f : [-\pi,\pi] \rightarrow \mathbb{C}$ whose Fourier series diverges at $t_0$.
This is joint work with Timothy H. McNicholl, and Jason Rute.
Carleson's Theorem states that for $1 < p < \infty$, the Fourier series of a function $f$ in $L^p[-\pi,\pi]$ converges to $f$ almost everywhere. We consider this theorem in the context of computable analysis and show the following two results.
(1) For a computable $p > 1$, if $f$ is a computable vector in $L^p[?\pi,\pi]$ and $t_0 \in [-\pi,\pi]$ is Schnorr random, then the Fourier series for $f$ converges at $t_0$.
(2) If $t_0 \in [-\pi,\pi]$ i...

03D32 ; 42A20 ; 03D78 ; 68Q30

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;Computer Science;Logic and Foundations

We discuss subshifts of finite type (tilings) that combine virtually opposite properties, being at once very simple and very complex. On the one hand, the combinatorial structure of these subshifts is rather simple: we require that all their configurations are quasiperiodic, or even that all configurations contain exactly the same finite patterns (in the last case a subshift is transitive, i.e., irreducible as a dynamical system). On the other hand, these subshifts are complex in the sense of computability theory: all their configurations are non periodic or even non-computable, or all their finite patterns have high Kolmogorov complexity, the Turing degree spectrum is rather sophisticated, etc.
We start with the simplest example of such centaurisme with an SFT that is minimal and contains only aperiodic (and quasiperiodic) configurations. Then we discuss how far these heterogeneous properties can be strengthened without getting mutually exclusive.
This is a joint work with Bruno Durand (Univ. de Montpellier).
We discuss subshifts of finite type (tilings) that combine virtually opposite properties, being at once very simple and very complex. On the one hand, the combinatorial structure of these subshifts is rather simple: we require that all their configurations are quasiperiodic, or even that all configurations contain exactly the same finite patterns (in the last case a subshift is transitive, i.e., irreducible as a dynamical system). On the other ...

68Q30 ; 03B80

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;Computer Science;Logic and Foundations

Barmpalias and Lewis-Pye recently proved that if $\alpha$ and $\beta$ are (Martin-Löf) random left-c.e. reals with left-c.e. approximations $\{\alpha_s \}_{s \in\ omega}$ and $\{\beta_s \}_{s \in\ omega}$, then
\[
\begin{equation}
\frac{\partial\alpha}{\partial\beta} = \lim_{s\to\infty} \frac{\alpha-\alpha_s}{\beta-\beta_s}.
\end{equation}
\]
converges and is independent of the choice of approximations. Furthermore, they showed that $\partial\alpha/\partial\beta = 1$ if and only if $\alpha-\beta$ is nonrandom; $\partial\alpha/\partial\beta>1$ if and only if $\alpha-\beta$ is a random left-c.e. real; and $\partial\alpha/\partial\beta<1$ if and only if $\alpha-\beta$ is a random right-c.e. real.

We extend their results to the d.c.e. reals, which clarifies what is happening. The extension is straightforward. Fix a random left-c.e. real $\Omega$ with approximation $\{\Omega_s\}_{s\in\omega}$. If $\alpha$ is a d.c.e. real with d.c.e. approximation $\{\alpha_s\}_{s\in\omega}$, let
\[
\partial\alpha = \frac{\partial\alpha}{\partial\Omega} = \lim_{s\to\infty} \frac{\alpha-\alpha_s}{\Omega-\Omega_s}.
\]
As above, the limit exists and is independent of the choice of approximations. Now $\partial\alpha=0$ if and only if $\alpha$ is nonrandom; $\partial\alpha>0$ if and only if $\alpha$ is a random left-c.e. real; and $\partial\alpha<0$ if and only if $\alpha$ is a random right-c.e. real.

As we have telegraphed by our choice of notation, $\partial$ is a derivation on the field of d.c.e. reals. In other words, $\partial$ preserves addition and satisfies the Leibniz law:
\[
\partial(\alpha\beta) = \alpha\,\partial\beta + \beta\,\partial\alpha.
\]
(However, $\partial$ maps outside of the d.c.e. reals, so it does not make them a differential field.) We will see how the properties of $\partial$ encapsulate much of what we know about randomness in the left-c.e. and d.c.e. reals. We also show that if $f\colon\mathbb{R}\rightarrow\mathbb{R}$ is a computable function that is differentiable at $\alpha$, then $\partial f(\alpha) = f'(\alpha)\,\partial\alpha$. This allows us to apply basic identities from calculus, so for example, $\partial\alpha^n = n\alpha^{n-1}\,\partial\alpha$ and $\partial e^\alpha = e^\alpha\,\partial\alpha$. Since $\partial\Omega=1$, we have $\partial e^\Omega = e^\Omega$.

Given a derivation on a field, the elements that it maps to zero also form a field: the $ \textit {field of constants}$. In our case, these are the nonrandom d.c.e. reals. We show that, in fact, the nonrandom d.c.e. reals form a $ \textit {real closed field}$. Note that it was not even known that the nonrandom d.c.e. reals are closed under addition, and indeed, it is easy to prove the convergence of [1] from this fact. In contrast, it has long been known that the nonrandom left-c.e. reals are closed under addition (Demuth [2] and Downey, Hirschfeldt, and Nies [3]). While also nontrivial, this fact seems to be easier to prove. Towards understanding this difference, we show that the real closure of the nonrandom left-c.e. reals is strictly smaller than the field of nonrandom d.c.e. reals. In particular, there are nonrandom d.c.e. reals that cannot be written as the difference of nonrandom left-c.e. reals; despite being nonrandom, they carry some kind of intrinsic randomness.
Barmpalias and Lewis-Pye recently proved that if $\alpha$ and $\beta$ are (Martin-Löf) random left-c.e. reals with left-c.e. approximations $\{\alpha_s \}_{s \in\ omega}$ and $\{\beta_s \}_{s \in\ omega}$, then
\[
\begin{equation}
\frac{\partial\alpha}{\partial\beta} = \lim_{s\to\infty} \frac{\alpha-\alpha_s}{\beta-\beta_s}.
\end{equation}
\]
converges and is independent of the choice of approximations. Furthermore, they showed that ...

03D28 ; 03D80 ; 03F60 ; 68Q30

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;Computer Science;Logic and Foundations

I will discuss two recent interactions of the field called randomness via algorithmic tests. With Yokoyama and Triplett, I study the reverse mathematical strength of two results of analysis. (1) The Jordan decomposition theorem says that every function of bounded variation is the difference of two nondecreasing functions. This is equivalent to ACA or to WKL, depending on the formalisation. (2) A theorem of Lebesgue states that each function of bounded variation is differentiable almost everywhere. This turns out to be equivalent WWKL (with some fine work left to be done on the amount of induction needed). The Gamma operator maps Turing degrees to real numbers; a smaller value means a higher complexity. This operator has an analog in the field of cardinal characteristics along the lines of the Rupprecht correspondence [4]; also see [1]. Given a real p between 0 and 1/2, d(p) is the least size of a set G so that for each set x of natural numbers, there is a set y in G such that x and y agree on asymptotically more than p of the bits. Clearly, d is monotonic. Based on Monin's recent solution to the Gamma question (see [3] for background, and the post in [2] for a sketch), I will discuss the result with J. Brendle that the cardinal d(p) doesn't depend on p. Remaining open questions in computability (is weakly Schnorr engulfing equivalent to "Gamma = 0"?) nicely match open questions about these cardinal characteristics. I will discuss two recent interactions of the field called randomness via algorithmic tests. With Yokoyama and Triplett, I study the reverse mathematical strength of two results of analysis. (1) The Jordan decomposition theorem says that every function of bounded variation is the difference of two nondecreasing functions. This is equivalent to ACA or to WKL, depending on the formalisation. (2) A theorem of Lebesgue states that each function of ...

03D25 ; 03D32 ; 03F60 ; 68Q30

... Lire [+]

Z