En del svårigheter som elever upplever i algebra kan bero på saknad förståelse av strukturen i matematiska uttryck. Struktur, i det här sammanhanget, syftar på hur en matematisk enhet består av delar, och hur dessa delar är relaterade till varandra. Tidigare studier indikerar också att elevers svårigheter inom algebra beror på bristande aritmetiska kunskaper. Inom aritmetiken kan elever ofta använda informella metoder, medan algebraiska aktiviteter kräver en större medvetenhet om matematiska strukturer. Man har därför hävdat att elevers svårigheter att hantera algebraiska uttryck kan bero på saknad förståelse av strukturen i aritmetiska uttryck.  Syftet med denna studie är att undersöka hur elever i årskurs 5 beräknar och strukturerar utvecklade aritmetiska uttryck, det vill säga, numeriska uttryck med flera räkneoperationer, som exempelvis 5 · 6 + 4 · 2 · 3. I denna studie behandlas numeriska uttryck med tre eller fyra operationer.  I studien ingick 116 elever från tre olika skolor. Analysen baseras på data från lösningar av uppgifter på ett skriftligt arbetsblad. Arbetsbladet bestod av tio aritmetiska räkneuppgifter, som eleverna arbetade med individuellt. I analysen av data framkom olika metoder, som eleverna använde för att strukturera och beräkna de aritmetiska uttrycken, speciellt fyra metoder var återkommande i flera uppgifter. Genom de olika tillvägagångssätten som eleverna använde för att beräkna matematiska uttryck kunde olika sätt att skapa struktur upptäckas. Många elever utgick från uttryckens ytliga struktur och endast få elever visade förmåga att urskilja uttryckens dolda struktur. / Some of the difficulties students experience in algebra can be due to lack of understanding of the structure in mathematical expressions. Structure, in this context, refers to how a mathematical entity consists of its parts, and how these parts are related to each other. Previous studies also indicate that students’ difficulties in algebra devolve upon a lack of arithmetical knowledge. In arithmetic, students can manage by using informal methods, while algebraic activities require a greater awareness of mathematical structures. It has therefore been argued that students’ difficulties with algebraic expressions are caused by a lack of knowledge of the structure in arithmetic expressions.  The purpose of this study is to investigate how 5th grade students calculate and structure longer arithmetic expressions, meaning numerical expressions with several operations, for example, 5 · 6 + 4 · 2 · 3. This study covers numerical expressions with three or four operations.  The study includes 116 students from three different schools. The analysis is based on data from solutions of tasks on a written worksheet. The worksheet consisted of ten arithmetic calculation assignments that the students worked with individually. The analysis of the data revealed different approaches that students used to structure and calculate the arithmetic expressions, particularly four methods were used in several tasks. Through the different approaches that students used to calculate mathematical expressions, different ways to create structure could be discovered. Many students based their calculations on the surface structure of an expression and only a few students seemed to be able to identify the hidden structure of an expression.

Designing efficient code in practice for a given computation is a hard task. In this thesis, we tackle this issue in two different situations. The first part of the thesis introduces some algorithmic improvements in structured linear algebra. We first show how to extend an algorithm by Cardinal for inverting Cauchy-like matrices to the other common structures. This approach, which mainly relies on products of the type "structured matrix × matrix", leads to a theoretical speed-up of a factor up to 7 that we also observe in practice. Then, we extend some works on Toeplitz-like matrices and prove that, for any of the common structures, the product of an n×n structured matrix of displacement rank α by an n×α matrix can be computed in Õ(α^(ω-1)n). This leads to direct inversion algorithms in Õ(α^(ω-1)n) , that do not rely on a reduction to the Toeplitz-like case. The second part of the thesis deals with the implementation of arithmetic expressions. This topic raises several issues like finding the minimum number of operations, and maximizing the speed or the accuracy when using some finite-precision arithmetic. Making use of the inductive nature of arithmetic expressions enables the design of algorithms that help to answer such questions. We thus present a set of algorithms for generating evaluation schemes, counting them, and optimizing them according to one or several criteria. These algorithms are part of a library that we have developed and used, among other things, in order to decrease the running time of a code generator for a mathematical library, and to study optimality issues about the evaluation of a small degree polynomial with scalar coefficients at a matrix point.

