text:
powerTransform {car} R Documentation

## Finding Univariate or Multivariate Power Transformations

### Description

powerTransform uses the maximum likelihood-like approach of Box and Cox (1964) to select a transformatiion of a univariate or multivariate response for normality, linearity and/or constant variance. Available families of transformations are the default Box-Cox power family and two additioal families that are modifications of the Box-Cox family that allow for (a few) negative responses. The summary method automatically computes two or three likelihood ratio type tests concerning the transformation powers.

### Usage

powerTransform(object, ...)

## Default S3 method:
powerTransform(object, family="bcPower", ...)

## S3 method for class 'lm'
powerTransform(object, family="bcPower", ...)

## S3 method for class 'formula'
powerTransform(object, data, subset, weights, na.action,
family="bcPower", ...)

## S3 method for class 'lmerMod'
powerTransform(object, family="bcPower", ...)

### Arguments

 object This can either be an object of class lm or lmerMod, a formula, or a matrix or vector; see below. family The quoted name of a family of transformations. The available options are "bcPower" for the default for the Box-Cox power family; "bcnPower" for a two-parameter modification of the Box-Cox family that allows negative responses (Hawkins and Weisberg (2017)), and the "yjPower" family (Yeo and Johnson(2000)), another modifiation of the Box-Cox family that allows a few negative values. All three families are documented at bcPower. data A data frame or environment, as in ‘lm’. subset Case indices to be used, as in ‘lm’. weights Weights as in ‘lm’. na.action Missing value action, as in ‘lm’. ... Additional arguments that used in the interative algorithm; defaults are generally adequate. For use with the bcnPower family, a convergence criterion can be set with conv=.0001 the default, and a minimum positive value of the location parameter can be set, with default gamma.min=.1.

### Details

This function implements the Box and Cox (1964) method of selecting a power transformation of a variable toward normality, and its generalization by Velilla (1993) to a multivariate response. Cook and Weisberg (1999) and Weisberg (2014) suggest the usefulness of transforming a set of predictors z1, z2, z3 for multivariate normality. It also includes two additional families that allow for negative values.

If the object argument is of class ‘lm’ or ‘lmerMod’, the Box-Cox procedure is applied to the conditional distribution of the response given the predictors. For ‘lm’ objects, the respose may be multivariate, and each column will have its own transformation. With ‘lmerMod’ the response must be univariate.

The object argument may also be a formula. For example, z ~ x1 + x2 + x3 will estimate a transformation for the response z from a family after fitting a linear model with the given formula. cbind(y1, y2, y3) ~ 1 specifies transformations to multivariate normality with no predictors. A vector value for object, for example powerTransform(ais$LBM), is equivalent topowerTransform(LBM ~ 1, ais). Similarly, powerTransform(cbind(ais$LBM, ais$SSF)), where the first argument is a matrix rather than a formula is equivalent to specification of a mulitvariate linear model powerTransform(cbind(LBM, SSF) ~ 1, ais). Three families of power transformations are available. The default Box-Cox power family (family="bcPower") of power transformations effectively replaces a vector by that vector raised to a power, generally in the range from -3 to 3. For powers close to zero, the log-transformtion is suggested. In practical situations, after estimating a power using the powerTransform function, a variable would be replaced by a simple power transformation of it, for example, if \lambda\approx 0.5, then the correspoding variable would be replaced by its square root; if \lambda is close enough to zero, the the variable would be replaced by its natural logarithm. The Box-Cox family requires the responses to be strictly positive. The family="bcnPower", or Box-Cox with negatives, family proposed by Hawkins and Weisberg (2017) allows for (a few) non-positive values, while allowing for the transformed data to be interpreted similarly to the interpretation of Box-Cox transformed values. This family is the Box-Cox transformation of z = .5 * (y + (y^2 + \gamma^2)^{1/2}) that depends on a location parameter \gamma. The quantity z is positive for all values of y. If \gamma = 0 and y is strictly positive, then the Box-Cox and the bcnPower transformations are identical. When fitting the Box-Cox with negatives family, lambda is restricted to the range [-3, 3], and gamma is restricted to the range from gamma.min=.1 to the largest positive value of the variable, since values outside these ranges are unreasonable in practice. The value of gamma.min can be changed with an argument to powerTransform. The final family family="yjPower" uses the Yeo-Johnson transformation, which is the Box-Cox transformation of U+1 for nonnegative values, and of |U|+1 with parameter 2-\lambda for U negative and thus it provides a family for fitting when (a few) observations are negative. Because of the unusual constraints on the powers for positive and negative data, this transformation is not used very often, as results are difficult to interpret. In practical problems, a variable would be replaced by its Yeo-Johnson transformation computed using the yjPower function. The function testTransform is used to obtain likelihood ratio tests for any specified value for the transformation parameter(s). Computations maximize the likelihood-like functions described by Box and Cox (1964) and by Velilla (1993). For univariate responses, the computations are very stable and problems are unlikely, although for ‘lmer’ models computations may be very slow because the model is refit many times. For multivariate responses with the bcnPower family, the computing algorithm may fail. In this case we recommend adding the argument itmax = 1 to the call to powerTransform. This will return the starting value estimates of the transformation parameters, fitting a d-dimensional response as if all the d responses were independent. ### Value An object of class powerTransform or class bcnPowerTransform if family="bcnPower" that inherits from powerTransform is returned, including the components listed below. A summary method presents estimated values for the transformation power lambda and for the ‘bcnPower’ family the location parameter gamma as well. Standard errors and Wald 95% confidence intervals based on the standard errors are computed from the inverse of the sample Hessian matrix evaluted at the estimates. The interval estimates for the gamma parameters will generally be very wide, reflecting little information available about the location parameter. Likelihood ratio type tests are also provided. For the ‘bcnPower’ family these are based on the profile loglikelihood for lambda alone; that is, we treat gamma as a nusiance parameter and average over it. The components of the returned object includes  lambda Estimated transformation parameter roundlam Convenient rounded values for the estimates. These rounded values will usually be the desired transformations. gamma Estimated location parameters for bcnPower, NULL otherwise invHess Estimated covariance matrix of the estimated parameters llik Value of the log-likelihood at the estimates The summary method for powerTransform returns an array with columns labeled "Est Power" for the value of lambda that maximizes the likelihood; "Rounded Pwr" for roundlam, and columns "Wald Lwr Bnd" and "Wald Ur Bnd" for a 95 percent Wald normal theory confidence interval for lambda computed as the estimate plus or minus 1.96 times the standard error. ### Author(s) Sanford Weisberg, <sandy@umn.edu> ### References Box, G. E. P. and Cox, D. R. (1964) An analysis of transformations. Journal of the Royal Statisistical Society, Series B. 26 211-46. Cook, R. D. and Weisberg, S. (1999) Applied Regression Including Computing and Graphics. Wiley. Fox, J. and Weisberg, S. (2019) An R Companion to Applied Regression, Third Edition, Sage. Hawkins, D. and Weisberg, S. (2017) Combining the Box-Cox Power and Generalized Log Transformations to Accomodate Nonpositive Responses In Linear and Mixed-Effects Linear Models South African Statistics Journal, 51, 317-328. Velilla, S. (1993) A note on the multivariate Box-Cox transformation to normality. Statistics and Probability Letters, 17, 259-263. Weisberg, S. (2014) Applied Linear Regression, Fourth Edition, Wiley. Yeo, I. and Johnson, R. (2000) A new family of power transformations to improve normality or symmetry. Biometrika, 87, 954-959. ### See Also testTransform, bcPower, bcnPower, transform, optim, boxCox. ### Examples # Box Cox Method, univariate summary(p1 <- powerTransform(cycles ~ len + amp + load, Wool)) # fit linear model with transformed response: coef(p1, round=TRUE) summary(m1 <- lm(bcPower(cycles, p1$roundlam) ~ len + amp + load, Wool))

# Multivariate Box Cox uses Highway1 data
summary(powerTransform(cbind(len, adt, trks, sigs1) ~ 1, Highway1))

# Multivariate transformation to normality within levels of 'htype'
summary(a3 <- powerTransform(cbind(len, adt, trks, sigs1) ~ htype, Highway1))

# test lambda = (0 0 0 -1)
testTransform(a3, c(0, 0, 0, -1))

# save the rounded transformed values, plot them with a separate
# color for each highway type
transformedY <- bcPower(with(Highway1, cbind(len, adt, trks, sigs1)),
coef(a3, round=TRUE))
## Not run:  # generates a smoother warning
scatterplotMatrix( ~ transformedY|htype, Highway1)

## End(Not run)

# With negative responses, use the bcnPower family
m2 <- lm(I1L1 ~ pool, LoBD)
summary(p2 <- powerTransform(m2, family="bcnPower"))
testTransform(p2, .5)
summary(powerTransform(update(m2, cbind(LoBD$I1L2, LoBD$I1L1) ~ .), family="bcnPower"))

## Not run:  # takes a few seconds:
# multivariate bcnPower, with 8 responses
summary(powerTransform(update(m2, as.matrix(LoBD[, -1]) ~ .), family="bcnPower"))
# multivariate bcnPower, fit with one iteration using starting values as estimates
summary(powerTransform(update(m2, as.matrix(LoBD[, -1]) ~ .), family="bcnPower", itmax=1))

## End(Not run)

# mixed effects model
## Not run:  # uses the lme4 package
data <- reshape(LoBD[1:20, ], varying=names(LoBD)[-1], direction="long", v.names="y")
names(data) <- c("pool", "assay", "y", "id")
data$assay <- factor(data$assay)
require(lme4)
m2 <- lmer(y ~ pool + (1|assay), data)
summary(l2 <- powerTransform(m2, family="bcnPower", verbose=TRUE))

## End(Not run)

[Package car version 3.1-0 Index]


text:
# Prove $\frac{x-1}{x}$ has exactly two real solutions [closed]

How do I prove $\frac{x-1}{x}=0$ has two real solutions?

I know it has one solution at $x=1$, but the question said "find the 2 real solutions", so I was confused if I was overlooking something. Maybe it's an error in the question.

Does anybody have any ideas to this problem?

## closed as unclear what you're asking by user137731, Jack D'Aurizio, ajotatxe, qbert, Jean MarieOct 2 '16 at 21:43

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• Usually one talk about solutions when there is an equation (or inequation) involve, but in your question there was only one function. Are you sure you should not include some $=$, or some inequality? – Darío G Oct 2 '16 at 21:18
• Shouldn't this be equal to something if it is to have "solutions?" I don't see an equation. Unless if you're asking if $f(x) = \frac{x-1}{x}$ has exactly two real roots. – Sean Roberson Oct 2 '16 at 21:19
• This question is not well posed just yet. To what is it supposed to be equal? – B. Pasternak Oct 2 '16 at 21:19
• If roots are meant, there is only one. At the root of the denominator , the function has a pole. Maybe, the OP means "asymptotics". In this case, we actually have two , namely $x=0$ and $y=1$ – Peter Oct 2 '16 at 21:22
• Ah yes I meant (x-1)/x = 0 , I know it has one solution but the question said find the 2 real solutions so I was confused if I was overlooking something. Maybe it's an error in the question. – Curtis Cleary Oct 2 '16 at 21:39

