Algorytm gąsienicy – zadanie Bierki

Omówienie zadania Bierki które wymaga algorytmu gąsienicy:
https://youtu.be/MJCkuBDezSE?t=976
Zadanie Bierki pochodzi z II etapu poprzednika Olimpiady Informatycznej Juniorów:
https://youtu.be/MJCkuBDezSE?t=895
Algorytm gąsienicy omówiony na podstawie zadania Bierki:
https://youtu.be/MJCkuBDezSE?t=2345
Złożoność algorytmu gąsienicy:
https://youtu.be/MJCkuBDezSE?t=3188

Strona z rozwiązaniem zadania Bierki – kod C++ który otrzymuje 100%:

Link do zadania Bierki:
https://szkopul.edu.pl/problemset/problem/KiEvCpZBaUNRCp6oTZx2oAQ4/site/
Link do wszystkich zadań II etapu OIG z którego pochodzi zadanie Bierki:
https://szkopul.edu.pl/portal/problemset/oig/1

————–
Grafy

Co to jest graf? Po co nam grafy?
https://youtu.be/UOei4vez6LM?t=118
Grafy – co to jest?
https://youtu.be/OA8BeVFvaNU?t=1006

Czy Europa i Wielka Brytania są spójne?
https://youtu.be/OA8BeVFvaNU?t=1260
oraz
https://youtu.be/OA8BeVFvaNU?t=1386

Co to jest cykl? Czy drzewo ma cykl?
https://youtu.be/OA8BeVFvaNU?t=1329

–
Graf w C++ – jak trzymamy graf w komputerze:
https://youtu.be/UOei4vez6LM?t=4090
–
Do trzymania grafu wykorzystujemy wektor:
https://youtu.be/UOei4vez6LM?t=6053
a tak naprawdę tablicę wektorów:
https://youtu.be/UOei4vez6LM?t=6100
–
Jak trzymamy graf w pamięci?
https://youtu.be/OA8BeVFvaNU?t=2479

–
Kiedy zaczęła się nauka o grafach? (Quiz)
Od analizy problemów w Królewcu przez Eulera
https://youtu.be/iDPLi4XQN2w?t=376

Co to jest graf?
https://youtu.be/iDPLi4XQN2w?t=738
Przykład osób w klasie połączonych relacją czy ktoś kogoś lubi czy nie?
Po co nam grafy?
https://youtu.be/iDPLi4XQN2w?t=830
– kto mnie może poznać z inną osobą?
– komu powiedzieć informacje by szybko się rozniosła?
– jak szybko się rozniesie?
– ile osób zna się w danej społeczności – na przykład zainteresowanej kupnem samochodu
– ile osób dzieli dwie inne by przekazać wiadomość
– na świecie jest 7 miliardów ludzi, różne preferencje -> grafy są gigantyczne
– a google w ciągu 1/10 sekundy musi nam pokazać strony spośród miliardów stron – zanalizował gigantyczny graf
– podobnie facebook – pokazuje nam strony – analizuje graf
– gwiazdka – podpowiedzi prezentów biorą się z analizy grafu!

Grafy to jest dziedzina która potrzebuje nowych pomysłów – nas!
https://youtu.be/iDPLi4XQN2w?t=1197
– to my wymyślimy lepsze algorytmu które lepiej pokażą strony, podpowiedzi prezentów, …
– wszystko można przedstawić jako graf
– jeśli umiemy posługiwać się grafami – jesteśmy pożądani, magikami
– zamiast miliona lat, program wykona się w sekundę
– każda sekunda poświęcona na grafy, to najlepiej spędzony czas
– mamy moc by te rozwiązać najtrudniejsze problemy!
– fascynują przygoda przed nami

Przykład, że grafem można zobrazować wszystko.
Budowa domu – harmonogram działań
https://youtu.be/iDPLi4XQN2w?t=1346
Dom jest prosty, ale bez gafu nie zrobimy:
– kompleks fabryk, osiedle, rakieta kosmiczna, rozkład zadań w fabryce

Samochód – produkcja – harmonogram zadań
https://youtu.be/iDPLi4XQN2w?t=1426
– fabryka dostaje plan na następny tydzień bo tydzień czasu jest graf analizowany
– znając grafy, możemy to poprawić, zwiększyć zyski fabryki