This thesis investigates the central issues underlying graph analysis, namely, scalability and quality. We first study the incremental problems for graph queries, which aim to compute the changes to the old query answer, in response to the updates to the input graph. The incremental problem is called bounded if its cost is decided by the sizes of the query and the changes only. No matter how desirable, however, our first results are negative: for common graph queries such as graph traversal, connectivity, keyword search and pattern matching, their incremental problems are unbounded. In light of the negative results, we propose two new characterizations for the effectiveness of incremental computation, and show that the incremental computations above can still be effectively conducted, by either reducing the computations on big graphs to small data, or incrementalizing batch algorithms by minimizing unnecessary recomputation. We next study the problems with regards to improving the quality of the graphs. To uniquely identify entities represented by vertices in a graph, we propose a class of keys that are recursively defined in terms of graph patterns, and are interpreted with subgraph isomorphism. As an application, we study the entity matching problem, which is to find all pairs of entities in a graph that are identified by a given set of keys. Although the problem is proved to be intractable, and cannot be parallelized in logarithmic rounds, we provide two parallel scalable algorithms for it. In addition, to catch numeric inconsistencies in real-life graphs, we extend graph functional dependencies with linear arithmetic expressions and comparison predicates, referred to as NGDs. Indeed, NGDs strike a balance between expressivity and complexity, since if we allow non-linear arithmetic expressions, even of degree at most 2, the satisfiability and implication problems become undecidable. A localizable incremental algorithm is developed to detect errors using NGDs, where the cost is determined by small neighbors of nodes in the updates instead of the entire graph. Finally, a rule-based method to clean graphs is proposed. We extend graph entity dependencies (GEDs) as data quality rules. Given a graph, a set of GEDs and a block of ground truth, we fix violations of GEDs in the graph by combining data repairing and object identification. The method finds certain fixes to errors detected by GEDs, i.e., as long as the GEDs and the ground truth are correct, the fixes are assured correct as their logical consequences. Several fundamental results underlying the method are established, and an algorithm is developed to implement the method. We also parallelize the method and guarantee to reduce its running time with the increase of processors.

Le développement de code efficace en pratique pour effectuer un calcul donné est un problème difficile. Cette thèse présente deux situations où nous avons été confronté à ce problème. La première partie de la thèse propose des améliorations au niveau algorithmique dans le cadre de l'algèbre linéaire structurée. Nous montrons d'abord comment étendre un algorithme de Cardinal pour l'inversion de matrices de type Cauchy afin de traiter les autres structures classiques. Cette approche, qui repose essentiellement sur des produits de type « matrice structurée × matrice », conduit à une accélération d'un facteur allant jusqu'à 7 en théorie et constaté en pratique. Ensuite, nous généralisons des travaux sur les matrices de type Toeplitz afin de montrer comment, pour les structures classiques, calculer le produit d'une matrice structurée n×n et de rang de déplacement α par une matrice n×α en Õ(α^(ω-1)n). Cela conduit à des algorithmes en Õ(α^(ω-1)n) pour l'inversion de matrices structurées, sans avoir à passer par des matrices de type Toeplitz. La deuxième partie de la thèse traite de l'implantation d'expressions arithmétiques. Ce sujet soulève de nombreuses questions comme le nombre d'opérations minimum, la vitesse, ou encore la précision des calculs en arithmétique approchée. En exploitant la nature inductive des expressions arithmétiques, il est possible de développer des algorithmes aidant à répondre à ces questions. Nous présentons ainsi plusieurs algorithmes de génération de schémas d'évaluation, de comptage et d'optimisation selon un ou plusieurs critères. Ces algorithmes ont été implanté dans une librairie qui a en autre été utilisée pour accélérer un logiciel de génération de code pour une librairie mathématique, et pour étudier des questions d'optimalité pour le problème de l'évaluation d'un polynôme à coefficients scalaires de petit degré en une matrice. / Designing efficient code in practice for a given computation is a hard task. In this thesis, we tackle this issue in two different situations. The first part of the thesis introduces some algorithmic improvements in structured linear algebra. We first show how to extend an algorithm by Cardinal for inverting Cauchy-like matrices to the other common structures. This approach, which mainly relies on products of the type "structured matrix × matrix", leads to a theoretical speed-up of a factor up to 7 that we also observe in practice. Then, we extend some works on Toeplitz-like matrices and prove that, for any of the common structures, the product of an n×n structured matrix of displacement rank α by an n×α matrix can be computed in Õ(α^(ω-1)n). This leads to direct inversion algorithms in Õ(α^(ω-1)n) , that do not rely on a reduction to the Toeplitz-like case. The second part of the thesis deals with the implementation of arithmetic expressions. This topic raises several issues like finding the minimum number of operations, and maximizing the speed or the accuracy when using some finite-precision arithmetic. Making use of the inductive nature of arithmetic expressions enables the design of algorithms that help to answer such questions. We thus present a set of algorithms for generating evaluation schemes, counting them, and optimizing them according to one or several criteria. These algorithms are part of a library that we have developed and used, among other things, in order to decrease the running time of a code generator for a mathematical library, and to study optimality issues about the evaluation of a small degree polynomial with scalar coefficients at a matrix point.