Well, assuming you want to find the roots of $f(x)=\frac{x-1}{x}$: $$f(x)=1-\frac{1}{x}$$ The roots are given when $f(x)=0$, so $$1=\frac{1}{x}\Rightarrow x=1$$
You could even plot $f(x)$ to see it:

format: plain


text:
# Software bug

(Redirected from Anomaly in software)
To report a MediaWiki error on Wikipedia, see Wikipedia:Bug reports.
Software development process
Core activities
Methodologies and frameworks
Supporting disciplines
Tools
Standards and BOKs

A software bug is an error, flaw, failure or fault in a computer program or system that causes it to produce an incorrect or unexpected result, or to behave in unintended ways. Most bugs arise from mistakes and errors made by people in either a program's source code or its design, or in frameworks and operating systems used by such programs, and a few are caused by compilers producing incorrect code. A program that contains a large number of bugs, and/or bugs that seriously interfere with its functionality, is said to be buggy or defective. Reports detailing bugs in a program are commonly known as bug reports, defect reports, fault reports, problem reports, trouble reports, change requests and so forth.

Bugs trigger errors that may in turn have a wide variety of ripple effects with varying levels of inconvenience to the user of the program. Some bugs have only a subtle effect on the program's functionality, and may thus lie undetected for a long time. More serious bugs may cause the program to crash or freeze. Others qualify as security bugs and might, for example, enable a malicious user to bypass access controls in order to obtain unauthorized privileges.

The results of bugs may be extremely serious. Bugs in the code controlling the Therac-25 radiation therapy machine were directly responsible for some patient deaths in the 1980s. In 1996, the European Space Agency's US\$1 billion prototype Ariane 5 rocket had to be destroyed less than a minute after launch due to a bug in the on-board guidance computer program. In June 1994, a Royal Air Force Chinook helicopter crashed into the Mull of Kintyre, killing 29. This was initially dismissed as pilot error, but an investigation by Computer Weekly uncovered sufficient evidence to convince a House of Lords inquiry that it may have been caused by a software bug in the aircraft's engine control computer.[1]

In 2002, a study commissioned by the US Department of Commerce's National Institute of Standards and Technology concluded that "software bugs, or errors, are so prevalent and so detrimental that they cost the US economy an estimated \$59 billion annually, or about 0.6 percent of the gross domestic product".[2]

## Etymology

Use of the term "bug" to describe inexplicable defects has been a part of engineering jargon for many decades and predates computers and computer software; it may have originally been used in hardware engineering to describe mechanical malfunctions. For instance, Thomas Edison wrote the following words in a letter to an associate in 1878:

It has been just so in all of my inventions. The first step is an intuition, and comes with a burst, then difficulties arise — this thing gives out and [it is] then that "Bugs" — as such little faults and difficulties are called — show themselves and months of intense watching, study and labor are requisite before commercial success or failure is certainly reached.[3]

The Middle English word bugge is the basis for the terms "bugbear" and "bugaboo", terms used for a monster.[4] Baffle Ball, the first mechanical pinball game, was advertised as being "free of bugs" in 1931.[5] Problems with military gear during World War II were referred to as bugs (or glitches).[6] In a book published in 1942, Louise Dickinson Rich, speaking of a powered ice cutting machine, said, "Ice sawing was suspended until the creator could be brought in to take the bugs out of his darling."[7]

A page from the Harvard Mark II electromechanical computer's log, featuring a dead moth that was removed from the device

The term "bug" was used in an account by computer pioneer Grace Hopper, who publicized the cause of a malfunction in an early electromechanical computer.[8] A typical version of the story is given by this quote:[9]

In 1946, when Hopper was released from active duty, she joined the Harvard Faculty at the Computation Laboratory where she continued her work on the Mark II and Mark III. Operators traced an error in the Mark II to a moth trapped in a relay, coining the term bug. This bug was carefully removed and taped to the log book. Stemming from the first bug, today we call errors or glitches in a program a bug.

Hopper was not actually the one who found the insect, as she readily acknowledged. The date in the log book was September 9, 1947,[10][11] although sometimes erroneously reported as 1945.[12] The operators who did find it, including William "Bill" Burke, later of the Naval Weapons Laboratory, Dahlgren, Virginia,[13] were familiar with the engineering term and, amused, kept the insect with the notation "First actual case of bug being found." Hopper loved to recount the story.[14] This log book, complete with attached moth, is part of the collection of the Smithsonian National Museum of American History.[11]

The related term "debug" also appears to predate its usage in computing: the Oxford English Dictionary's etymology of the word contains an attestation from 1945, in the context of aircraft engines.[15]

## History

The concept that software might contain errors dates back to Ada Lovelace's 1843 notes on the analytical engine, in which she speaks of the possibility of program "cards" for Charles Babbage's analytical engine being erroneous:

... an analysing process must equally have been performed in order to furnish the Analytical Engine with the necessary operative data; and that herein may also lie a possible source of error. Granted that the actual mechanism is unerring in its processes, the cards may give it wrong orders.

## Prevalence

In software development projects, a "mistake" or "fault" may be introduced at any stage during development. Bugs are a consequence of the nature of human factors in the programming task. They arise from oversights or mutual misunderstandings made by a software team during specification, design, coding, data entry and documentation. For example, in creating a relatively simple program to sort a list of words into alphabetical order, one's design might fail to consider what should happen when a word contains a hyphen. Perhaps, when converting the abstract design into the chosen programming language, one might inadvertently create an off-by-one error and fail to sort the last word in the list. Finally, when typing the resulting program into the computer, one might accidentally type a "<" where a ">" was intended, perhaps resulting in the words being sorted into reverse alphabetical order.

Another category of bug is called a race condition that may occur when programs have multiple components executing at the same time, either on the same system or across multiple systems interacting across a network. If the components interact in a different order than the developers intended, it may break the logical flow of the program. These bugs may be difficult to detect or anticipate, since they may not occur during every execution of a program.

More complex bugs may arise from unintended interactions between different parts of a computer program. This frequently occurs because computer programs may be complex — millions of lines long in some cases — often having been programmed by many people over a great length of time, so that programmers are unable to mentally track every possible way in which parts may interact.

## Mistake metamorphism

There is ongoing debate over the use of the term "bug" to describe software errors.[16] One argument is that the word "bug" is divorced from a sense that a human being caused the problem, and instead implies that the defect arose on its own, leading to a push to abandon the term "bug" in favor of terms such as "defect", with limited success.[citation needed]

In software engineering, mistake metamorphism (from Greek meta = "change", morph = "form") refers to the evolution of a defect in the final stage of software deployment. Transformation of a "mistake" committed by an analyst in the early stages of the software development lifecycle, which leads to a "defect" in the final stage of the cycle has been called 'mistake metamorphism'.[17]

Different stages of a "mistake" in the entire cycle may be described as "mistakes", "anomalies", "faults", "failures", "errors", "exceptions", "crashes", "bugs", "defects", "incidents", or "side effects".[17]

## Prevention

The software industry has put much effort into finding methods for preventing programmers from inadvertently introducing bugs while writing software.[18][19] These include:

Programming style
While typos in the program code are often caught by the compiler, a bug usually appears when the programmer makes a logic error. Various innovations in programming style and defensive programming are designed to make these bugs less likely, or easier to spot. In some programming languages, so-called typos, especially of symbols or logical/mathematical operators, actually represent logic errors, since the mistyped constructs are accepted by the compiler with a meaning other than that which the programmer intended.
Programming techniques
Bugs often create inconsistencies in the internal data of a running program. Programs can be written to check the consistency of their own internal data while running. If an inconsistency is encountered the program may immediately halt so that the bug may be located and fixed. Alternatively, the program may simply inform the user, attempt to correct the inconsistency and continue running.
Development methodologies
There are several schemes for managing programmer activity so that fewer bugs are produced. Many of these fall under the discipline of software engineering (which addresses software design issues as well). For example, formal program specifications are used to state the exact behavior of programs so that design bugs may be eliminated. Unfortunately, formal specifications are impractical or impossible[citation needed] for anything but the shortest programs, because of problems of combinatorial explosion and indeterminacy.
In modern times, popular approaches include automated unit testing and automated acceptance testing (sometimes going to the extreme of test-driven development), and agile software development (which is often combined with, or even in some cases mandates, automated testing). All of these approaches are supposed to catch bugs and poorly-specified requirements soon after they are introduced, which should make them easier and cheaper to fix, and to catch at least some of them before they enter into production use.
Programming language support
Programming languages often include features which help programmers prevent bugs, such as static type systems, restricted namespaces and modular programming, among others. For example, when a programmer writes (pseudocode) `LET REAL_VALUE PI = "THREE AND A BIT"`, although this may be syntactically correct, the code fails a type check. Depending on the language and implementation, this may be caught by the compiler or at run-time. In addition, many recently invented languages have deliberately excluded features which may easily lead to bugs, at the expense of making code slower than it need be: the general principle being that, because of Moore's law, computers get faster and software engineers get slower; it is almost always better to write simpler, slower code than "clever", inscrutable code, especially considering that maintenance cost is substantial. For example, the Java programming language does not support pointer arithmetic; implementations of some languages such as Pascal and scripting languages often have runtime bounds checking of arrays, at least in a debugging build.
Code analysis
Tools for code analysis help developers by inspecting the program text beyond the compiler's capabilities to spot potential problems. Although in general the problem of finding all programming errors given a specification is not solvable (see halting problem), these tools exploit the fact that human programmers tend to make the same kinds of mistakes when writing software.
Instrumentation
Tools to monitor the performance of the software as it is running, either specifically to find problems such as bottlenecks or to give assurance as to correct working, may be embedded in the code explicitly (perhaps as simple as a statement saying `PRINT "I AM HERE"`), or provided as tools. It is often a surprise to find where most of the time is taken by a piece of code, and this removal of assumptions might cause the code to be rewritten.

## Debugging

The typical bug history (GNU Classpath project data). A new bug submitted by the user is unconfirmed. Once it has been reproduced by a developer, it is a confirmed bug. The confirmed bugs are later fixed. Bugs belonging to other categories (unreproducible, will not be fixed, etc.) are usually in the minority
Main article: Debugging

Finding and fixing bugs, or "debugging", has always been a major part of computer programming. Maurice Wilkes, an early computing pioneer, described his realization in the late 1940s that much of the rest of his life would be spent finding mistakes in his own programs.[20] As computer programs grow more complex, bugs become more common and difficult to fix. Often programmers spend more time and effort finding and fixing bugs than writing new code. Software testers are professionals whose primary task is to find bugs, or write code to support testing. On some projects, more resources may be spent on testing than in developing the program.