Klasyczne problemy grafu:
https://youtu.be/iDPLi4XQN2w?t=1522
– najkrótsza droga
– problem chińskiego listonosza – obejść wszystkie domy i wrócić do bazy

Przykład z ciężarówkami – redukujemy koszty o 10% – skracając drogę ciężarówek – gigantyczny zysk dla nas i dla firmy!
https://youtu.be/iDPLi4XQN2w?t=1546

Jesteśmy w stanie pomóc jeśli znamy algorytmikę!
https://youtu.be/iDPLi4XQN2w?t=1772
– jeśli umiemy przedstawić problem jako graf to przyspieszymy jego rozwiązanie!
– i wielki FUN!

===============
DFS – Depth First Search
Algorytm który chodzi po grafie “W głąb”
–
Chodzimy po grafie – Co to jest DFS?
https://youtu.be/UOei4vez6LM?t=884

Jak chodzić po grafie / drzewie:
https://youtu.be/OA8BeVFvaNU?t=3933

Algorytm DFS:
https://youtu.be/OA8BeVFvaNU?t=4025

DFS – implementacja i wyjaśnienie:
https://youtu.be/UOei4vez6LM?t=5326

Implementacja DFS:
https://youtu.be/OA8BeVFvaNU?t=5623

PreOrder i PostOrder:
https://youtu.be/-6XSy1IUlgg?t=1998

===============
C++ – pierwszy program

Jak wypisujemy tekst w języku C++?
Czym kończy się każde polecenie w C++?
https://youtu.be/zN3CApegsSY?t=2388

ZADANIE SERCE – pierwszy program wypisujący piękne serce na ekranie
Początek omówienia zadania Serce:
https://youtu.be/zN3CApegsSY?t=1682
Omówienie, kod link do zadania Serce:
https://oki.org.pl/serce/

Piszemy pierwszy program w języku C++
Rysowanie choinki z kodów ASCII
https://youtu.be/xF5wlR-xX8g?t=2072
Link do kodu, omówienia zadania:
https://oki.org.pl/choinka/

Zadanie czekoladki dało nam nową wiedzę w C++
Wczytywanie danych w C++:
https://youtu.be/CMasYTVhIjQ?t=1393
–
Zmienne w programowaniu / C++ czyli szufladki w których komputer przechowuje nam wartości
https://youtu.be/CMasYTVhIjQ?t=1422
W naszym kodzie były to liczby całkowite typu int o wielkości -2 147 483 648 do 2 147 483 647
–
Komentarz w C++ czyli coś co C++ zupełnie nie interesuje:
https://youtu.be/CMasYTVhIjQ?t=1608
–
Wczytywanie z klawiatury i przechowywanie w zmiennych:
https://youtu.be/CMasYTVhIjQ?t=1796
–
Jak nazywać zmienne?
Piszmy kod, byśmy zawsze wiedzieli co on robi:
https://youtu.be/CMasYTVhIjQ?t=2212
–
Wykonujemy działania arytmetyczne w C++:
https://youtu.be/CMasYTVhIjQ?t=2271
–
Wszystkie zmienne deklarujemy w C++:
https://youtu.be/CMasYTVhIjQ?t=2397
–
Deklarujmy zmienne na początku:
https://youtu.be/CMasYTVhIjQ?t=2488

===============
Tworzymy CV na podstawie rozwiązanego zadania
Tworzymy CV na podstawie rozwiązanego zadania USACO – Amerykańska Olimpiada Informatyczna.
W przyszłości (staż, projekt, uczelnia) pokazujemy moc, pracowitość, pomysłowość!!!
Nawet na imprezie!
https://youtu.be/UOei4vez6LM?t=7251

CV pomaga nam w zdobyciu dobrej szkoły, stażu – tak jak pan Krzysztof Maziarz z Microsoft który był naszym gościem:
https://youtu.be/yYn4AOQU4S4?t=8114

Pokazanie jak tworzymy CV – dla video, postów, maili:
https://youtu.be/AcWCajYtYoI?t=5458

CV uczestniczki OKI:
https://youtu.be/34qu4l2B5dI?t=4780

