- Видео 58
- Просмотров 170 936
Computational Thinking
Швейцария
Добавлен 14 сен 2022
Computation is everywhere, but what is computation actually? In this video series we will discuss the power and limitations of computation. Computational thinking is about understanding machine intelligence: What is computable, and how efficiently?
Understanding computation lies at the heart of many exciting scientific and social developments. Computational thinking is more than programming a computer -- rather it is thinking in abstractions. Consequently, computational thinking has become a fundamental skill for everyone, not just computer scientists.
This channel explores some of the fundamental computational topics: Algorithms, Complexity, Cryptography, Databases, Machine Learning, Neural Networks, and Computability.
Understanding computation lies at the heart of many exciting scientific and social developments. Computational thinking is more than programming a computer -- rather it is thinking in abstractions. Consequently, computational thinking has become a fundamental skill for everyone, not just computer scientists.
This channel explores some of the fundamental computational topics: Algorithms, Complexity, Cryptography, Databases, Machine Learning, Neural Networks, and Computability.
Second Price Auction & Mechanism Design
In this video, we present three classic types of auctions: First the sealed-bid auction, then the English auction, and finally the second price auction, which is a hybrid of the other two. Then we quickly show that the second price auction is a truthful mechanism.
Просмотров: 477
Видео
Selfish Caching and The Price of Anarchy
Просмотров 937Год назад
In this video, we study game theory in the context of distributed systems. Our main example is selfish caching. We discuss some core concepts in game theory, like the Nash equilibrium, the social optimum, the price of anarchy, and the optimistic price of anarchy. We also present a simple greedy algorithm to compute a Nash equilibrium for selfish caching.
Advanced Topics in Python: Types, Objects, Parameters, Scope and Copying
Просмотров 431Год назад
The video is describes the more advanced concepts (the second page) of this Python Cheat Sheet: disco.ethz.ch/courses/coti/lecturenotes/pythoncheatsheet.pdf In this video, we learn about five slightly more elaborate concepts in Python that are often necessary, namely additional types, object oriented programming, function parameters, variable scope, and different copying versions.
Learning the Python Programming Language in 8 Minutes
Просмотров 962Год назад
The video is based on the single-page Python Cheat Sheet: disco.ethz.ch/courses/coti/lecturenotes/pythoncheatsheet.pdf This video teaches all the basic principles of the Python programming language in just 8 minutes. In particular, the video describes how Python does Math, operates on Strings, Lists, Sets, and Dictionaries. Then the video discusses Conditional statements such as if-statements, ...
Computability Summary
Просмотров 725Год назад
This video presents a summary of all videos on Computability. It shows how the videos are related. This summary video is best watched after watching the individual videos.
The Post Correspondence Problem (PCP)
Просмотров 2,3 тыс.Год назад
In this video, we discuss another Turing complete computation model which is based on dominoes. It is known as the Post Correspondence Problem, or PCP for short. PCP is interesting because we can study several PCP variants. Some of these variants are powerful enough to include undecidable problems, others are NP-complete, and others can be solved efficiently with a simple algorithm. So PCP nice...
The Turing Machine
Просмотров 835Год назад
In this video, we discuss a formal model for computation: The Turing machine. The Turing machine combines a finite automaton (the computer program) with an infinite tape (the memory). In principle, the Turing machine is computationally powerful, it can anything that can be computed with the best available hardware and software. At the same time, the Turing machine is simple, and easy to complet...
The Halting Problem
Просмотров 791Год назад
In this video, we study a classic problem introduced by Alan Turing, the so-called halting problem. In the halting problem, our input is the source code of any computer program, and we want to know whether this computer program eventually terminates. We show that in general the halting problem is not solvable, not even if we have unlimited time and resources. The halting problem is an example o...
The Universal Approximation Theorem of Neural Networks
Просмотров 7 тыс.Год назад
This video explains and discusses the universal approximation theorem.
Dictionaries and Binary Search Trees
Просмотров 2,4 тыс.Год назад
Dictionaries and Binary Search Trees
Sehr gut
Lovely visualizations
thank you sir
Thank you, intelligent persons, for sharing this for free!!!
Amazing video! i'll try to implement this in c#
Why the table columns are the values, not the volume?
Really clear explanation. Thanks for the video!
Thanks for this, it’s enough to get me started in zk
can you share the code?
I love the graphics. The artificial voice is distracting however.
The AI voice is very difficult to listen after the first few minutes.
Gemini 1.5 Pro: This video is about the Bin Packing Problem and how to solve it with an approximation algorithm. The video starts with a scenario where you are running a drone transportation company. The drone has a carrying capacity of one kilogram, and you want to pack the items into boxes as tightly as possible to save on the number of journeys. The items include an apple weighing 500 grams, an orange weighing 300 grams, 400 grams of strawberries, and 700 grams of grapes. The video then introduces a simple algorithm called First Fit. This algorithm considers the items in whatever order and places them into bins one by one. The goal is to place each item in the leftmost bin that it fits into. For example, with the items listed above, the first item would go into the first bin, the second item would not fit into the first bin so it goes into the second bin, and so on. This algorithm uses five bins in total. The video then analyses the First Fit algorithm and proves that it is a two approximation algorithm for bin packing. This means that the algorithm uses at most two times as many bins as the optimal solution. The video also discusses an improvement to the First Fit algorithm by sorting the elements in decreasing order. This improvement can achieve an approximation ratio of three over two. The video concludes by proving that it is NP-hard to approximate bin packing to any constant less than 1.5. This means that there is no polynomial time algorithm that can guarantee an approximation ratio better than 1.5. The video also mentions that First Fit with sorting is a 1.5-approximation algorithm.
Thanks for the good work!
Great explanation ❤❤❤…Thank u so much👌👌
Great video
You forgot to mention that the idea with the test program is we want the test program to output the opposite result of the halting program. Hence where you got the inner body of the program named 'test'. This is a key component you forgot to mention.
1st
what the fuck this is so good
I have been banging my head trying to understand the theory, but you made it very simple.! <3
thank you. well explained.
Incredibly high quality video, thank you very much!
the first example might be wrong. The number of letter different between top and down. How can rows be same?
AI
Best video on the subject with an additional proof of reduction, amazing help in the NP-Completeness world !!! Thanks a lot
There is no proof here. It’s zero proof.
Brilliant! I have absolutely no idea what's going on.
Very detailed video
thanks
Looks like series to me.
Alice and Bob will be together forever.
the best explanation ever, thanks man
idk what i'm doing here, i was just trying to learn how to draw a maze
welcome to algorithm analysis and complexity classes
You can’t find the most efficient path
This was a great explanation! Covered nearly everything I learnt in my class. The confusion matrix is, well, confusing but also quite logical.
Very clear and thorough explanation in such a short time, complete with application examples. More mechanism design videos please!
It is extending our brain. But we need more. Please make video which explains just algorithm then let us write code. Thanks.
Really cool video, I am writing a scientific work about cryptography and this video was extremely usefull
Thank you! waiting for a 3D Bin Packing video :)
very good video, you talk slowly that it is possible to understand, thanks!
Thank you for the beautiful explanation
great video
Waldo is behind the train in the bottom right corner
Damn this channel is so so good, I wonder why youtube does not recomend it for me
Good work, I really like your videos!
Wouldn’t the where’s waldo proof convince a third party?
If the 3rd party had access to all the information you do, they'd just be a perfect copy of 2nd party I think, as far as this theory is concerned
Having the same prior knowledge and going through the same interactions between themselves and the person who's trying to prove their knowledge
Also you can't pretend you have the knowledge to a 3rd party because you don't know how the sheet below the black overlay was moved, so you can use this method to pretend you know something you don't, which in this case is a proof of work that you've look at different places on the board until you've found Waldo
So, the basic idea of a zero-knowledge proof is to show that you have information not by revealing the information, but by showing that you know things that would be difficult or impossible to know without having that information?
Yes, this is correct.
@@discoETHand also the person you've proven your knowledge to cannot exploit that proof to pretend they know the same information to someone else
@@ikcikor3670 This is a good way to put it.
@@discoETH Hmmm. But you may not even HAVE the information right? An example: A KYC check. You might use a service to do a KYC check, at the end of which the service returns you a hash of the outcome/result - You store the hash. That hash alone can serve as a zero-knowledge proof that you have validated the customer via KYC even though you have no details of the information itself (of course I'm omitting some steps here but the high-level approach holds). You may then present this hash to regulatory authorities as proof that you indeed did perform a KYC check without storing any details of the KYC process/customer.
Did not help. Sorry
5:12. If C* is the optimal solution. How come we say C*>=C? Why would the optimal solution be larger or equal to the approx solution? Shouldn't it be the other way around?
the statement c* >= c is correct in this context. Since the blue edges (c=3) are sufficiently apart in the example, we need at least 3 (c*) nodes to cover these edges. This is generally true. If some c edges do not share any node, c* is at least as large as c.
at 5:00, you said that the key space is 6 to the power of 26. is that right or its supposed to be 26 to the power 6?
Ouch, you are of course correct, for some reason we mixed up the numbers there. Apologies.
simple question.😏😏😏
That AI voice doesn't go well we these long math expressions, especially when they're just thrown out there without much elaboration.