Usually, the most difficult part of debugging is finding the bug in the source code. Once it is found, correcting it is usually relatively easy. Programs known as debuggers exist to help programmers locate bugs by executing code line by line, watching variable values, and other features to observe program behavior. Without a debugger, code may be added so that messages or values may be written to a console (for example with printf in the C programming language) or to a window or log file to trace program execution or show values.

However, even with the aid of a debugger, locating bugs is something of an art. It is not uncommon for a bug in one section of a program to cause failures in a completely different section,[citation needed] thus making it especially difficult to track (for example, an error in a graphics rendering routine causing a file I/O routine to fail), in an apparently unrelated part of the system.

Sometimes, a bug is not an isolated flaw, but represents an error of thinking or planning on the part of the programmer. Such logic errors require a section of the program to be overhauled or rewritten. As a part of Code review, stepping through the code modelling the execution process in one's head or on paper may often find these errors without ever needing to reproduce the bug as such, if it can be shown there is some faulty logic in its implementation.

But more typically, the first step in locating a bug is to reproduce it reliably. Once the bug is reproduced, the programmer may use a debugger or some other tool to monitor the execution of the program in the faulty region, and find the point at which the program went astray.

It is not always easy to reproduce bugs. Some are triggered by inputs to the program which may be difficult for the programmer to re-create. One cause of the Therac-25 radiation machine deaths was a bug (specifically, a race condition) that occurred only when the machine operator very rapidly entered a treatment plan; it took days of practice to become able to do this, so the bug did not manifest in testing or when the manufacturer attempted to duplicate it. Other bugs may disappear when the program is run with a debugger; these are heisenbugs (humorously named after the Heisenberg uncertainty principle).

Debugging is still a tedious task requiring considerable effort. Since the 1990s, particularly following the Ariane 5 Flight 501 disaster, there has been a renewed interest in the development of effective automated aids to debugging. For instance, methods of static code analysis by abstract interpretation have already made significant achievements, while still remaining much of a work in progress.

As with any creative act, sometimes a flash of inspiration will show a solution, but this is rare and, by definition, cannot be relied on.

There are also classes of bugs that have nothing to do with the code itself. If, for example, one relies on faulty documentation or hardware, the code may be written perfectly properly to what the documentation says, but the bug truly lies in the documentation or hardware, not the code. However, it is common to change the code instead of the other parts of the system, as the cost and time to change it is generally less. Embedded systems frequently have workarounds for hardware bugs, since to make a new version of a ROM is much cheaper than remanufacturing the hardware, especially if they are commodity items.

## Bug management

Bug management may be more than bug tracking alone but there is no industry-wide standard. Proposed changes to software – bugs as well as enhancement requests and even entire releases – are commonly tracked and managed using bug tracking systems or issue tracking systems. The items added may be called defects, tickets, issues, or, following the agile development paradigm, stories and epics. The systems allow or even require some type of categorization of each issue. Categories may be objective, subjective or a combination, such as version number, area of the software, severity and priority, as well as what type of issue it is, such as a feature request or a bug.

### Severity of a bug

Given a bug is impairing a user scenario, one can easily see the impact the bug has. This impact may be tangible as tangible as of data loss, immediate losses in terms of money, or may be indirect – loss of goodwill or man hours, and eventually business. This impact is said to be the severity of a bug: "the impact a bug causes when encountered by users". Thus, severity, as a software metric does have a very precise meaning. Unfortunately, severity levels are not standardized in industry and are decided by each software producer, if they are even used. This is because impacts differ across the industry. A crash in a video game has a totally different impact than a crash in the browser, or real time monitoring system. Irrespective of that, crashes would be generally categorised high severity in the respective fields. For example, bug severity levels might be "crash or hang", "no workaround" (meaning there is no way the customer can accomplish a given task), "has workaround" (meaning there is a way for the user to recover and accomplish the task), "UI" or "visual defect" (for example, a missing image or displaced button or form element), or "documentation error". Some software publishers use more qualified severities such as "critical", "high", "low," "blocker," or "trivial".[21] The severity of a bug may be a separate category to its priority for fixing, and the two may be quantified and managed separately.

### Priority of a bug

Given a bug, how fast it needs to get fixed is defined by the software metric priority. How the priority for fixing is used is decided internally by each software producer. Priorities are sometimes numerical and sometimes words, such as "critical," "high," "low" or "deferred"; note that these may be similar or even identical to severity ratings when looking at different software producers. For example, a software company may decide that priority 1 bugs are always to be fixed for the next release, whereas "5" could mean its fix is put off – sometimes indefinitely.

### Connection between priority and severity

If a flaw is found in an application which causes it to crash, yet the crash is so rare and takes, say, ten extremely unusual or unlikely steps to produce it, management may set its priority as "low" or even "will not fix." Thus it is easily seen that Priority is a function of probability of a bug to occur, and Severity (impact) of the bug. In specificity, priority is a strictly increasing function of both probability of the bug occurrence and severity. Given probability p = 1, the severity defines the priority. When p = 0, the bug, in all probability needs not to be fixed at all, however we may have a priority strictly proportional to the severity. In the same way, when Severity S=0 for a bug, we may have a priority strictly proportional to the probability.

One may axiomatize the priority function as any function having above characteristics, for example this very simplified function works : ${\displaystyle P(p,s)=B-\lceil kpS\rceil }$ where p is the probability while S is the severity, with k a scaling constant, and to invert the value B is the base. The ceiling function is used to get the domain of priority to only integers. It also assigns priority-B to almost never occurring bugs. Industry standard practice is to use an inverted scale, so that highest priority are low numbers, example priority 0, priority 1, while lowest priority are bigger numbers, i.e. priority 3, priority 4... etc.

### Software releases

It is common practice for software to be released with known bugs that are considered "non-critical" as defined by the software producer(s). While software products may, by definition, contain any number of unknown bugs, measurements during testing can provide an estimate of the number of likely bugs remaining; this becomes more reliable the longer a product is tested and developed. Most big software projects maintain two lists of "known bugs" – those known to the software team, and those to be told to users.[citation needed] The second list informs users about bugs that are not fixed in the current release, or not fixed at all, and a workaround may be offered.

A software publisher may opt not to fix a particular bug for a number of reasons, including:

• A deadline must be met and priorities are such that only those above a certain severity are fixed for the current software release.
• The bug is already fixed in an upcoming release, and it is not serious enough to warrant an immediate update or patch
• The changes to the code required to fix the bug are too costly, will take too long for the current release, or affect too many other areas of the software.
• Users may be relying on the undocumented, buggy behavior; it may introduce a breaking change.
• The problem is in an area which will be obsolete with an upcoming release; fixing it is unnecessary.
• It's "not a bug". A misunderstanding has arisen between expected and perceived behavior, when such misunderstanding is not due to confusion arising from design flaws, or faulty documentation.

The amount and type of damage a software bug may cause naturally affects decision-making, processes and policy regarding software quality. In applications such as manned space travel or automotive safety, since software flaws have the potential to cause human injury or even death, such software will have far more scrutiny and quality control than, for example, an online shopping website. In applications such as banking, where software flaws have the potential to cause serious financial damage to a bank or its customers, quality control is also more important than, say, a photo editing application. NASA's Software Assurance Technology Center managed to reduce the number of errors to fewer than 0.1 per 1000 lines of code (SLOC)[citation needed] but this was not felt to be feasible for projects in the business world.

A school of thought popularized by Eric S. Raymond as Linus's Law says that popular open-source software has more chance of having few or no bugs than other software, because "given enough eyeballs, all bugs are shallow".[22] This assertion has been disputed, however: computer security specialist Elias Levy wrote that "it is easy to hide vulnerabilities in complex, little understood and undocumented source code," because, "even if people are reviewing the code, that doesn't mean they're qualified to do so."[23]

## Security vulnerabilities

Malicious software may attempt to exploit known vulnerabilities in a system–which may or may not be bugs. Viruses and other malicious software are not bugs in themselves–they are typically programs that are doing precisely what they were designed to do. In addition, it is often a security bug in a computer system that allows malicious software to work in the first place.

## Common types of computer bugs

• Conceptual error (code is syntactically correct, but the programmer or designer intended it to do something else).

### Syntax bugs

• Use of the wrong operator, such as performing assignment instead of equality test. For example, in some languages x=5 will set the value of x to 5 while x==5 will check whether x is currently 5 or some other number. In simple cases often the compiler may generate a warning. In many languages, the language syntax is deliberately designed to guard against this error.

### Interfacing bugs

• Incorrect API usage.
• Incorrect protocol implementation.
• Incorrect hardware handling.
• Incorrect assumptions of a particular platform.
• Incompatible systems. Often a proposed "new API" or new communications protocol may seem to work when both computers use the old version or both computers use the new version, but upgrading only the receiver exposes backward compatibility problems; in other cases upgrading only the transmitter exposes forward compatibility problems. Often it is not feasible to upgrade every computer simultaneously—in particular, in the telecommunication industry[24] or the internet.[25][26][27] Even when it is feasible to update every computer simultaneously, sometimes people accidentally forget to update every computer—the Knight Capital Group#2012 stock trading disruption involved one such incompatibility between the old API and a new API.

### Teamworking bugs

• Unpropagated updates; e.g. programmer changes "myAdd" but forgets to change "mySubtract", which uses the same algorithm. These errors are mitigated by the Don't Repeat Yourself philosophy.
• Comments out of date or incorrect: many programmers assume the comments accurately describe the code.
• Differences between documentation and the actual product.

## Well-known bugs

Main article: List of software bugs

A number of software bugs have become well-known, usually due to their severity: examples include various space and military aircraft crashes. Possibly the most famous bug is the Year 2000 problem, also known as the Y2K bug, in which it was feared that worldwide economic collapse would happen at the start of the year 2000 as a result of computers thinking it was 1900. (In the end, no major problems occurred.)

## In popular culture

• In Robert A. Heinlein's 1966 novel The Moon Is a Harsh Mistress, computer technician Manuel Davis blames a real bug for a (non-existent) failure of supercomputer Mike, presenting a dead fly as evidence.
• In the 1968 novel 2001: A Space Odyssey (and its corresponding 1968 film adaptation), a spaceship's onboard computer, HAL 9000, attempts to kill all its crew members. In the followup 1982 novel, 2010: Odyssey Two, and the accompanying 1984 film, 2010, it is revealed that this action was caused by the computer having been programmed with two conflicting objectives: to fully disclose all its information, and to keep the true purpose of the flight secret from the crew; this conflict caused HAL to become paranoid and eventually homicidal.
• In the 1999 American comedy Office Space, the plot focuses on an attempt by three employees to exploit the company's preoccupation with fixing the Y2K computer bug by infecting the company's computer system with a virus that sends rounded off pennies to a separate bank account. The plan backfires as the virus itself has its own bug which sends large amounts of money to the account prematurely.
• In 2000, Joe Trela correctly answered moth for the million dollar question: "What insect shorted out an early supercomputer and inspired the term Computer Bug." in the United States version of the game show Who Wants to be a Millionaire.
• The 2004 novel The Bug, by Ellen Ullman, is about a programmer's attempt to find an elusive bug in a database application.[citation needed]
• The 2008 Canadian film Control Alt Delete is about a computer programmer at the end of 1999 struggling to fix bugs at his company related to the year 2000 problem.