=================
Przygoda / Olimpiada

Programujemy, rozwiązujemy problemy.
Dziś motywuje nas Olimpiada. W przyszłości znajdziemy lek na raka, przyjazny plastik, sygnał dalekiej cywilizacji
https://youtu.be/zN3CApegsSY?t=32

Olimpiada motywuje nas do nauki programowania i algorytmiki.
By w przyszłości pisać programy i znaleźć lek na raka:
https://youtu.be/zN3CApegsSY?t=32

Olimpiada prowadzi nas do pięknej przygody by zmieniać, negować, wymyślać.
Jesteśmy odkrywcami, tymi którzy negują, tymi którzy w przyszłości mają wymyślać w Google’u, start-upach, na uczelniach:
https://youtu.be/2RV8_naxzHE

Przez programowanie, Olimpiadę do pięknej przygody!
https://youtu.be/xF5wlR-xX8g?t=953

Dlaczego Olimpiada?
Chodzi o rozwiązanie problemów świata
Oki #1 2019/2020
https://youtu.be/xF5wlR-xX8g?t=953

Ilość operacji. Szczegółowe wyjaśnienie:
https://youtu.be/LryJ-4lrXts?t=8663

Komputer kwantowy nie rozwiąże problemów.
Problemy są o złożoności 2^n
Musimy czekać miliony lat na rozwiązanie tych problemów.
Dlatego świat potrzebuje Ciebie – Twoich pomysłów, by komputer zdążył policzyć.
Świat czeka być dużo nauczył się w Olimpiadzie!!!
https://youtu.be/MJCkuBDezSE?t=120

Sztuczna inteligencja jest potrzebna bo komputery są wolne – startup który zarobił 2.1 mld.
Dlatego startujemy w Olimpiadzie – negujemy, wymyślamy.
https://youtu.be/Je9Bfy6lu3Y?t=237

=================
Quizy, samodzielne poszukiwania nas rozwijają

Był tez quiz który dał wielka radość
Quiz z rysowanie znaków ASCII:
https://youtu.be/CMasYTVhIjQ?t=4050

Ale też eksperymentowaliśmy!
https://youtu.be/CMasYTVhIjQ?t=2867
I zmusiliśmy komputer do błędu:
https://youtu.be/CMasYTVhIjQ?t=3328
2147483647 + 1 dało liczbę ujemną!
A dlaczego?
Bo każde pudełko kiedyś pęka!

Jeśli czegoś nie rozumiemy – to normalne!
Zawsze można wrócić do treści!
Ale trochę czasu – i będziemy śmigać
https://youtu.be/CMasYTVhIjQ?t=4658

Zadanie przed zajęciami są jawne.
Myśląc nad zadaniem więcej korzystamy z zajęć!
https://youtu.be/OC_xrHSMYlA?t=4190

Robiąc research jesteśmy naukowcami, poszukiwaczami, odkrywcami nowych lądów!
https://youtu.be/eCSjwO9wu0I?t=10111

Być odkrywcą! Wszystko się zaczyna od pytania dlaczego? Jest wiele do odkrycia!
https://youtu.be/Q3j6LNU_LRM?t=937

Zawsze zadajemy pytanie dlaczego, kiedy? Wówczas jesteśmy odkrywcami, tymi którzy wymyślą nową rzecz, założą start-up. Historia DD
https://youtu.be/Q3j6LNU_LRM?t=415

Nie ma znaczenia czy umiem programować, czy nie – czy znam algorytmikę czy nie – wystarczy poświęcić się pasji, wystarczy trud, wystarczy liczyć zadania – historia Mikołaja:
https://youtu.be/SUnVGr8lWw4?t=1111

Dlaczego zadania są znane przed zajęciami? Bo nasze pomysły przed zajęciami są najważniejsze:
https://youtu.be/2RV8_naxzHE?t=4530

Nasze pomysły są najważniejsze! Żebyśmy myśleli inaczej niż wszyscy!
https://youtu.be/2RV8_naxzHE?t=5872

Nasza droga która czymś więcej niż programowanie – to wymyślanie!
https://youtu.be/OC_xrHSMYlA?t=254

=================
Programowanie, algorytmika

