Dans cette thèse, nous cherchons à comparer la complexité booléenne classique et la complexité algébrique, en étudiant des problèmes sur les polynômes. Nous considérons les modèles de calcul algébriques de Valiant et de Blum, Shub et Smale (BSS). Pour étudier les classes de complexité algébriques, il est naturel de partir des résultats et des questions ouvertes dans le cas booléen, et de regarder ce qu'il en est dans le contexte algébrique. La comparaison des résultats obtenus dans ces deux domaines permet ainsi d'enrichir notre compréhension des deux théories. La première partie suit cette approche. En considérant un polynôme canoniquement associé à toute formule booléenne, nous obtenons un lien entre les questions de complexité booléenne sur la formule booléenne et les questions de complexité algébrique sur le polynôme. Nous avons étudié la complexité du calcul de ce polynôme dans le modèle de Valiant en fonction de la complexité de la formule booléenne, et avons obtenu des analogues algébriques à certains résultats booléens. Nous avons aussi pu utiliser des méthodes algébriques pour améliorer certains résultats booléens, en particulier de meilleures réductions de comptage. Une autre motivation aux modèles de calcul algébriques est d'offrir un cadre pour l'analyse d'algorithmes continus. La seconde partie suit cette approche. Nous sommes partis d'algorithmes nouveaux pour la recherche de zéros approchés d'un système de n polynômes complexes à n inconnues. Jusqu'à présent il s'agissait d'algorithmes pour le modèle BSS. Nous avons étudié l'implémentabilité de ces algorithmes sur un ordinateur booléen et proposons un algorithme booléen.

Dans l'Infralittoral rocheux méditerranéen, les algues brunes du genre Cystoseira forment des habitats structurellement complexes, dénommés forêts à Cystoseira. A cause de certaines activités anthropiques, ces forêts ont déjà disparu dans de nombreuses localités et sont en train de régresser dans d'autres. Elles ont été (sont) généralement remplacées par des habitats structurellement moins complexes de type brousse, gazon ou désert. Cette thèse a visé à estimer les possibles conséquences pour les poissons de la régression des forêts à Cystoseira et à identifier les processus écologiques en cause. Plusieurs approches complémentaires ont été employées : inventaires de macroalgues et de poissons, expériences de prédation et de sélection d'habitats en aquarium, analyses de composions isotopiques et de contenus stomacaux. Les densités de poissons proie et prédateur étaient plus importantes dans les forêts à Cystoseira que dans les habitats structurellement moins complexes. Cela peut résulter, au moins en partie, du rôle "refuge" de Cystoseira spp. qui induit (1) une plus faible mortalité des poissons proies et prédateurs dans les forêts, due à une plus grande disponibilité en abris et en nourriture, respectivement, (2) une immigration nette des poissons dans les forêts due à leur préférence pour cet habitat structurellement complexe. De plus, Cystoseira spp. pourrait être une importante source de matière organique pour l'écosystème. Ce potentiel rôle trophique mérite des études complémentaires. Ce travail suggère que la régression des forêts à Cystoseira est néfaste pour les poissons et souligne donc la nécessité de mieux gérer les activités humaines impactant Cystoseira spp. / In Mediterranean rocky subtidal, large brown algae belonging to the genus Cystoseira form structurally complex habitats, called Cystoseira forest. Due to anthropogenic stressors, Cystoseira forests disappeared from numerous localities in the Mediterranean Sea and are deteriorating in other localities. Cystoseira forests are usually replaced by structurally less complex habitats, such as shrublands, turfs and barren. This PhD aimed to assess putative consequences for fish of Cystoseira forest degradation, and to identify the underlying ecological processes. Multiple complementary approaches were used: macroalgae and fish field surveys, tank-based predation and habitat-choice experiments, stable isotopes and stomach contents analyses. Densities of prey and predatory fish were higher in Cystoseira forests compared to structurally less complex habitats. This may be due to the shelter role of Cystoseira spp. that induces (1) reduced mortality of prey and predatory fish in forests, due to high shelter and food availability, respectively, and (2) net immigration of fish into forests due to their preference for this structurally complex habitat. Moreover, Cystoseira spp. may be an important source of organic matter to the ecosystem. This possible trophic role deserves complementary studies. This work suggests that Cystoseira forest degradation are harmful to fish and from this perspective stresses the need to better manage human activities impacting Cystoseira spp.