## Notes

1. ^ Prof. Simon Rogerson. "The Chinook Helicopter Disaster". Ccsr.cse.dmu.ac.uk. Retrieved September 24, 2012.
2. ^ "Software bugs cost US economy dear". Web.archive.org. June 10, 2009. Archived from the original on June 10, 2009. Retrieved September 24, 2012.
3. ^ Edison to Puskas, 13 November 1878, Edison papers, Edison National Laboratory, U.S. National Park Service, West Orange, N.J., cited in Thomas P. Hughes, American Genesis: A History of the American Genius for Invention, Penguin Books, 1989, ISBN 0-14-009741-4, on page 75.
4. ^ Computerworld staff (September 3, 2011). "Moth in the machine: Debugging the origins of 'bug'". Computerworld.
5. ^ "Baffle Ball". Internet Pinball Database. (See image of advertisement in reference entry)
6. ^ "Modern Aircraft Carriers are Result of 20 Years of Smart Experimentation". Life. June 29, 1942. p. 25. Retrieved November 17, 2011.
7. ^ Dickinson Rich, Louise (1942), We Took to the Woods, JB Lippincott Co, p. 93, LCCN 42024308, OCLC 405243.
8. ^ FCAT NRT Test, Harcourt, March 18, 2008
9. ^ "Danis, Sharron Ann: "Rear Admiral Grace Murray Hopper"". ei.cs.vt.edu. February 16, 1997. Retrieved January 31, 2010.
10. ^ "Bug", The Jargon File, ver. 4.4.7. Retrieved June 3, 2010.
11. ^ a b "Log Book With Computer Bug", National Museum of American History, Smithsonian Institution.
12. ^ "The First "Computer Bug", Naval Historical Center. But note the Harvard Mark II computer was not complete until the summer of 1947.
13. ^ IEEE Annals of the History of Computing, Vol 22 Issue 1, 2000
14. ^ James S. Huggins. "First Computer Bug". Jamesshuggins.com. Retrieved September 24, 2012.
15. ^ Journal of the Royal Aeronautical Society. 49, 183/2, 1945 "It ranged ... through the stage of type test and flight test and ‘debugging’ ..."
16. ^ "News at SEI 1999 Archive". cmu.edu.
17. ^ a b Testing Experience (Germany: testingexperience): 42. March 2012. ISSN 1866-5705. Missing or empty `|title=` (help) (subscription required)
18. ^ Huizinga, Dorota; Kolawa, Adam (2007). Automated Defect Prevention: Best Practices in Software Management. Wiley-IEEE Computer Society Press. p. 426. ISBN 0-470-04212-5.
19. ^ McDonald, Marc; Musson, Robert; Smith, Ross (2007). The Practical Guide to Defect Prevention. Microsoft Press. p. 480. ISBN 0-7356-2253-1.
20. ^ Maurice Wilkes Quotes
21. ^ "5.3. Anatomy of a Bug". bugzilla.org.
22. ^
23. ^ "Wide Open Source", Elias Levy, SecurityFocus, April 17, 2000
24. ^
25. ^ Mahbubur Rahman Syed. "Multimedia Networking: Technology, Management and Applications: Technology, Management and Applications". p. 398.
26. ^ Chwan-Hwa (John) Wu, J. David Irwin. "Introduction to Computer Networks and Cybersecurity". p. 500.
27. ^ RFC 1263: "TCP Extensions Considered Harmful" quote: "the time to distribute the new version of the protocol to all hosts can be quite long (forever in fact). ... If there is the slightest incompatibly between old and new versions, chaos can result."


text:
## anonymous 4 years ago Derivative help.

1. anonymous

d/dx (cosx)/e^x)

2. anonymous

3. amistre64

Dx(cos(x)*e^(-x)) and product rule it

4. anonymous

yeah, either use the product rule or the quotient rule (which in fact are equivalent)

5. anonymous

I got the answer but it's different what khanAcademy is showing me, so please give me the exact answer so that i can verify it.

6. anonymous

d/dx((cos(x))/e^x) = -e^(-x) (sin(x)+cos(x))

7. amistre64

cos'(x)*e^(-x) + cos(x)*e'^(-x) -sin(x)*e^(-x) - cos(x)*e^(-x)

8. anonymous

$\frac{d}{dx} \left(\frac{\cos (x)}{e^x}\right) = \frac{d}{dx} e^{-x}\cos (x) = e^{-x}(-\sin (x)) + \cos (x)(-e^{-x}) = -e^{-x} (\sin (x) + \cos (x))$

9. anonymous

hmm it wrote it off the page

10. anonymous

$\frac{d}{dx} \left(\frac{\cos (x)}{e^x}\right) = \frac{d}{dx} e^{-x}\cos (x)$ $= e^{-x}(-\sin (x)) + \cos (x)(-e^{-x})$ $= -e^{-x} (\sin (x) + \cos (x))$

11. anonymous

In the second step why the second term is e^-x, why you did not derviate it ?

12. anonymous

the derivative of $e^{-x}$ is $-e^{-x}$

13. anonymous

but i learned the derivative of e^x is e^x

14. anonymous

this is what khan academy says the answer is

15. anonymous

16. anonymous

yes that's right. Let's show, usin gthe chain rule that the derivative of e^{-x} is -e^{-x}. Find the derivative of $y = e^{-x}.$ Let t=-x. Then y = e^t $\frac{dy}{dx} = \frac{dy}{dt}\frac{dt}{dx} = e^{t}(-1) = e^{-x}(-1) = -e^{-x}$

17. anonymous

Yes, notice that answer a) is exactly the same as $-e^{-x} (\sin (x) + \cos (x))$

18. anonymous

That answer is likely derived from the quotient rule, which can be re-written as the product rule by making the requirement of multiplying by e^{-x} rather than dividing by e^x. Notice that this is equivalent.

19. anonymous

Thanks a lot, i understood it.


text:
# Approximation Algorithms and the Hardness of Approximation (14w5051)

Arriving in Banff, Alberta Sunday, August 3 and departing Friday August 8, 2014

## Organizers

(University of Illinois, Urbana-Champaign)

(University of Waterloo)

(Carnegie Mellon University)

(University of Alberta)

(Cornell University, School of Operations Research and Information Engineering)

## Objectives

The goals of the workshop are as follows:

(1) To bring together researchers in the fields of approximation algorithms (who work on finding algorithms with good approximation guarantees) and complexity theory (who work on finding hardness thresholds), and to stimulate the exchange of ideas and techniques between the two groups.

(2) To focus on a few key topics that could lead to deep new results in the areas of approximation algorithms, combinatorial optimization, hardness of approximation, and proof complexity. We describe a few ambitious topics below.

(2a) The most famous problem in all of discrete optimization is the Traveling Salesman Problem (TSP). Yet despite the attention paid to this problem, its approximability remains poorly understood. The best known approximation algorithm for the symmetric case is a 3/2-approximation algorithm due to Christofides from 1976. On the other hand, the known hardness-of-approximation results are weak, and there is a substantial gap between upper bounds and lower bounds.

Recently, there has been remarkable progress on some special cases of the TSP and on some variants of the TSP, but, as of now, there has been no improvement on the approximation guarantee of 3/2 for the TSP. Some of the recent advances were covered in the 2011 BIRS workshop, and a whole day was devoted to talks on the TSP and related problems. Many of these advances are based on new and beautiful connections with Probability Theory, coupled with technically difficult exploitation of methods and structures that are studied in Combinatorial Optimization. For example, Oveis Gharan, Saberi, and Singh [OSS11] used properties of strongly Rayleigh measures coupled with an elaborate analysis of the structure of near-minimum cuts to obtain the first improvement on the 3/2-approximation guarantee for a key special case called the graphic TSP; also, see Asadpour, et al. [AGMOS09]. The most recent result on this special case is a 7/5-approximation algorithm of Sebo and Vygen [SV12] that hinges on a probabilistic lemma of Momke and Svensson [MS11] coupled with an in-depth and novel analysis of structures that are well known in Combinatorial Optimization. An, Kleinberg, and Shmoys [AKS12] improved on a 20-year old 5/3-approximation guarantee of Hoogeveen [H91] for the s-t path TSP, which is a variant of TSP; they use a randomized rounding algorithm, and their improvement uses probabilistic methods coupled with an analysis of near-minimum cuts. Very recently, Sebo [S12] has improved on this result to obtain an 8/5-approxmation guarantee, by using further probabilistic insights.

It has long been conjectured that there is a 4/3-approximation algorithm for the TSP, and a 3/2-approximation algorithm for the s-t path TSP. By re-focusing attention on these conjectures, our goal is to continue the momentum from the 2011 BIRS workshop on the TSP.

(2b) Another focus topic will be approximation algorithms for disjoint paths and related routing problems. These problems are intimately related to fundamental topics on structural graph theory as well as to multicommodity flows. At the 2011 BIRS workshop, Chuzhoy [C12] presented a plenary talk on her breakthrough work that obtained the first poly-logarithmic approximation algorithm with constant congestion for the maximum edge-disjoint paths problem (MEDP). This built on a long line of work and numerous tools. There has been subsequent exciting progress including the work of Chuzhoy and Li [CL12] who improved the congestion bound from 14 to 2.

Despite this progress, the approximability of the maximum disjoint paths problem is wide open if the congestion bound is kept at one. Let $n$ denote the number of nodes of the input graph. The known upper bound is $O(\sqrt{n})$ while the lower bound is only sub-logarithmic in $n$ (namely, $\Omega(\log^{\frac{1}{2}-\epsilon}{n})$), see Andrews et al. [ACGKTZ10]. The approximability threshold is poorly understood even for restricted instances such as planar graphs and graphs of bounded treewidth. The impetus from the recent results and tools promises to lead to exciting new advances on algorithms for routing problems. The results of Chuzhoy [C12] have been extended to the maximum node-disjoint paths problem with constant congestion by Chekuri and Ene [CE13]. In addition, there are strong connections to structural aspects of graph theory. The recent progress on disjoint path problems is based on proving the existence of routing structures whose size is proportional to the treewidth of the graph, see [CE13]. This points to further connections between the above algorithmic results and the theory of Graph Minors developed by Robertson and Seymour, [RS83].

Our aim is to start systematic explorations of this connection. On the one hand, this could lead to the design of powerful new algorithmic tools for some of the routing problems that arise in many applied areas, and on the other hand, it could provide new techniques for attacking some of the significant conjectures within the theory of Graph Minors.