Po co nam to programowanie?
https://youtu.be/zN3CApegsSY?t=952
By komputer robił nudne, powtarzające się czynności.
By ułatwiał życie – przykłady problemów:
https://youtu.be/zN3CApegsSY?t=1372

Na czym polega programowanie?
Pokazaliśmy to na przykładzie oddzielania grochu od maku
https://youtu.be/zN3CApegsSY?t=1006
zobaczyliśmy, że programowanie to powtarzanie (pętla) i decyzja (warunek)
https://youtu.be/zN3CApegsSY?t=1079
Może ciut więcej

Wielu z nas myśli – ale ja nic nie umiem…
Spokojnie – będzie moc!
https://youtu.be/zN3CApegsSY?t=1092

Nie tylko będziesz pisał programy ale rozwiązywał problemy!
Algorytmika – piękna część informatyki
Dlaczego nikt nie znalazł leku na raku?
Bo komputer jest wolny.
Potrzebujemy algorytmiki – by programy się szybko kończyły
https://youtu.be/zN3CApegsSY?t=1190

Przykłady problemów algorytmicznych:
https://youtu.be/zN3CApegsSY?t=1382

Zapraszam na zajęcia z algorytmiki.
Problem źle rozwiązany komputer liczy długo, problem dobrze rozwiązany – komputer liczy ułamek sekundy,
https://youtu.be/zN3CApegsSY?t=1311

Czym jest język programowania a czym algorytmika?
https://youtu.be/iDPLi4XQN2w?t=6944

Dlaczego warto umieć programować – quiz:
https://youtu.be/zN3CApegsSY?t=609
Mogę pomóc, automatyzuję, jestem lepszy w grach – MAM FUN!

Co to jest programowanie – quiz:
https://youtu.be/zN3CApegsSY?t=450

Jaki musi być program komputerowy?
https://youtu.be/zN3CApegsSY?t=812
Poprawny – a czasem też z szybki!

=====================
Dokąd prowadzi nasza droga?
Dlaczego warto?
Video z lwem który tańczy na dachu budynku
https://youtu.be/cAQh5a4uBDw?t=31
–
Dlaczego jesteśmy potrzebni – latające parasolki, algorytmika, drony – nasza przyszłość:
https://youtu.be/NAPLYSpHlNU?t=39
–
Roboty autonomiczne:
https://youtu.be/Z6sdLhpdC2s?t=156
–
Kareta prowadzona przez roboty:
https://youtu.be/CMasYTVhIjQ?t=173
–
Bijące serce – rzeczywistość 3D:
https://youtu.be/uCOAsvGsD2k?t=22
oraz
https://youtu.be/9ue1ALMk6aE?t=3
–

=====================
OKI – na czym polegają nasze zajęcia?

Co jest najważniejsze z tej trójki?
https://youtu.be/zN3CApegsSY?t=1580
Challenge – nasze własne rozwiązania zadań!
To one pchają nas do przodu
Myślimy 4h sami – nawet jak nie zrobimy – najlepiej spędzony czas
Potem szukamy pomocy – Pitagoras nie doszedł tego momentu

Pamiętajmy co jest kluczem do sukcesu
3-6 zadań tygodniowo:
https://youtu.be/zN3CApegsSY?t=1602

Jak wrzucać/dodawać własne rozwiązanie do challenge / pracy domowej?
https://youtu.be/zN3CApegsSY?t=3972
Lista zadań w Challenge’u:
https://oki.org.pl/lista-zadan.php
Ranking:
https://oki.org.pl/ranking-z-ostatniego-tygodnia.php

Zachęcam do samodzielnego rozwiązywania zadań – wtedy się rozwijasz!
https://youtu.be/zN3CApegsSY?t=4210
Jak najwięcej samemu!

====================
Lista algorytmów i osób które wymyśliły te algorytmy:
https://www.ics.uci.edu/~eppstein/161/people.html

Lista pionierów w “ComputerScience”:
https://en.wikipedia.org/wiki/List_of_pioneers_in_computer_science 

Zastosowanie grafów:
https://www.sunjackson.com/post/7060/

—-
Jak uzyskac specjalizację w danej grupie programistycznej?
https://roadmap.sh/