Wiedza – linki do zagadnień

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

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!

———-
Jak przechowywać graf w pamięci komputera:
https://youtu.be/UOei4vez6LM?t=4090
Czym jest vector?
https://youtu.be/UOei4vez6LM?t=6053
Czym jest tablica vector-ów która trzyma graf:
https://youtu.be/UOei4vez6LM?t=6100

 

===============
DFS – Depth First Search
Algorytm który chodzi po grafie “W głąb”

Co to jest DFS?
https://youtu.be/UOei4vez6LM?t=884

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

 

===============
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

 

=================
Złożoność

Zadanie Park
Pokazało Moc algorytmik!
Wolny algorytm rozwiązuje zadanie w 3 godziny.
Szybki algorytm robi to w mniej niż w sekundę.
Powiedzieliśmy sobie czym jest operacja algorytmu:
I że nie ma znaczenia z ilu mniejszych elementów się składa:
 
Na Olimpiadzie nasz program wykonać 10^6 – 10^8 operacji:
 
Powiedzieliśmy sobie też czym jest złożoność:
Nasz program dla n danych wykonywał n*n operacji.
 
Pamiętamy o magicznych linijkach które przyspieszają wczytywanie danych i wypisywanie danych:
QUIZY 
Mieliśmy też życiowe pytanie:
Czy 5 zł ma znaczenie wobec miliona złotych? Szczególnie gdy uciekamy.
To pytanie zadaje sobie tez komputer!
Bo przecież jeśli ma wykonać milion operacji
 
Zadaliśmy sobie też pytanie – bardzo ciekawe.
Na ile sposobów można ustawić 30 osób w klasie:
Odpowiedź zaskakująca!
 
I wreszcie puenta.
Ile czasu zajmie NAJSZYBSZEMU KOMPUTEROWI na świecie sprawdzenie wszystkich ustawień klasy w rzędzie?
Ale jakie ma to znaczenie.
A gdybyśmy chcieli znaleźć ekologiczny proszek, rozkładający się plastik,… który składa się z 30 elementów – jak uczniowie w klasie…
To już ma znaczenie!

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

Nad każdym zadaniem pomyśl! https://youtu.be/2RV8_naxzHE?t=9257

Olimpijskie Koło Informatyczne #2 zaczęliśmy od nietypowej karety:
https://youtu.be/CMasYTVhIjQ?t=154
Dlaczego? Przyszłość jest nasza! Świat nas potrzebuje!!!
Potrzeba bardzo dużo programistów, osób które wymyślają
Jest mnóstwo problemów które trzeba rozwiązać – świat czeka na nas!

Czy Olimpiada Informatyczna Juniorów jest dla początkujących
czy zaawansowanych?
I dla takich i dla takich!
https://youtu.be/CMasYTVhIjQ?t=4800

O co chodzi w Olimpiadzie?
https://youtu.be/CMasYTVhIjQ?t=4885
* Żeby się poznawać algorytmy, programować
* Pretekst do rozwijania się
* Żebyśmy pod koniec roku byli dużo mocniejsi

Algorytmika – znajduje rozwiązanie problemów – świat nasz potrzebuje:
https://youtu.be/zN3CApegsSY?t=1205
OKI1 – przygotowanie OD ZERA do Olimpiady i do pięknej przyszłości!
Dlaczego jest Olimpiada. Dlaczego świat nas potrzebuje?
Czas!
Komputery są wolne i dlatego świat nas potrzebuje!

My wymyślamy a komputer liczy!
Co jest najważniejsze?
CZAS!!!

Wolny algorytm rozwiązuje zadanie w 3 godziny.
Szybki algorytm robi to w mniej niż w sekundę.
Zamiast 3 godzin nasz program działał ułamek sekund.
Zamiast złożoności O(n^2) WYMYŚLILIŚMY rozwiązanie O(n).
To jest jedyny powód dla którego jest olimpiada i algorytmika
CZAS!!!
Komputer jest wolny!
Dlatego świat potrzebuje Ciebie.
My musimy powiedzieć komputerowi jak znaleźć optymalny proszek, ułożenie elementów na taśmie, drogę ciężarówek – by zaoszczędzić prąd, zwiększyć zysk.

By mieć ciekawe życie, fun, godne życie.

Jak mam to osiągnąć – rozwiązywać problemy z Olimpiady?
https://youtu.be/qVgwgwmozcs?t=4647
Przygotowuj się do Olimpiady.
Rozwiązuj zadania.
Po pół roku zobaczy moc – to jest obietnica.
Przykład ucznia który zrobił algorytm do pakowania paczek.
Przykład ucznia który otrzymał duże pieniądze za optymalizację ryzyka.
Będziemy pożądanymi ludźmi na rynku.

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!

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

Na czym polegają nasze spotkania
Wtorki: Programowanie – ładny, czytelny kod.
Środa: Algorytmika – rozwiązujemy problemy, Olimpiada, przyszłość FUN!!!
Poniedziałek: Zaawansowana algorytmika

Na czym polegają zajęcia OKI?
https://youtu.be/zN3CApegsSY?t=1484
* Spotkania – problemy znamy wcześniej by samodzielnie pomyśleć
Nasze pomysły są bardzo ważne
* Quizy
* Challenge

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!

Przed każdymi zajęciami nasze zadanie jest publicznie dostępne:
Bo liczy się NASZ pomysł!
Zachęcam by zapisać się na newsletter
Otrzymujemy komplet informacji o zajęciach

====================
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/