(2c) A key component of the workshop will focus on the notorious Unique Games Conjecture (UGC) and surrounding issues in the complexity of optimization problems. Since its proposal in 2002 by Khot [K02], the UGC has led to major new (conditional) inapproximability results for constraint satisfaction problems (CSPs). This culminated in Raghavendra's 2009 work [R09] giving a polynomial-time algorithm for optimally approximating each CSP, assuming the UGC.

The workshop will explore two directions that are at the vanguard of UGC research: improving optimization algorithms via Lasserre / SOS-proofs methodology, and going beyond the UGC in complexity results.

Lasserre / SOS algorithms.

In 2011, it was shown that the powerful Lasserre SDP hierarchy of algorithms (see [L01], and also see [SA90], [LS91]) could be used to obtain a subexponential-time algorithm for Unique Games (UG) (as in Arora et al. [ABS10]) and some related problems, see Barak et al. [BRS11] and Guruswami et al. [GS11]. (The 2011 BIRS workshop included two talks on these topics, by Georgiou and Steurer.) These results are motivating further advances in optimization using Lasserre algorithms.

A very recent, important work of Barak et al. [BBHKSZ12] emphasized and applied the connection between Lasserre algorithms and Sum-of-Squares (SOS) proof complexity; they showed that the known hard instances'' of the UG problem can be analyzed by constant-degree SOS proofs, and hence solved by a polynomial-time algorithm. Subsequent research furthered the connection to proof complexity, see O'Donnell et al. [OZ13]. The organizers are eager to bring together researchers working on optimization algorithms and on proof complexity, with the belief that these newly developed connections may lead to dramatic breakthroughs in efficient approximation algorithms.

Beyond the UGC.

One emerging stream of current research is concerned with going beyond the UGC. In one direction, going beyond the UGC has involved upgrading'' known UG-hardness results to full-fledged NP-hardness results. New techniques in this area, such as smooth Label Cover'' (see Guruswami et al. [GRSW12] and Hastad [H12]) and PCPs robust gainst low-degree polynomials'' (see Chan [Chan12] and Khot et al. [KST12]), are giving hope that many optimization tasks known to be UG-hard'' can be proved to be NP-hard without needing to resolve the UGC.

In the other direction, going beyond the UGC involves introducing alternative conjectures which can lead to inapproximability results not provable via UGC; one example is the Projection Games Conjecture introduced at the 2011 BIRS workshop by Moshkovitz [M12].

(3) To include many younger researchers, and foster a relaxed interaction with established researchers. At present, we have informed only a small number of young researchers. If the workshop is approved, then we will invite other young researchers. Our goal is to have a third of the workshop participants from this group. We expect a good number of female participants, similar to the workshop 11w5117.

(4) To allow groups of Canadian researchers working in this area to meet, and either initiate or renew collaborations.

Timeliness and appropriateness of the workshop

The study of approximation algorithms and the hardness of approximation is one of the most exciting areas among researchers in theoretical computer science; every major conference in the field has several papers on these topics. Significant progress is being made. We give two examples of recent, dramatic innovations:

(1) Arora, Barak and Steurer [ABS10] recently presented a sub-exponential-time algorithm for Unique Games. This is a landmark result on one of the most perplexing questions in the area, namely the Unique Games Conjecture (UGC). While this result does not disprove the UGC, it gives strong indications that the UGC may not be true. The implication is that some of the remarkable tight approximation thresholds proved assuming the UGC need to be revisited; one possibility is that substantially deeper methods may be needed to prove the tightness of these approximation thresholds assuming the P.not.=NP conjecture.

(2) Chuzhoy and Li [CL12] (FOCS 2012) very recently presented an approximation algorithm for maximizing the numer of edge disjoint paths with congestion two that acieves a poly-logarithmic approximation guarantee with respect to a standard LP relaxation. This is a remarkable achievement, because their LP relaxation has an integrality ratio that is much higher (than poly-logarithmic) for congestion one, meaning that poly-logarithmic approximation guarantees for congestion one are not possible (based on their LP relaxation); moreover, qualitatively speaking, the approximation guarantee for congestion two is best possible, due to lower bounds from the area of hardness of approximation.

REFERENCES

[AKS12] H.-C.An, R.Kleinberg, and D.B.Shmoys: Improving Christofides' algorithm for the s-t path TSP. ACM STOC: 875-886 (2012)

[ACGKTZ10] M.Andrews, J.Chuzhoy, V.Guruswami, S.Khanna, K.Talwar, and L.Zhang: Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs. Combinatorica 30(5): 485-520 (2010)

[ABS10] S.Arora, B.Barak, and D.Steurer: Subexponential algorithms for Unique Games and related problems. IEEE FOCS: 563-572 (2010)

[ALN07] S.Arora, J.R.Lee, and A.Naor: Fre'chet embeddings of negative type metrics. Discrete & Computational Geometry 38(4): 726-739 (2007)

[ARV09] S.Arora, S.Rao, and U.V.Vazirani: Expander flows, geometric embeddings and graph partitioning. J.ACM: 56(2) (2009)

[AGMOS09] A.Asadpour, M.Goemans, A.Madry, S.Oveis Gharan, and A.Saberi: An O(log n/log log n)-approximation algorithm for the asymmetric Traveling Salesman Problem. ACM-SIAM SODA: 379-389 (2010)

[BRS11] B.Barak, P.Raghavendra, and D.Steurer: Rounding semidefinite programming hierarchies via global correlation. IEEE FOCS: 472-481 (2011)

[BBHKSZ12] B.Barak, F.Brandao, A.Harrow, J.Kelner, D.Steurer, and Y.Zhou. Hypercontractivity, sum-of-squares proofs, and their applications. ACM STOC: 307-326 (2012)

[Chan12] Siu On Chan. Approximation resistance from pairwise independent subgroups. Technical Report TR12-110, ECCC (2012)

[CE13] C.Chekuri, and A.Ene: Poly-logarithmic approximation for maximum node disjoint paths with constant congestion. To appear in ACM-SIAM SODA (2013)

[C12] J.Chuzhoy: Routing in undirected graphs with constant congestion. STOC: 855-874 (2012)

[CL12] J.Chuzhoy, and S.Li: A polylogarithimic approximation algorithm for Edge-Disjoint Paths with congestion 2. CoRR abs/1208.1272 (2012) To appear in IEEE FOCS (2012)

[F98] U.Feige: A threshold of $\ln{n}$ for approximating Set Cover. J. ACM 45(4): 634-652 (1998)

[GW95] M.X.Goemans, and D.P.Williamson: Improved approximation algorithms for Maximum Cut and Satisfiability problems using semidefinite programming. J. ACM 42(6): 1115-1145 (1995)

[GS11] V.Guruswami, A.K.Sinop: Lasserre hierarchy, higher eigenvalues, and approximation schemes for quadratic integer programming with PSD objectives. IEEE FOCS: 482-491 (2011)

[GRSW12] V.Guruswami, P.Raghavendra, R.Saket, and Y.Wu: Bypassing UGC from some optimal geometric inapproximability results. ACM-SIAM SODA: 699-717 (2012)

[H01] J.Hastad: Some optimal inapproximability results. J.ACM 48(4): 798-859 (2001)

[H12] J.Hastad: On the NP-hardness of Max-Not-2. Approx-Random: 170-181 (2012)

[H91] J.A.Hoogeveen: Analysis of Christofides' heuristic: Some paths are more difficult than cycles. Operations Research Letters 10: 291-295 (1991)

[J01] K.Jain: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21(1): 39-60 (2001)

[K02] S.Khot: On the power of unique 2-prover 1-round games. ACM STOC: 767-775 (2002)

[KKMO07] S.Khot, G.Kindler, E.Mossel, and R.O'Donnell: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput. 37(1): 319-357 (2007)

[KR08] S.Khot, and O.Regev: Vertex cover might be hard to approximate to within $2-\epsilon$. J. Comput. Syst. Sci. 74(3): 335-349 (2008)

[KST12] S.Khot, M.Safra, and M.Tulsiani. Towards an optimal query efficient PCP? Technical Report TR12-109, ECCC (2012)

[L01] J.B.Lasserre: An explicit exact SDP relaxation for nonlinear 0-1 programs. IPCO (Integer Programming and Combinatorial Optimization): 293-303 (2001)

[LRS11] L.Lau, R.Ravi, and M.Singh, Iterative Methods in Combinatorial Optimization. Cambridge University Press, Cambridge, U.K., 2011.

[LLR95] N.Linial, E.London, and Y.Rabinovich: The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2): 215-245 (1995)

[LS91] L.Lovasz, and A.Schrijver: Cones of matrices and set functions, and 0-1 optimization. SIAM Journal on Optimization 1: 166--190 (1991)

[MS11] T.Momke, and O.Svensson: Approximating graphic TSP by matchings. IEEE FOCS: 560-569 (2011)

[M12] D.Moshkovitz: The Projection Games Conjecture and the NP-hardness of $\ln{n}$-approximating Set-Cover. Approx-Random: 276-287, 2012.

[MOO05] E.Mossel, R.O'Donnell, and K.Oleszkiewicz: Noise stability of functions with low influences: invariance and optimality. IEEE FOCS: 21-30 (2005)

[OZ13] R.O'Donnell, and Y.Zhou: Approximability and proof complexity. To appear in ACM-SIAM SODA 2013.

[OSS11] S.Oveis Gharan, A.Saberi, and M.Singh: A randomized rounding approach to the Traveling Salesman Problem. IEEE FOCS: 550-559 (2011)

[R08] P.Raghavendra: Optimal algorithms and inapproximability results for every CSP? ACM STOC: 245-254 (2008)

[R09] P.Raghavendra: Approximating NP-hard problems: efficient algorithms and their limits. Ph.D. thesis, University of Washington, 2009.

[RS83] N.Robertson, and P.D.Seymour, Graph Minors I. J.Comb. Theory, Ser.B 35(1): 39-61 (1983), to Graph Minors XXIII. J.Comb. Theory, Ser.B 100(2): 181-205 (2010)

[S12] A.Sebo: Eight fifth approximation for TSP paths. Manuscript, 2012.

[SV12] A.Sebo, and J.Vygen: Shorter tours by nicer ears: 7/5-approximation for graphic TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. CoRR, abs/1201.1870v2 (2012)

[SA90] H.D.Sherali, and W.P.Adams, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics 3 (3):411--430 (1990)

[V01] V.V.Vazirani, Approximation Algorithms. Springer-Verlag, Berlin, (2001)

[WS10] D.P. Williamson, and D.B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, Cambridge, U.K., 2011.

[Z07] D.Zuckerman, Linear degree extractors and the inapproximability of Max Clique and Chromatic Number, Theory of Computing 3(6): 103-128 (2007)


text:
# Highlights

• Unsupervised “skill” discovery without extrinsic rewards
• Planning in “skill” space allows to generalize to unseen tasks

# Introduction

