Truebit is a recent proposal for building smart contracts on top of Ethereum. Truebit allows outsourcing complex computations to untrusted parties, verifying that the computation was done correctly, and paying them for their work. The enforcement and incentives are implemented as a set of Ethereum smart contracts. This is an improvement over current Ethereum, as currently the gas limit means that Ethereum smart contracts can only perform a limited amount of computation.
There are various proposals for sharding, which allow the Ethereum blockchain to scale to a larger number of transactions. They might plausibly allow for increasing the gas limit. So, they could be viewed as an alternative to Truebit.
What advantages and disadvantages does Truebit have over sharding, as a way of allowing smart contracts to perform more computation?