Model-based reinforcement learning (MBRL) tries to learn the dynamics of the environment as well as a policy that plans the optimal course of action using the learned dynamics. This allows the policy to be learned in more sample-efficient way as well as making able to generalize to new tasks.

However, generalizing to new state distributions remains an open problem, as exploring the full state-space and learning the full dynamics for high-dimensional systems is generally infeasible. The authors want to retain the flexibility of MBRL by using the simplicity of model-free RL to learn low-level behaviors that can be leveraged at test time.

# Methods

The authors want to learn the dynamics for a large and diverse set of skills, which allows them to use model-based planning in the skill space (or behavior space, the terms are used interchangeably) for solving new tasks.

## Unsupervised skill discovery

Using the common MDP $$M = (S, A, p, r)$$, they want to learn a skill-conditioned policy $$\pi(a \vert s,z)$$ with $$z \in \mathbb(Z)$$ that can be sampled from a prior $$p(z)$$. To plan in the skill space, the authors also propose to learn the dynamics for skills $$q_{\theta}(s'{\vert}s,z)$$, which will be used to plan at test time. The authors argue that learning the dynamics of the environment only for certain skills is much easier than learning the whole environment dynamics (aka for all possible behaviors).

To discover skills, the authors propose to maximise the mutual information (MI) between the next state $$s'$$ and the skill $$z$$ conditioned on the current state $$s$$ s.t.

Maximizing eq.2 means promoting the diversity of transitions from $$s$$ to $$s'$$ (therefore maximizing the probability of learning relevant skills), while making the transitions for a given $$z$$ predictable (thus making the process stable).

Because the actual dynamics are unknown but can be sampled, maximizing (2) is intractable, but the objective can at least be lower-bounded by

Which leads to the following gradient update for $$q_{\theta}$$

which corresponds to maximizing the likelihood of samples from $$p$$ under $$q_{\theta}$$.

To make use of the learned dynamics, the authors propose to train a policy using any model-free RL algorithm using the following instrinsic reward function

with $$L$$ the number of samples drawn from $$p(z)$$. Again, the reward function encourages the policy to produce transitions that are predictable under $$q_\theta$$ as well as diversified.

In implementation, the authors use the Soft Actor-Critic algorithm to train their policy, and their prior $$p(z) = U(-1, 1)^D$$ where $$D$$ is the dimentionality of the input space.

## Planning in action space

To make use of the low-level behaviors learned, the authors suggest planning in behavior space, instead of state-space as is usually done with MBRL. To do so, the latent space $$p(z)$$ is sampled according to the $$\mu$$s in fig. 3 and a few short trajectories are sampled using the learned prior-dependant dynamics. Presuming access to the reward function, the reward is computed for the candidate trajectories and the best one is selected. A few steps from the selected plan are executed in the environment, the $$\mu$$s are recomputed to promote behaviors corresponding to the reward function as

and the whole planning process is repeated.

# Results

## Qualitative

DADS can discover primitives for Half-Cheetah to run forward and backward with multiple different gaits, for Ant to navigate the environment using diverse locomotion primitives and for Humanoid to walk using stable locomotion primitives with diverse gaits and direction. Qualitatively, we find the skills discovered by DADS to be predictable and stable, in line with implicit constraints of the proposed objective. While the Half-Cheetah will learn to run in both backward and forward directions, DADS will disincentivize skills which make Half-Cheetah flip owing to the reduced predictability on landing. Similarly, skills discovered for Ant rarely flip over, and tend to provide stable navigation primitives in the environment. This also incentivizes the Humanoid, which is characteristically prone to collapsing and extremely unstable by design, to discover gaits which are stable for sustainable locomotion.

## Against MBRL

DADS can achieve better performance than state-of-the-art MBRL with variying degrees of directed exploration on having the Ant Mujoco model travel to a random point.

## Against hierarchical RL and model-free RL

Same goal as against MBRL.

# Conclusions

We have proposed a novel unsupervised skill learning algorithm that is amenable to model-based planning for hierarchical control on downstream tasks. We show that our skill learning method can scale to high-dimensional state-spaces, while discovering a diverse set of low-variance skills. In addition, we demonstrated that, without any training on the specified task, we can compose the learned skills to outperform competitive model-based baselines that were trained with the knowledge of the test tasks.

# Remarks

• It took me a while to figure out how planning was done until I went on the Openreview page and read that the model has access to the reward function


text:
In your hiding, you're alone. Kept your treasures with my bones.crawl somewhere bettermore quotes

# phi: fun

DNA on 10th — street art, wayfinding and font

# visualization + design

Typography geek? If you like the geometry and mathematics of these posters, you may enjoy something more letter ed. Visions of type: Type Peep Show: The Private Curves of Letters posters.

# The art of Pi ($pi$), Phi ($phi$) and $e$

This section contains various art work based on $\pi$, $\phi$ and $e$ that I created over the years. $pi$ day and $pi$ approximation day artwork is kept separate.

The accidental similarity number (ASN) is a kind of overlap between numbers. I came up with this concept after creating typographical art about the $i$-ness of $\pi$.

To construct the accidental similarity number (ASN) for three numbers $\pi$, $\phi$ and $e$, we first align these numbers and then identify positions for which the numbers have the same digit.

$π φ e$
$3.1415926535897932 … 21170679821 … 10270193852 … 1.6180339887498948 … 93911374847 … 08659593958 … 2.7182818284590452 … 51664274274 … 32862794349 …$

These digits are then used to create the accidental similarity number. In this case,

$ASN(π, φ, e) = 0.97911 48920 55221 …$

By definition, the decimal is held in place.

The posters of $asn(pi,phi,e)$ show the accidental similarity number created from the first 1,000,000 digits of each number. The numbers have the same digit at 9,997 positions.

The poster shows 9,996 ASN digits (last one is omitted) because I use the distance between the index of the digits that make up the ASN for the color mapping.

The distribution of distances follows a Poisson distribution with an average of 100, with about 1-1/$e$ values being smaller than 100.

The font is Neutraface Slab Display Medium.

## properties of the accidental similarity number

Any properties are accidental, but curiously ASN($\pi$,$\phi$,$e$) ≈ 1.

If you find other curiously accidental properties, let me know.

## data files

Download the first 9,997 digits of the accidental similarity number. This file provides the ASN digit index, $i$, the digit, $ASN_i$ and the position from which it is sampled, $\text{index}(ASN_i)$.

$i ASN_i index(ASN_i) 0 9 13 1 7 100 2 9 170 3 1 396 # e.g. 4th ASN digit is 1, sampled from digit index 396 4 1 500 5 4 596 6 8 607 7 9 694 8 2 825 9 0 828 10 5 841 11 5 941 12 2 1283 ...$
VIEW ALL

# Yearning for the Infinite — Aleph 2

Mon 18-11-2019

Discover Cantor's transfinite numbers through my music video for the Aleph 2 track of Max Cooper's Yearning for the Infinite (album page, event page).

Yearning for the Infinite, Max Cooper at the Barbican Hall, London. Track Aleph 2. Video by Martin Krzywinski. Photo by Michal Augustini. (more)

I discuss the math behind the video and the system I built to create the video.

# Hidden Markov Models

Mon 18-11-2019

Everything we see hides another thing, we always want to see what is hidden by what we see.
—Rene Magritte

A Hidden Markov Model extends a Markov chain to have hidden states. Hidden states are used to model aspects of the system that cannot be directly observed and themselves form a Markov chain and each state may emit one or more observed values.

Hidden states in HMMs do not have to have meaning—they can be used to account for measurement errors, compress multi-modal observational data, or to detect unobservable events.

Nature Methods Points of Significance column: Hidden Markov Models. (read)

In this column, we extend the cell growth model from our Markov Chain column to include two hidden states: normal and sedentary.

We show how to calculate forward probabilities that can predict the most likely path through the HMM given an observed sequence.

Grewal, J., Krzywinski, M. & Altman, N. (2019) Points of significance: Hidden Markov Models. Nature Methods 16:795–796.

Altman, N. & Krzywinski, M. (2019) Points of significance: Markov Chains. Nature Methods 16:663–664.

# Hola Mundo Cover

Sat 21-09-2019

My cover design for Hola Mundo by Hannah Fry. Published by Blackie Books.

Hola Mundo by Hannah Fry. Cover design is based on my 2013 $\pi$ day art. (read)

Curious how the design was created? Read the full details.

# Markov Chains

Tue 30-07-2019

You can look back there to explain things,
but the explanation disappears.
You'll never find it there.
Things are not explained by the past.
They're explained by what happens now.
—Alan Watts

A Markov chain is a probabilistic model that is used to model how a system changes over time as a series of transitions between states. Each transition is assigned a probability that defines the chance of the system changing from one state to another.

Nature Methods Points of Significance column: Markov Chains. (read)

Together with the states, these transitions probabilities define a stochastic model with the Markov property: transition probabilities only depend on the current state—the future is independent of the past if the present is known.

Once the transition probabilities are defined in matrix form, it is easy to predict the distribution of future states of the system. We cover concepts of aperiodicity, irreducibility, limiting and stationary distributions and absorption.

This column is the first part of a series and pairs particularly well with Alan Watts and Blond:ish.

Grewal, J., Krzywinski, M. & Altman, N. (2019) Points of significance: Markov Chains. Nature Methods 16:663–664.


text:
# American Institute of Mathematical Sciences

• Previous Article
Well-posedness for the Cauchy problem of the Klein-Gordon-Zakharov system in four and more spatial dimensions
• CPAA Home
• This Issue
• Next Article
Low regularity solutions for the (2+1)-dimensional Maxwell-Klein-Gordon equations in temporal gauge
November  2016, 15(6): 2221-2245. doi: 10.3934/cpaa.2016035

## Existence and upper semicontinuity of attractors for non-autonomous stochastic lattice systems with random coupled coefficients

 1 School of Mathematical Science, Huaiyin Normal University, Huaian 223300, China 2 Department of Mathematics, Zhejiang Normal University, Jinhua, 321004

Received  January 2016 Revised  June 2016 Published  September 2016

In this paper, we consider the existence of random attractors in a weighted space $l_\rho ^2$ for first-order non-autonomous stochastic lattice system with random coupled coefficients and multiplicative/additive white noise, and establish the upper semicontinuity of random attractors as the intensity of noise approaches zero.
Citation: Zhaojuan Wang, Shengfan Zhou. Existence and upper semicontinuity of attractors for non-autonomous stochastic lattice systems with random coupled coefficients. Communications on Pure & Applied Analysis, 2016, 15 (6) : 2221-2245. doi: 10.3934/cpaa.2016035
##### References:

show all references

##### References:
 [1] Zhaojuan Wang, Shengfan Zhou. Random attractor and random exponential attractor for stochastic non-autonomous damped cubic wave equation with linear multiplicative white noise. Discrete & Continuous Dynamical Systems, 2018, 38 (9) : 4767-4817. doi: 10.3934/dcds.2018210 [2] Zhaojuan Wang, Shengfan Zhou. Random attractor for stochastic non-autonomous damped wave equation with critical exponent. Discrete & Continuous Dynamical Systems, 2017, 37 (1) : 545-573. doi: 10.3934/dcds.2017022 [3] Shengfan Zhou, Min Zhao. Fractal dimension of random attractor for stochastic non-autonomous damped wave equation with linear multiplicative white noise. Discrete & Continuous Dynamical Systems, 2016, 36 (5) : 2887-2914. doi: 10.3934/dcds.2016.36.2887 [4] Shuang Yang, Yangrong Li. Forward controllability of a random attractor for the non-autonomous stochastic sine-Gordon equation on an unbounded domain. Evolution Equations & Control Theory, 2020, 9 (3) : 581-604. doi: 10.3934/eect.2020025 [5] Ling Xu, Jianhua Huang, Qiaozhen Ma. Random exponential attractor for stochastic non-autonomous suspension bridge equation with additive white noise. Discrete & Continuous Dynamical Systems - B, 2022  doi: 10.3934/dcdsb.2021318 [6] Xiaoyue Li, Xuerong Mao. Population dynamical behavior of non-autonomous Lotka-Volterra competitive system with random perturbation. Discrete & Continuous Dynamical Systems, 2009, 24 (2) : 523-545. doi: 10.3934/dcds.2009.24.523 [7] Bixiang Wang. Random attractors for non-autonomous stochastic wave equations with multiplicative noise. Discrete & Continuous Dynamical Systems, 2014, 34 (1) : 269-300. doi: 10.3934/dcds.2014.34.269 [8] Bixiang Wang. Multivalued non-autonomous random dynamical systems for wave equations without uniqueness. Discrete & Continuous Dynamical Systems - B, 2017, 22 (5) : 2011-2051. doi: 10.3934/dcdsb.2017119 [9] Ling Xu, Jianhua Huang, Qiaozhen Ma. Upper semicontinuity of random attractors for the stochastic non-autonomous suspension bridge equation with memory. Discrete & Continuous Dynamical Systems - B, 2019, 24 (11) : 5959-5979. doi: 10.3934/dcdsb.2019115 [10] Hong Lu, Jiangang Qi, Bixiang Wang, Mingji Zhang. Random attractors for non-autonomous fractional stochastic parabolic equations on unbounded domains. Discrete & Continuous Dynamical Systems, 2019, 39 (2) : 683-706. doi: 10.3934/dcds.2019028 [11] Abiti Adili, Bixiang Wang. Random attractors for stochastic FitzHugh-Nagumo systems driven by deterministic non-autonomous forcing. Discrete & Continuous Dynamical Systems - B, 2013, 18 (3) : 643-666. doi: 10.3934/dcdsb.2013.18.643 [12] Yangrong Li, Shuang Yang, Qiangheng Zhang. Odd random attractors for stochastic non-autonomous Kuramoto-Sivashinsky equations without dissipation. Electronic Research Archive, 2020, 28 (4) : 1529-1544. doi: 10.3934/era.2020080 [13] Dingshi Li, Xuemin Wang. Regular random attractors for non-autonomous stochastic reaction-diffusion equations on thin domains. Electronic Research Archive, 2021, 29 (2) : 1969-1990. doi: 10.3934/era.2020100 [14] Abiti Adili, Bixiang Wang. Random attractors for non-autonomous stochastic FitzHugh-Nagumo systems with multiplicative noise. Conference Publications, 2013, 2013 (special) : 1-10. doi: 10.3934/proc.2013.2013.1 [15] Zhaojuan Wang, Shengfan Zhou. Existence and upper semicontinuity of random attractors for non-autonomous stochastic strongly damped wave equation with multiplicative noise. Discrete & Continuous Dynamical Systems, 2017, 37 (5) : 2787-2812. doi: 10.3934/dcds.2017120 [16] Junyi Tu, Yuncheng You. Random attractor of stochastic Brusselator system with multiplicative noise. Discrete & Continuous Dynamical Systems, 2016, 36 (5) : 2757-2779. doi: 10.3934/dcds.2016.36.2757 [17] Xinyuan Liao, Caidi Zhao, Shengfan Zhou. Compact uniform attractors for dissipative non-autonomous lattice dynamical systems. Communications on Pure & Applied Analysis, 2007, 6 (4) : 1087-1111. doi: 10.3934/cpaa.2007.6.1087 [18] Tomás Caraballo, David Cheban. On the structure of the global attractor for non-autonomous dynamical systems with weak convergence. Communications on Pure & Applied Analysis, 2012, 11 (2) : 809-828. doi: 10.3934/cpaa.2012.11.809 [19] Alexandre N. Carvalho, José A. Langa, James C. Robinson. Non-autonomous dynamical systems. Discrete & Continuous Dynamical Systems - B, 2015, 20 (3) : 703-747. doi: 10.3934/dcdsb.2015.20.703 [20] Radosław Czaja. Pullback attractors via quasi-stability for non-autonomous lattice dynamical systems. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021276

2020 Impact Factor: 1.916

## Metrics

• HTML views (0)
• Cited by (2)

• on AIMS


text:
Metacube – Gigacube

In communication, the term means to the plication in 3D of an informative 2D surface in order to obtain a compact disposition of information in digital devices. Some authors[1] refer to this plication as the reiterated interlacement or multi- interlacement of an informative surface. An informative surface is the result of exposing the required information in an only one visual plane. The transit for the exposed information respects an orthogonal direction. That informative surface is defined in base on the informative unit of surface ${\displaystyle a_{ij}}$ ( normally square ) whose amount of information is defined ad hoc.

Presentation of the information

Metacube arises from the need to communicate and store the information in devices of increasingly smaller screen. This fact has influenced in other basic parameter, the portability. We can view the information where and when we desire. This fact, is being transcendental in time to design the presentation of the information, because it obligates to iconography and to group a lot more (simple symbols or complexer combinatorials), this is, impels to synthesize concepts to expose them in a relatively small screen. Also, has been important the “touching” incorporation as interaction element “user-interface” because it establishes simpler protocols and obligates to synthesize the distribution of the information. Some investigators usually define the 2.0 era (and its devices) precisely for what the new design of the information involves in reduced screen. The 2.0 refers to the size, the portability and today, refers to the possibility to manage the transfer of information without physical anchors to networks through 3G devices of reduced dimensions.

The “presentation of the information” (screen interface) must accomplish three basic requirements adjusted in three parameters:

• FORM: the aspect of the base in which is presented the information must be compact and codable ( density and comprehension of the screen information).
• SIZE: the proposed route is initially infinite ( the infinite amount of information is limited only by the memory).
• USABILITY: the ways and possible directions to transit through, must be easily and intuitively understood (the “touching” that finally is proposed to respond to that aim, must count with intelligible and codable protocols ).

A (rentable) solution at the proposed challenge for the combination of these three parameters was developed by Josep A. Esteve in 2011 with a configuration of interface, that was called Metacube.[2] The extensive Metacube theory is being developed in the CETEC where is tried to create a theory framework for an information model of synthesis applied to the interfaces of 2.0 devices .

The construct plot in which is based the Metacube concept, is exposed in the sections below:

Informative surface

We start from a determined amount of information. We can express this amount in number of “information screens”.

All screen information is shown as a 2D surface where each cell (view Image 1) is an “information unit” (text, image, sound,...). This cell is represented by ${\displaystyle a_{ij}}$, in mode of the element of a matrix, where ${\displaystyle i,j}$∈ℤ+ (are entire positive numbers) and to the set (all the information surface) is denoted by ${\displaystyle \{a_{ij}\}}$. An informative surface is an infinite set of units-cells of information.

Image 1.

This surface can be as big as you desire. In practical effects the storing of the information only depends on the memory of the involved device .

We define the concept “informative surface operator”[3] to all made action on the information surface, or in one of its cells in order to generate a change in the information presentation. This change can be structural, apparent, virtual, etc...

Is defined the operator k that corresponds to the “cell jump[4] concept. This action is the pass of one cell to one of the for cell-borderline below, as is indicated in the image 2.

Image 2.

We have a set of elements with an operator, this is ${\displaystyle (\{a_{ij}\},k)}$.

Metacube

Assuming the 2.0 needs explicited before, to which were necessary to respond with solving, is proceeded to “fold” the structure “informative surface” that has been defined and we transformer it in a 3D element, this is, a cube. This cube, is what we have called Metacube, because it has infinite faces ( or the amount that are desired to define). In terms of a mentally supposed tridimensional representation in the cognitive process of the user, Metacube does not let of representing itself as a polyhedron of six appereant faces, because it maintains the formally of a one traditional cube.

Every frontal face, which is shown in the screen interface, is one of the cells ${\displaystyle \{a_{ij}\}}$ of the informative surface ${\displaystyle (\{a_{ij}\},k)}$ and every “face jump” pass to be a “rotation” of central axis ( vertical or horizontal ) showing the informative content anterior or posterior of the cube face of infinite faces, as is shown in the images 3 and 4.

Image 3. Cell jump (2D)
Image 4. Face rotation of Metacube (3D)

The structure ${\displaystyle (\{a_{ij}\},k)}$ is denominated METACUBE.

It is obvious that Metacube allows to store the amount of information that we desire (each face shows the information that we have put in the Metacube), to select with the “touching” the information that we want (search).

Gigacube

In order to increase the organizational capacity and therefore magnificate the Metacube structure, is defined the concept called GIGACUBE. A Gigacube is a Metacube of Metacubes. It is the association of a Metacube to each face of a Metacube, multiplying exponentially the organizational capacity of the Gigacube structure. In fact, the growing is logarithmic and can be regulated at will. It could be said that all the information of the universe, could be presented to the user through a Gigacube interface.

Is denominated Metacube of Base or Metacube of level 1, the first Metacube that we find in the interface.

Metacubes associated to the faces of the Metacube of level 1, are denominated Metacubes of level 2 and so on.

The capacity of one Gigacube, depends on the magnitude (number of faces of the Metacubes of superior levels) associated to the faces of the metacube of level 1 and successively the metacubes of distinc level that are associated.

To active the Metacube associated to the face of one Metacube of base ( or inferior) we use the operator D that realize the action that we know as “Double Click” .Is understood that the double clic actives the emergent metacube.

The structure ${\displaystyle (\{a_{ij}\},k,D)}$ is denominated GIGACUBE.

Gigacube form in the screen interface of a digital device is shown in the image 5.

Image 5. Left,Metacube Appearance. Right, Gigacubo Appearance

The Gigacube structure ${\displaystyle (\{a_{ij}\},k,D)}$ complies the three requirements for the correct “presentation of the information” in the reduced interface. It remains to establish the “ compare information” protocol.

To compare information (units) must be exposed some Metacube faces at the same time in the screen interface. For this, is defined the operator ${\displaystyle {\overrightarrow {T}}}$ that acts as “timer-touching” on the interface of Metacube. This operator corresponds to the action for which the user, keeping the “touch” during a period of time larger than normally, actives the Metacube as screen element and he can drag it around this, until place it where he desire. By this way, different Metacubes can be placed in a same interface of a same Gigacube or not ( different origin). The vectorial notation of this operator refers to its displacement capacity of the information element Metacube.

The structure ${\displaystyle (\{a_{ij}\},k,D,{\overrightarrow {T}})}$ complies the three basic requirements and, therefore, is constituted in the base of the architecture of the Gigacube concept.

This theory has been brought to practice successfully by different companies such as Tons of Toons, Esteve Animació and AppStar in the development of different App Games and App Utilities, including Zong-Ji, Pellex, Suma and Sudoku using chromenumerical Metacubes; or the PuzzKids that use iconical and chromealphabetical Metacubes.

The Gigacube structure is being used in the design of new sport informative applications.

References

1. ^ 1. Dr. J Mª Blanco in the conference “ Compactation of the Information in Metacube”. Speech of CETEC foundation. Center of Theorical Studies of the Communication. Empuriabrava, Girona, November 11th of 2011.
2. ^ 2. In works such as Nguyen, Tjoa and Wagner has been presented a Metacube Concept as the tridimensional disposition of the information (Nguyen, Tjoa y Wagner (2000) “ Conceptual Multidimensional Data Model Based on Metacube” of Nguyen, Tjoa and Wagner (T. Yakno (Ed): ADVIS 2000, LNCS, p 24-33, 2000). This approach only explains the spatial disposition of the information, transposes 2D graphic trees in a accumulate cubic in 3D, but it does not stablish the protocols of searching and comparation of the same. It is a preterit theoerical form of talking about 3D disposition of the information, for the advances in 3D infography. In the Metacube (Esteve) the information is compacted, establishing clear protocols of searching and comparation of the stored information.
3. ^ 3. The “operator” concept is generalized for any realizable action on the information and the communication of the information.
4. ^ 4. The cell jump, that more ahead we will denote it as “Face rotation [or facet]” allows the calculation of “ Informative trajectories” and the definition of “Courses of information” and how to calculate its reversibility (Thermodynamics of the information).


text:
Rate of Change as moving toward a point

• March 4th 2008, 03:43 PM
crwhd4
Rate of Change as moving toward a point
Find the rate of change of f(x,y,z) = ln(x+yz^2)-sin(y+z)+xe^y at the point (0,1,-1) as you move toward the point (4,1,2)
• March 4th 2008, 04:43 PM
Jhevon
Quote:

Originally Posted by crwhd4
Find the rate of change of f(x,y,z) = ln(x+yz^2)-sin(y+z)+xe^y at the point (0,1,-1) as you move toward the point (4,1,2)

you want the directional derivative here.

first, find the vector from (0,1,-1) to (4,1,2).

then find the unit vector in that direction

then use the formula: $D_u f = \nabla f \cdot u$

where $\nabla f$ is the gradient vector of $f$ (at the point (0,1,-1)), $\cdot$ is the dot product and $u$ is the unit vector i asked you to find.


text:
Arithmetic Mean

Suppose the principal of your school asks your class teacher that how was the score of your class this time? What do you think is the teacher going to do? Do you think that the teacher is going to actually read out the individual score of all the students? NO!!! What the teacher does is, the teacher will tell the average score of the class instead of saying the individual score. So the principal gets an idea regarding the performance of the students. So let us now study the topic arithmetic mean in detail.

Arithmetic Mean

In general language arithmetic mean is same as the average of data. It is the representative value of the group of data.  Suppose we are given ‘ n ‘ number of data and we need to compute the arithmetic mean, all that we need to do is just sum up all the numbers and divide it by the total numbers.

Browse more Topics under Data Handling

Let us understand this with an example:

There are two sisters, with different heights. The height of the younger sister is 128 cm and height of the elder sister us 150cm. So what if you want to know the average height of the two sisters? What if you are asked to find out the mean of the heights?  As their total height is divided into two equal parts,

$$\frac{128 + 150}{2}$$ = $$\frac{278}{2}$$ = 139 cm

So 139 cm is the average height of the sisters. Here 150 > 139 >  128. Also, the average value also lies in between the minimum value and the maximum value.

Formula for Arithmetic Mean

Mean = $$\frac{Sum of all observations}{number of observations}$$

Thus, the mean of n observation x1, x2, . . ., xn, is given by

$$\overline{x}$$  = $$\frac{x_1 + x_2 +….+ x_n}{n}$$  = $$\sum_{i=1}^{n}$$ xi

Where the symbol ∑ called sigma which stands for summation. Suppose you want to find the mean score of all the tests you gave in this month.

 Marks Frequency 2 2 5 3 7 4 8 2 9 3 10 3

To find the sum of all the scores, you have to multiply the frequency of each score, with the marks obtained.

Mean = $$\frac{Sum of all observations}{number of observations}$$

So here we get another formula,

$$\overline{x} = \frac{∑ f_x}{∑ f}$$

Now that data may be in several forms. One such type is raw data. Do you know what is Raw Data? To understand the concept of raw data, let me explain this with an example.

Suppose you are dealing with the scores of the particular cricketer over hundred matches, So for the first match, he scores xruns, for the second match he scores xruns and so on up to x100 for the hundred matches.

So this is what we call as raw data. That means we are not grouping any data but presenting it as it is. So when such kind of data is presented to you and you are supposed to find out the mean, we use the formula, according to the above data,

Mean = $$\sum_{i=1}^{100}$$ xi  /100

This is when n is 100. In general,

Mean of  $$\overline{x} = \sum_{i=1}^{n}$$ x/n

This the formula for the arithmetic mean of the raw data.

Solved Examples for You

Question: The runs scored by Sachin in 5 test matches are 140, 153, 148, 150 and 154 respectively. Find the mean.

1. 150
2. 149
3. 147
4. 148

Solution: The correct option is B. Runs scored by Sachin in 5 test matches: 140, 153, 148, and 154

Means of the runs =  $$\frac{total runs}{number of matches}$$

Mean =  $$\frac{140+153+148 + 150+154}{5}$$ = $$\frac{745}{5}$$ = 149

Question: Mean of a set of observations is the value which

1. Occurs most frequently
2. Divides observation into two equal parts
3. is a representative of the whole number.
4. is the sum of observations

Solution: The correct option is C. Mean is the value which is the representative of the whole number. It takes into account of all the values present in the group and averages them.

Question 3: What are the type of mean?

Answer: In central tendency mean is the most common measure that we use. Moreover, there are different type of mean such as arithmetic mean, weighted mean, geometric mean, and harmonic mean. Also, if we mention it without an adjective (as mean) then, it generally refers to the arithmetic mean.

Question 4: Define geometric mean?

Answer: Geometric mean refers to the average that indicates the central tendency or typical value of a set of numbers by using the product of their values as opposed to the arithmetic mean that we also know as mean.

Question 5: Why we use the arithmetic mean?

Answer: Arithmetic mean allows us to categorize the centre of the frequency distribution of a quantitative variable by considering all of the observation with the same weight afforded to each (in contrast to the weighted arithmetic mean).

Question 6: How do you solve arithmetic mean?

• First, add up all the numbers.
• Next, divide the total by how many there are, solving Maths problems: Finding the mean.
• After that, you can find the mean by adding pieces of data together and dividing by the number of pieces of data.

Share with friends

Customize your course in 30 seconds

Which class are you in?
5th
6th
7th
8th
9th
10th
11th
12th
Get ready for all-new Live Classes!
Now learn Live with India's best teachers. Join courses with the best schedule and enjoy fun and interactive classes.
Ashhar Firdausi
IIT Roorkee
Biology
Dr. Nazma Shaik
VTU
Chemistry
Gaurav Tiwari
APJAKTU
Physics
Get Started

Subscribe
Notify of


text:
Estás viendo el contenido archivado del viejo foro de Ojodigital. No podrás iniciar sesión ni crear nuevo contenido o comentarios. El foro de ojodigital ha migrado a: https://foro.ojodigital.com, con un aspecto mucho más moderno, amigable y adaptado a dispositivos móviles.
Tab Content
No Recent Activity
Acerca de v3ave273

#### Información básica

Fecha de nacimiento
enero 18, 1988 (32)
##### Acerca de v3ave273
Equipo fotográfico:
Sony Cyber-shot DSC-RX10
Biografía:
serwis wózków widłowych Learn to get Boundless Indemnity Garage sale Is in the lead (3 Actions) FRANKFURT Infineon brushed away matter to facilitate it turned out fritter excessive to acquire U.S.-based Global Rectifier, claim the arrangement possibilities a success involving do good to to the A language like german chipmaker. As soon as mark optimistic the classified ad near upright support just before no cost classified want ad, make sure you impart the communication talk to, number after that website web page link returning to ones indemnity website along with the idea in actual fact crucial that you assent to nations live through they might get added emancipated in turn once they communication a person with riposting on the flyer along with post the make contact with in sequence. Instead of saying to live in reality, propaganda repeatedly aspires by operation involving concepts near effect the activities of your large numbers of nations. By Peroxide in order to Value Geass, they am alive the whole another modish storyline, images with intrigue. Cetus Corporation's creates GeneAmp polymerase shackle retort (PCR) skill, that could engender huge amounts of carbon copy of any affected genetic material arrangement in vogue individual hr. The human being genome shoot is placed positive, a relationship in between scientists beginning peoples around the globe to function absent the full in the soul genetic secret language. ENGENDER takes on the road to further interconnection, belongingness, abilities as a consequence moot accomplishment with the first-generation students regarding San Jose Mess Academe. The Shenzhen-based corporation what's more shouted that looked forward to to come up with the maneuvering perimeter connected with 18.3 pct from the foremost half a year connected with 2014. The pastry-cook cause lwrp subcommand is needed to come up with a unimportant reserve then donor within the /learning resource in addition to /companies service. Just by pleasure, I am real attempting to find a superb reasoning to build a accidental variety in between 1 next 10 (uniformly) having an unbiased six-sided pack in. If $1\leq n\leq 3$ the range are going to be relating $1$ as well as $5$ in case $4\leq n\leq 6$ your own figure is going to be relating $6$ next $10$. In their normal direction a person breed a the same dispersal over $1,10$ with $\frac115=\colorred2.2$ throwins, featuring in ordinary. Right after describes on the earlier entry here Sept, RSA needed it's clients to avoid taking advantage of the Twin Elliptic Curve quantity turbine. This may spawn a vibrant obstruct grid you are able to regulate via selecting that data to look through which lay off. Taking into account working on the Enhance Research static opening for the set down furnish feature on the road to identify which usually tags can get diagramed just click the Seek out push button to get products.
País:
ESPAÑA
Localización:

#### Contacto

##### Total de mensajes
Total de mensajes
0
Mensajes por día
0